분수 십진법 변환 알고리즘, 어떻게 작동합니까?

Question

나는 고조파 비율 프로그램을 만들고 있으며 사용자가 할 수있는 부분은 다양한 비율을 연결하고 연주하는 소수 값 주파수를 사용하면 더 높거나 낮은 비율의 고정 주파수를 재생할 수 있습니다 .

어쨌든이 웹 페이지에는 주어진 십진수에서 분수 값 (비율)을 표시하는 자바 스크립트 알고리즘이 있습니다.

http://www.mindspring.com/~alanh/fracs.html

는 어떻게 작동합니까? 직접 구현하는 데 관심이 있지만 실제로 어떻게 작동하는지 이해하지 못합니다. 분수를 시험해 보면 많은 옵션 (여분의 소수점 포함)을 제공하므로 정확히 GCD가 아닙니다.

편집 :이 알고리즘 질문이 programmers.se에 더 적합 할 경우 알려 주시면 다시 게시하고 삭제하겠습니다.

Answer 1

연속 분수를 계산하여 표시하고 있습니다. 연속 분수의 각 항은 당신에게 다른 분수를 제공합니다.

사용하기로 선택할 수있는 자세한 설명 및 대체 알고리즘은 Algorithm for simplifying decimal to fractions을 참조하십시오. 당신의 소수점 값이 가장 가능성이 그 안에 저장 될 때

Answer 2

당신은 IEEE 754을 이용할 수 있으며, 가수는 정수이고 지수가 직접 그것에서 a/b 양식을 추출 할 수 있도록 너무 부문을 정수로 변환 할 수있는 곳은 필수 이진 표현을 사용합니다. 32 비트 부동 소수점 위해 우리는 가지고 :

1 bit sign 
8 bit exponent (with bias 127) 
23+1 bit mantissa (the highest bit is not present in binary but it is 1). 

지금 예를 들어 float 3.14159265358979을.

float = (sign) (mantissa+2^23)/2^(23-(exp-127)) 

: 나는 내가 가진 "대수"식으로 정의하면

3.14159265358979 = +1.10010010000111111011011b*2^(10000000b-01111111b) 
3.14159265358979 = +110010010000111111011011b/2^(23-(10000000b-01111111b)) 
3.14159265358979 = +110010010000111111011011b/2^(23-(10000000b-01111111b)) 
3.14159265358979 = +110010010000111111011011b/2^22 
3.14159265358979 = +110010010000111111011011b/2^22 
3.14159265358979 = 13176795/4194304 = 3.1415927410125732421875 

: 그래서

0x40490FDB hex 
0100 0000 0100 1001 0000 1111 1101 1011 bin 
0 10000000 10010010000111111011011 bin 
s exponent  mantissa 

: 다음 정수 타입이 Float의 내용을 읽을 경우는 다음과 같이 저장됩니다 이제 GCD을 신청하거나 원하는 것을 선택할 수 있습니다. 여기 간단합니다 C++ 코드 :

void fraction(int &a,int &b,float c) // a/b ~= c 
    { 
    union // convert between float and integer representation 
     { 
     float f32; 
     unsigned int u32; 
     } x; 
    x.f32=c; 
    int s,e; 
    s =x.u32&0x80000000; // sign bit 
    a =x.u32&0x007FFFFF; // mantisa 
    a|=  0x00800000; // add MSB in mantisa (not present in float representation) 
    e =(x.u32>>23)&0xFF; // exponent 
    e-=   0x7F; // exponent bias to make exponent signed again 

    // (optional) divide by 2 while you can (too lazy for GCD as b will be always power of 2 ...) it is better to do it on e instead of b to avoid possible overflows 
    while ((a>=2)&&((a&1)==0)) { a>>=1; e++; } 

    b=1<<(23-e);   // b= 2^(23-exp) 
    if (s) a=-a;   // sign 
    } 

이진 지수를 얻었으므로 b은 항상 2의 거듭 제곱입니다. 그 대신 GCD의가 2에 의해 a을 분할하기에 충분하다는 것을 의미하는 동안 우리가 할 수있는 및 중 증가 지수 e 또는 분할 b 최초이자 유일한 후 일반적으로 훨씬 작은 숫자에 GCD을 적용합니다. 최종 지수가 e=<-104,151>이고 결과적으로 b이 정수일 뿐이므로 오버플로를 피하기 위해 e에 적용하는 것이 더 좋으며 필요에 따라 비트 수가 훨씬 적습니다. 이 경우 b이 정수에 맞지 않습니다 (곱하기 을 2로 곱하고 e을 감소 시키거나 b에 2를 곱하여 가수가 낮은 비트를 자르기까지 ...) 당신이 링크 된 페이지에서

다음

예 :

a   b   a/b   c 
13176795/4194304 = 3.141593 ~= 3.141593 
11863283/8388608 = 1.414214 ~= 1.414214 
13573053/8388608 = 1.618034 ~= 1.618034 
    46751/ 128 = 365.242188 ~= 365.242188 

당신이 반올림 문제 부동이 때문에보다 더 나은 얻을 수있는 것보다 문자열이나 임의 정밀도에이를 계산하지 않는. 그래서 당신이 원하는 정밀도 부동 (32 비트 float, 64 비트 double, 80bit extended, ...) 가수, 지수를 추출하고 a/b

이 충분히 지금 분명 희망에 변환 선택했다. 우리가 어떻게 IEEE 754 폼을 (문자열/값) 형식으로 가져올 수 있는지 알고 싶다면 바이너리로 변환하십시오. 분수 부분 만 있으면되고 원본베이스 (10 또는 2^8,2^16,2^32,...)의 대상베이스 (2)에 의한 연속적인 곱셈에 의해 수행됩니다. 따라서 각 반복에서 값을 곱하고 결과의 정수 부분은 새로운 자릿수이며 다음 반복에 분수 부분을 사용합니다 ... 값이 0이 아니거나 최대 자릿수가 사용될 때까지 반복합니다.

0.123 0b 
0.246 -> 0.0b 
0.492 -> 0.00b 
0.984 -> 0.000b 
1.968 -> 0.0001b 
1.936 -> 0.00011b 
1.872 -> 0.000111b 
1.744 -> 0.0001111b 
1.488 -> 0.00011111b 
0.976 -> 0.000111110b