문자열에서 부동 소수점 숫자를 수동으로 구문 분석하는 방법
https://stackoverflow.com/questions/85223
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
물론 대부분의 언어에는 이를 위한 라이브러리 기능이 있지만 내가 직접 수행하고 싶다고 가정해 보겠습니다.
C 또는 Java 프로그램에서와 같이 float가 제공된다고 가정합니다('f' 또는 'd' 접미사 제외). 예를 들어 "4.2e1", ".42e2" 또는 단순히 "42".일반적으로 소수점 앞에는 "정수부", 소수점 뒤에는 "분수부", "지수"가 있습니다.세 개 모두 정수입니다.
개별 숫자를 찾아 처리하는 것은 쉽지만 이를 유형의 값으로 구성하는 방법은 무엇입니까? float 또는 double 정밀도를 잃지 않고?
정수 부분에 10^을 곱할 생각이에요N, 어디 N 는 분수부의 자릿수이고, 정수부에 분수부를 더하고 빼는 것입니다. N 지수에서.이는 효과적으로 변한다. 4.2e1 ~ 안으로 42e0, 예를 들어.그런 다음 pow 10^을 계산하는 함수멱지수 결과에 새로운 정수 부분을 곱합니다.문제는 이 방법이 전체적으로 최대의 정밀도를 보장하는가입니다.
이것에 대한 생각이 있나요?
해결책
나는 이진 표현을 사용하여 부동 소수점 숫자를 직접 조합할 것입니다.
숫자를 하나씩 읽고 먼저 모든 숫자를 찾으세요.정수 산술로 그렇게 하세요.또한 소수점과 지수를 기록해 두십시오.이것은 나중에 중요할 것입니다.
이제 부동 소수점 숫자를 조합할 수 있습니다.가장 먼저 해야 할 일은 첫 번째 세트 1비트(가장 높은 것에서 가장 낮은 것까지)에 대한 숫자의 정수 표현을 스캔하는 것입니다.
첫 번째 1비트 바로 다음의 비트가 가수입니다.
지수를 구하는 것도 어렵지 않습니다.과학적 표기법의 첫 번째 1비트 위치, 소수점 위치 및 선택적 지수를 알고 있습니다.그것들을 결합하고 부동 소수점 지수 바이어스를 추가합니다(127인 것 같지만 참조를 확인하십시오).
이 지수는 0에서 255 사이에 있어야 합니다.더 크거나 작으면 양수 또는 음수 무한대가 됩니다(특별한 경우).
지수를 float의 비트 24~30에 그대로 저장합니다.
가장 중요한 비트는 단순히 기호입니다.1은 음수를 의미하고, 0은 양수를 의미합니다.
실제보다 설명하기가 어렵습니다. 부동 소수점 수를 분해하고 지수와 가수를 살펴보면 실제로 얼마나 쉬운지 알 수 있습니다.
그런데 - 부동 소수점 자체에서 산술 연산을 수행하는 것은 나쁜 생각입니다. 가수가 항상 23개의 유효 비트로 잘리도록 강제하기 때문입니다.그런 식으로는 정확한 표현을 얻을 수 없습니다.
다른 팁
다른 모든 답변은 어떻게 놓쳤습니까? 딱딱한 이것을 제대로 하는 것입니다.어느 정도 정확한 첫 번째 컷 접근 방식을 수행할 수 있지만 IEEE 반올림 모드(et al)를 고려할 때까지는 결코 오른쪽 답변.나는 이전에 상당히 많은 양의 오류가 있는 순진한 구현을 작성한 적이 있습니다.
수학이 두렵지 않다면 David Goldberg의 다음 기사를 읽어 보시기 바랍니다. 모든 컴퓨터 과학자가 부동 소수점 산술에 대해 알아야 할 사항.내부적으로 무슨 일이 일어나고 있는지, 그리고 왜 비트가 그렇게 배치되었는지 더 잘 이해할 수 있을 것입니다.
나의 최선의 조언은 작동하는 atoi 구현부터 시작하여 거기에서 벗어나는 것입니다.당신은 빠진 것이 있다는 것을 금방 깨닫게 될 것입니다. 그러나 몇 가지를 살펴보면 strtod의 소스를 찾으면 올바른 길(길고 긴 길)에 있게 될 것입니다.결국엔 칭찬해줄게 여기에 다이어트를 삽입하세요 표준 라이브러리가 있다는 것입니다.
/* use this to start your atof implementation */
/* atoi - christopher.watford@gmail.com */
/* PUBLIC DOMAIN */
long atoi(const char *value) {
unsigned long ival = 0, c, n = 1, i = 0, oval;
for( ; c = value[i]; ++i) /* chomp leading spaces */
if(!isspace(c)) break;
if(c == '-' || c == '+') { /* chomp sign */
n = (c != '-' ? n : -1);
i++;
}
while(c = value[i++]) { /* parse number */
if(!isdigit(c)) return 0;
ival = (ival * 10) + (c - '0'); /* mult/accum */
if((n > 0 && ival > LONG_MAX)
|| (n < 0 && ival > (LONG_MAX + 1UL))) {
/* report overflow/underflow */
errno = ERANGE;
return (n > 0 ? LONG_MAX : LONG_MIN);
}
}
return (n>0 ? (long)ival : -(long)ival);
}
십진수를 최상의 부동 소수점 근사값으로 변환하는 "표준" 알고리즘은 William Clinger의 알고리즘입니다. 부동 소수점 숫자를 정확하게 읽는 방법,에서 다운로드 가능 여기.이 작업을 올바르게 수행하려면 특수한 경우를 처리하기 위해 최소한 특정 비율의 다중 정밀도 정수가 필요합니다.
다른 방향으로 진행하여 부동 숫자에서 가장 좋은 십진수를 인쇄하는 알고리즘은 Burger 및 Dybvig's에서 찾을 수 있습니다. 부동 소수점 숫자를 빠르고 정확하게 인쇄하기, 다운로드 가능 여기.또한 다중 정밀도 정수 연산이 필요합니다.
David M Gay의 글도 참조하세요. 올바르게 반올림된 이진-십진수 및 십진수-이진수 변환 알고리즘이 양방향으로 진행되기 때문입니다.
구문 분석 시 소수점을 무시할 수 있습니다(위치 제외).입력이 다음과 같다고 가정해 보겠습니다.156.7834e10...이는 정수 1567834 뒤에 e10이 오는 것으로 쉽게 구문 분석할 수 있습니다. 그런 다음 소수점은 float의 "숫자" 부분 끝에서 4자리이므로 e6으로 수정합니다.
정밀도가 문제입니다.사용 중인 언어의 IEEE 사양을 확인해야 합니다.가수(또는 분수)의 비트 수가 정수 유형의 비트 수보다 큰 경우 누군가가 다음과 같은 숫자를 입력하면 정밀도가 떨어질 수 있습니다.
5123.123123e0 - 우리 방법에서는 5123123123으로 변환하는데, 이는 Integer에 맞지 않지만 5.123123123의 비트는 float 사양의 가수에 맞을 수 있습니다.
물론 소수점 앞의 각 숫자를 가져와 현재 합계(부동 소수점)에 10을 곱한 다음 새 숫자를 추가하는 방법을 사용할 수 있습니다.소수점 이하 자릿수의 경우 현재 합계에 추가하기 전에 숫자에 10의 거듭제곱을 곱합니다.그러나 이 방법은 쉽게 사용할 수 있는 구문 분석 라이브러리를 사용하지 않고 부동 소수점 프리미티브를 사용해야 하기 때문에 왜 이 작업을 수행하는지에 대한 의문을 불러일으키는 것 같습니다.
어쨌든, 행운을 빌어요!
예, 구성을 부동 소수점 연산으로 분해할 수 있습니다. ~하는 한 이러한 작업은 정확한, 그리고 당신은 단일 최종 부정확 작업.
불행하게도 부동소수점 연산 곧 부정확해지면 가수의 정밀도를 초과하면 결과가 반올림됩니다.반올림 "오류"가 발생하면 이후 작업에서 누적됩니다...
그래서 일반적으로, 아니요, 임의의 소수를 변환하기 위해 이러한 순진한 알고리즘을 사용할 수 없습니다. 이로 인해 다른 사람들이 이미 말한 것처럼 올바른 숫자의 몇 ulp가 잘못 반올림된 숫자가 발생할 수 있습니다.
하지만 우리가 얼마나 멀리 갈 수 있는지 봅시다:
플로트를 다음과 같이 주의 깊게 재구성한다면:
if(biasedExponent >= 0)
return integerMantissa * (10^biasedExponent);
else
return integerMantissa / (10^(-biasedExponent));
자릿수가 많은 경우 IntegerMantissa를 누적할 때와 10을biasedExComponent의 거듭제곱으로 올릴 때 정밀도를 초과할 위험이 있습니다.
다행스럽게도 처음 두 연산이 정확하면 IEEE 속성 덕분에 최종 부정확한 연산 * 또는 /를 감당할 수 있으며 결과는 올바르게 반올림됩니다.
이것을 24비트의 정밀도를 갖는 단정밀도 부동소수점에 적용해 보겠습니다.
10^8 > 2^24 > 10^7
2의 배수는 지수만 증가시키고 가수는 변경되지 않은 채로 남겨두므로 10의 지수화를 위해 5의 거듭제곱만 처리하면 됩니다.
5^11 > 2^24 > 5^10
하지만 IntegerMantissa와 -10에서 10 사이의 BiasedExComponent에서 7자리 정밀도를 허용할 수 있습니다.
배정밀도에서는 53비트,
10^16 > 2^53 > 10^15
5^23 > 2^53 > 5^22
따라서 십진수 15자리와 -22에서 22 사이의 편향 지수를 감당할 수 있습니다.
숫자가 항상 올바른 범위에 속하는지 확인하는 것은 귀하에게 달려 있습니다.(정말 까다롭다면 뒤에 오는 0을 삽입/제거하여 가수와 지수의 균형을 맞출 수 있습니다.)
그렇지 않으면 확장된 정밀도를 사용해야 합니다.
귀하의 언어가 임의의 정밀도 정수를 제공하는 경우 이를 올바르게 구현하는 것이 약간 까다롭지만 그렇게 어렵지는 않습니다. 저는 Smalltalk에서 이 작업을 수행하고 다음 블로그에서 이에 대해 블로그에 올렸습니다. http://smallissimo.blogspot.fr/2011/09/clarifying-and-optimizing.html 그리고 http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html
이는 간단하고 순진한 구현입니다.다행히도 libc는 더 최적화되어 있습니다.
내 첫 번째 생각은 문자열을 int64 가수와 int 가수의 처음 18자리만 사용하는 십진수 지수.예를 들어 1.2345e-5는 12345와 -9로 구문 분석됩니다.그런 다음 가수에 10을 곱하고 가수 길이가 18자리(정밀도 >56비트)가 될 때까지 지수를 감소시킵니다.그런 다음 십진수 n*10^m에서 이진수 p*2^q 형식으로 변환하는 데 사용할 수 있는 요소와 이진 지수를 찾기 위해 테이블에서 십진 지수를 찾습니다.요인은 또 다른 것일 것이다 int64 그래서 나는 가수에 곱하여 결과 128비트 숫자의 상위 64비트를 얻었습니다.이것 int64 가수는 필요한 정밀도만 손실되는 부동 소수점으로 캐스팅될 수 있으며 2^q 지수는 정밀도 손실 없이 곱셈을 사용하여 적용될 수 있습니다.
나는 이것이 매우 정확하고 매우 빠르기를 기대하지만 특수 숫자 NaN, -infinity, -0.0 및 infinity를 처리하고 싶을 수도 있습니다.비정규화된 숫자나 반올림 모드에 대해서는 생각해 본 적이 없습니다.
이를 위해서는 적절한 바이너리 표현을 위해 표준 IEEE 754를 이해해야 합니다.그 후에는 사용할 수 있습니다 Float.intBitsToFloat 또는 Double.longBitsToDouble.
가능한 가장 정확한 결과를 원한다면 더 높은 내부 작업 정밀도를 사용한 다음 결과를 원하는 정밀도로 하향 변환해야 합니다.몇 가지 ULP 오류가 마음에 들지 않으면 필요에 따라 원하는 정밀도로 10을 반복적으로 곱할 수 있습니다.pow() 함수는 큰 지수에 대해 부정확한 결과를 생성하므로 사용하지 않겠습니다.
숫자를 나타내는 임의의 문자열을 정밀도를 잃지 않고 double 또는 float로 변환하는 것은 불가능합니다.십진수로 정확하게 표시할 수 있는 분수가 많이 있습니다(예:"0.1") 이는 이진 부동 소수점 또는 이중 형식으로만 근사화될 수 있습니다.이는 분수 1/3이 십진수로 정확하게 표시될 수 없는 것과 유사합니다. 0.333333...만 쓸 수 있습니다.
라이브러리 함수를 직접 사용하고 싶지 않다면 해당 라이브러리 함수의 소스 코드를 살펴보는 것은 어떨까요?당신은 Java를 언급했습니다.대부분의 JDK에는 클래스 라이브러리의 소스 코드가 함께 제공되므로 java.lang.Double.parseDouble(String) 메서드가 작동하는 방식을 찾아볼 수 있습니다.물론 BigDecimal과 같은 것이 정밀도와 반올림 모드를 제어하는 데 더 좋지만 부동 소수점 또는 이중이어야 한다고 말씀하셨습니다.
상태 머신을 사용합니다.이는 매우 쉽고 데이터 스트림이 중단된 경우에도 작동합니다(상태와 부분 결과만 유지하면 됩니다).(더 복잡한 작업을 수행하는 경우) 파서 생성기를 사용할 수도 있습니다.
종착역에 동의합니다.파서가 깨질 수 있는 어리석은 방법이 많기 때문에 상태 머신은 이 작업을 수행하는 가장 좋은 방법입니다.지금 하나 작업 중인데 완성된 것 같고 13개 상태가 있는 것 같아요.
문제는 사소한 것이 아닙니다.
저는 부동 소수점 하드웨어 설계에 관심이 있는 하드웨어 엔지니어입니다.두 번째 구현을 진행 중입니다.
오늘 이걸 찾았어요 http://speleotrove.com/decimal/decarith.pdf
18페이지에는 몇 가지 흥미로운 테스트 사례가 나와 있습니다.
예, Clinger의 기사를 읽었지만 단순한 하드웨어 엔지니어이기 때문에 제시된 코드를 이해할 수 없습니다.Knuth의 텍스트에서 답변된 Steele의 알고리즘에 대한 참조는 나에게 도움이 되었습니다.입력과 출력 모두 문제가 있습니다.
위에서 언급한 다양한 기사에 대한 언급은 모두 훌륭합니다.
아직 여기에 가입하지 않았지만 가입하면 로그인이 이루어지지 않는다고 가정하면 broh가 될 것입니다.(브로 도트).
클라이드
