小数到分数的转换算法，它是如何工作的？

问题描述 投票：0回答：3

我正在开发一个谐波比程序，我希望用户能够做的部分事情是插入各种比率，并让正在播放的十进制值频率向您显示更多更高或更低的比率锁定频率。

无论如何，在这个网页上有一个 JavaScript 算法来显示给定小数的分数（比率）。

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

它是如何运作的？我有兴趣自己实现它，但我不太明白它是如何运作的。如果你尝试一些分数，它会给你很多选择（有些带有额外的小数），所以它不仅仅是 GCD。

编辑：如果这个算法问题更适合程序员。请告诉我，我会在那里重新发布并删除它。

algorithm decimal fractions
3个回答
3
投票

您可以利用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
的幂。这意味着用 a 除以 
2
而不是 
GCD
就足够了，而我们可以增加指数 
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
，80位
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
2
投票

它正在计算连分数并显示它。连分数中的每一项都会给你一个更好的分数。

请参阅将小数简化为分数的算法，了解更详细的说明和您可以选择使用的替代算法。

0
投票

我对 sprintf 包装器使用了稍微不同的方法。所有 10 的幂（以及其他数字基数）都可以除以 2 的幂的数字基数的因子，如下例所示

10^11 = 10^8 * 10^2 * 10^1

这就是为什么我们需要一个包含 10 的 2 次方的数组来查找十进制指数。 然后我们需要迭代该数组（甚至进行二分搜索）以查找值在其中的位置。 之后，我们返回到数组的开头，将我们的数字除以基数的所有幂（低于或等于剩余结果），直到我们的值最终变成搜索到的尾数，即 1.0 和我们的基数之间的数字。 这减少了寻找底数指数的迭代次数。仅在双打以 10 为基数的情况下，最多需要进行 9 次比较。在我的 github 上的 sprintf 包装器中，callback_printf.c 中有一个函数（base10），它使用它来计算小数尾数并查找指数。

https://github.com/klux21/callback_printf

它还包含函数“rebase”，它可以对其他数字基数执行相同的操作，并动态生成所需的数组。

但是当然，我们也可以在包含所有现有 10 次方的数组中进行简单的二分搜索。这会将之后的除法数量减少到只有一个，并且会以一些内存为代价得到更准确的结果。但在今天，几百个双精度数（甚至八千个长双精度数）实际上并不是那么多的内存。甚至可以将其放入处理器中。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.