小数到分数转换算法，它是如何工作的？(Decimals to Fractions Conversio

我工作的是我希望用户能够做一个调和比和部位是插在不同的比例，并有正在播放的节目，你更比锁定频率变得更高或更低的十进制数值频率。

无论如何，在此网页上有一个JavaScript算法，以显示从给定的小数部分值（比）。

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

它是如何工作的？我感兴趣的执行它自己，但我真的不明白它是如何发挥作用。如果你尝试了一些分数，它为您提供了许多选项（有些额外小数），所以它不是完全只是GCD。

编辑：如果这种算法的问题是更适合programmers.se只是让我知道，我会重新发布那里删除。

Answer 1:

据计算连分数并显示。在连分数每学期给你另一部分是一个数量级的更好。

见用于简化小数分数算法进行更详细的解释和替代算法，你可以选择使用。

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 。如果我读这个浮动内容作为整数类型则存储为：

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

所以：

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

如果我把它定义为“代数”公式我：

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

现在，你可以申请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就足以划分a由2 ，而我们可以和任何增加指数e或除b第一，只适用GCD后通常更小的数字。更好地应用此上e避免溢出作为最终指数为e=<-104,151>并且将所得b只是整数所以它有，因为它需要大量的要少得多的比特。在这种情况下b不适合整数做相反的（乘以a由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的形式把它归结为转换为二进制。我们只需要小数部分和由连续的乘法由目标基站（进行2在源基站）（ 10或2^8,2^16,2^32,... ）。因此，在每次迭代乘以值，结果的整数部分是新的数字，并使用小数部分进行下一次迭代......重复，直到值不为零或最大位数使用。

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