代码之家 › 专栏 › 技术社区 › R.. GitHub STOP HELPING ICE

如何打印浮点数的精确值?

floating-point math algorithm c

R.. GitHub STOP HELPING ICE · 技术社区 · 14 年前

首先,这不是一个浮点数新手问题。我知道浮点运算的结果(更不用说超越函数)通常不能精确表示,而且大多数终止小数不能精确表示为二进制浮点数。

也就是说,每个可能的浮点值正好对应于一个二元有理数(一个有理数 p/q 哪里 q 是2的幂),它依次具有精确的十进制表示。

我的问题是:如何有效地找到这个精确的十进制表示法? sprintf 类似的函数通常只指定若干个有效数字来唯一地确定原始浮点值;它们不必打印精确的十进制表示。我知道我用过一种算法,但速度很慢, O(e^2) 哪里 e 是指数。下面是一个大纲:

将尾数转换为十进制整数。您可以通过分离位来直接读取尾数,也可以编写一个混乱的浮点循环,该循环首先将值乘以2的幂,将其置于1<=x<10的范围内,然后通过强制转换为int、减法和乘以10,一次提取一个数字。
通过反复乘以或除以2来应用指数。这是一个关于一串生成的小数位数。每~3次乘法都会在左边多加一个数字。每一个人都会在右边多加一个数字。

这真的是最好的吗?我对此表示怀疑,但我不是浮点专家,我找不到一种方法可以在不产生不精确结果的情况下,对数字的浮点表示进行以10为基数的计算(乘以或除以除2的幂以外的任何值,都是对浮点数的一种有损操作,除非你知道你有自由位要工作。k)。

10 回复 | 直到 8 年前

kennytm 8 年前

这个问题有官僚部分和算法部分。浮点数在内部存储为(2 ^e _m),其中e是指数(本身为二进制),m是尾数。问题的官僚主义部分是如何访问这些数据,但R.似乎对问题的算法部分更感兴趣,即转换(2 ^e _m)小数(A/B)。用几种语言回答这个官僚主义问题的答案是“frexp”(这是一个有趣的细节,我以前不知道)。

的确,乍一看,它需要 ^二 )只写2 ^e 以小数为单位,尾数还有更多的时间。但是,多亏了 Schonhage-Strassen 快速乘法算法,您可以在_(e)时间内完成,其中tilde表示“最多对数因子”。如果你把Schonhage Strassen看作是魔法,那么想怎么做并不难。如果e为偶数,则可以递归计算2 ^e/2 然后用快速乘法将其平方。另一方面,如果e是奇数,则可以递归地计算2 ^E-1 然后加倍。你必须仔细检查是否有Schonhage Strassen的版本在10基。虽然没有广泛的文档记录,但是可以在任何基础上完成。

将一个很长的尾数从二进制转换为基数10的问题并不完全相同,但它有一个相似的答案。你可以把尾数分成两半,m=a 2 ^K +然后递归地将a和b转换成10进制,将2^k转换成10进制,再做一个快速乘法,以10进制计算m。

所有这些背后的抽象结果是,您可以在_(n)时间内将整数从一个基转换为另一个基。

如果问题是关于标准的64位浮点数,那么对于复杂的Schonhage-Strassen算法来说,它太小了。在这个范围内,您可以使用各种技巧来节省工作。一种方法是存储2的所有2048个值 ^e 在查找表中,然后在尾数中使用不对称乘法(在长乘法和短乘法之间)。另一个技巧是在10000基(或者10的更大功率,取决于架构)中工作,而不是10基。但是,正如R.在评论中指出的那样,128位浮点数已经允许足够大的指数对查找表和标准长乘法都产生疑问。作为一个实际问题,长乘法是最快的,最多可达几个数字,然后在一个有效的中等范围内可以使用 Karatsuba multiplication 或 Toom-Cook multiplication 之后,Schonhage-Strassen的变化不仅在理论上最好,在实践中也最好。

实际上,大整数包 GMP 已经有了(n)时间基数转换,以及选择乘法算法的良好启发式。他们的解和我的解的唯一区别是,他们不在基10中做任何大的算术,而是在基2中计算10的大幂。在这个解中,它们也需要快速除法,但可以通过几种方法中的任何一种从快速乘法中获得。

ib. Evgeny Shavlyugin 11 年前

我看到您已经接受了一个答案,但下面是一些您可能希望查看的此转换的开放源代码实现:

David Gay dtoa() 功能在 dtoa.c ( http://www.netlib.org/fp/dtoa.c )
函数 ___printf_fp() 在文件中 /stdio-common/printf_fp.c 在GLYBC中 http://ftp.gnu.org/gnu/glibc/glibc-2.11.2.tar.gz 例如。

两者都将按您在 %f 类型 printf (正如我在这里写的: http://www.exploringbinary.com/print-precision-of-dyadic-fractions-varies-by-language/ 和 http://www.exploringbinary.com/print-precision-of-floating-point-integers-varies-too/ )

Norman Ramsey 14 年前

在打印浮点数字方面有很多工作。黄金标准是打印出一个最小长度的十进制等价物,这样当十进制等价物被重新读取时,无论在重新读取过程中采用什么舍入模式,您都能得到与开始时相同的浮点数。你可以在优秀的 paper by Burger and Dybvig .

Gabe Timothy Khouri 14 年前

虽然它是c并且你的问题被标记为c,但jon skeet有代码来转换a double 以字符串的形式精确表示: http://www.yoda.arachsys.com/csharp/DoubleConverter.cs

从一个快速的视角来看,它似乎不太难移植到C,甚至更容易在C++中编写。

经过进一步的思考,乔恩的算法似乎也是O(e^2),因为它也在指数上循环。但是,这意味着算法是O(对数(n)^2)(其中n是浮点数),我不确定您是否可以在比对数平方时间更好的情况下从基数2转换为基数10。

Byron Whitlock 14 年前

作为一个不擅长浮点运算的专家,我倾向于使用经过良好测试的开放源码库。

这个 GNU MPFR 是一个好的。

MPFR库是用于多精度浮点使用正确的四舍五入进行计算。 MPFR的主要目标是提供多精度库浮点计算,即既有效率又有明确的定义语义学。

dan04 14 年前

sprintf和类似功能通常最多只能指定一个数字有效数字的唯一确定原始浮点价值;它们不必打印精确的十进制表示。

您可以要求输入比默认值更多的有效数字:

printf("%.100g\n", 0.1);

印刷品 0.1000000000000000055511151231257827021181583404541015625 .

Michael Dorgan 14 年前

如果你想要更精确的结果,为什么不使用定点数学呢?转换速度很快。错误是已知的,可以解决。不是你问题的确切答案,而是你的另一个想法。

eruciform 14 年前

从我的头上看,为什么不先把指数分解成二进制指数的和,那么所有的操作都会损失更少。

即。

10^2 = 2^6 + 2^5 + 2^2

然后总结:

mantissa<<6 + mantissa<<5 + mantissa<<2

我想把它分解成数字的O(n),移位是O(1),求和是O(n)位数…

当然,您必须有一个足够大的整数类来存储结果…

让我知道-我很好奇,这真的让我想起来了。-)

Spektre 9 年前

有三种方法

正在打印数字 bin 或 hex

这是最精确的方法。我更喜欢 十六进制 因为它更像基地 10 例如阅读/感觉 F.8h = 15.5 这里没有精度损失。

印刷在 dec 但只有相关数字

我的意思是只有数字可以 1 尽可能接近你的数字。

num 属于 整数位数 简单精确(无精度损失):

// n10 - base 10 integer digits
// n2  - base 2 integer digits
n10=log10(2^n2)
n10=log2(2^n2)/log2(10)
n10=n2/log2(10)
n10=ceil(n2*0.30102999566398119521373889472449)
// if fist digit is 0 and n10 > 1 then n10--

号码 属于 小数位数 更棘手和经验性的是,我发现:

// n10 - base 10 fract. digits
// n2  - base 2 fract. digits >= 8
n10=0; if (n02==8) n10=1;
else if (n02==9) n10=2;
else if (n02> 9)
    {
    n10=((n02-9)%10);
         if (n10>=6) n10=2;
    else if (n10>=1) n10=1;
    n10+=2+(((n02-9)/10)*3);
    }

如果创建依赖关系表 n02 <-> n10 然后你看到这个常数 0.30102999566398119521373889472449 仍然存在,但从8位开始,因为less不能表示 0.1 精度令人满意( 0.85 - 1.15 )因为基的负指数 2 依赖关系不是线性的,而是模式。此代码适用于小比特数( <=52 )但在较大的位计数下,可能会出现错误,因为使用的模式不适合 log10(2) 或 1/log2(10) 确切地。

对于更大的位计数,我使用这个:

n10=7.810+(9.6366363636363636363636*((n02>>5)-1.0));

但这个公式是32位对齐的!!!!还有更大的比特数广告错误。

附笔。 十进制数二进制表示的进一步分析

0.1
0.01
0.001
0.0001
...

可以显示精确的模式重复,这将导致任何位计数的相关数字的确切数目。

为了清晰:

8 bin digits -> 1 dec digits
9 bin digits -> 2 dec digits
10 bin digits -> 3 dec digits
11 bin digits -> 3 dec digits
12 bin digits -> 3 dec digits
13 bin digits -> 3 dec digits
14 bin digits -> 3 dec digits
15 bin digits -> 4 dec digits
16 bin digits -> 4 dec digits
17 bin digits -> 4 dec digits
18 bin digits -> 4 dec digits
19 bin digits -> 5 dec digits
20 bin digits -> 6 dec digits
21 bin digits -> 6 dec digits
22 bin digits -> 6 dec digits
23 bin digits -> 6 dec digits
24 bin digits -> 6 dec digits
25 bin digits -> 7 dec digits
26 bin digits -> 7 dec digits
27 bin digits -> 7 dec digits
28 bin digits -> 7 dec digits
29 bin digits -> 8 dec digits
30 bin digits -> 9 dec digits
31 bin digits -> 9 dec digits
32 bin digits -> 9 dec digits
33 bin digits -> 9 dec digits
34 bin digits -> 9 dec digits
35 bin digits -> 10 dec digits
36 bin digits -> 10 dec digits
37 bin digits -> 10 dec digits
38 bin digits -> 10 dec digits
39 bin digits -> 11 dec digits
40 bin digits -> 12 dec digits
41 bin digits -> 12 dec digits
42 bin digits -> 12 dec digits
43 bin digits -> 12 dec digits
44 bin digits -> 12 dec digits
45 bin digits -> 13 dec digits
46 bin digits -> 13 dec digits
47 bin digits -> 13 dec digits
48 bin digits -> 13 dec digits
49 bin digits -> 14 dec digits
50 bin digits -> 15 dec digits
51 bin digits -> 15 dec digits
52 bin digits -> 15 dec digits
53 bin digits -> 15 dec digits
54 bin digits -> 15 dec digits
55 bin digits -> 16 dec digits
56 bin digits -> 16 dec digits
57 bin digits -> 16 dec digits
58 bin digits -> 16 dec digits
59 bin digits -> 17 dec digits
60 bin digits -> 18 dec digits
61 bin digits -> 18 dec digits
62 bin digits -> 18 dec digits
63 bin digits -> 18 dec digits
64 bin digits -> 18 dec digits

最后别忘了把切掉的数字四舍五入!!!!也就是说,如果最后一个相关数字后面的数字是 >=5 在12月比最后一个相关数字应该是 +1 …如果已经有了 9 比你必须转到前一个数字等等…

打印精确值

打印 分数二进制数 只打印分数 n 数字在哪里 n 是小数位数,因为表示的值是该值的和,所以小数不能大于 号码 的小数位数 LSB . 上面的内容(项目符号 α2 )与将十进制数存储到相关 float (或打印相关的小数)。

两个精确值的负幂…

2^- 1 = 0.5
2^- 2 = 0.25
2^- 3 = 0.125
2^- 4 = 0.0625
2^- 5 = 0.03125
2^- 6 = 0.015625
2^- 7 = 0.0078125
2^- 8 = 0.00390625
2^- 9 = 0.001953125
2^-10 = 0.0009765625
2^-11 = 0.00048828125
2^-12 = 0.000244140625
2^-13 = 0.0001220703125
2^-14 = 0.00006103515625
2^-15 = 0.000030517578125
2^-16 = 0.0000152587890625
2^-17 = 0.00000762939453125
2^-18 = 0.000003814697265625
2^-19 = 0.0000019073486328125
2^-20 = 0.00000095367431640625

现在负的力量 十 按64位的精确值样式打印 doubles :

10^+ -1 = 0.1000000000000000055511151231257827021181583404541015625
        = 0.0001100110011001100110011001100110011001100110011001101b
10^+ -2 = 0.01000000000000000020816681711721685132943093776702880859375
        = 0.00000010100011110101110000101000111101011100001010001111011b
10^+ -3 = 0.001000000000000000020816681711721685132943093776702880859375
        = 0.000000000100000110001001001101110100101111000110101001111111b
10^+ -4 = 0.000100000000000000004792173602385929598312941379845142364501953125
        = 0.000000000000011010001101101110001011101011000111000100001100101101b
10^+ -5 = 0.000010000000000000000818030539140313095458623138256371021270751953125
        = 0.000000000000000010100111110001011010110001000111000110110100011110001b
10^+ -6 = 0.000000999999999999999954748111825886258685613938723690807819366455078125
        = 0.000000000000000000010000110001101111011110100000101101011110110110001101b
10^+ -7 = 0.0000000999999999999999954748111825886258685613938723690807819366455078125
        = 0.0000000000000000000000011010110101111111001010011010101111001010111101001b
10^+ -8 = 0.000000010000000000000000209225608301284726753266340892878361046314239501953125
        = 0.000000000000000000000000001010101111001100011101110001000110000100011000011101b
10^+ -9 = 0.0000000010000000000000000622815914577798564188970686927859787829220294952392578125
        = 0.0000000000000000000000000000010001001011100000101111101000001001101101011010010101b
10^+-10 = 0.00000000010000000000000000364321973154977415791655470655996396089904010295867919921875
        = 0.00000000000000000000000000000000011011011111001101111111011001110101111011110110111011b
10^+-11 = 0.00000000000999999999999999939496969281939810930172340963650867706746794283390045166015625
        = 0.00000000000000000000000000000000000010101111111010111111111100001011110010110010010010101b
10^+-12 = 0.00000000000099999999999999997988664762925561536725284350612952266601496376097202301025390625
        = 0.00000000000000000000000000000000000000010001100101111001100110000001001011011110101000010001b
10^+-13 = 0.00000000000010000000000000000303737455634003709136034716842278413651001756079494953155517578125
        = 0.00000000000000000000000000000000000000000001110000100101110000100110100001001001011101101000001b
10^+-14 = 0.000000000000009999999999999999988193093545598986971343290729163921781719182035885751247406005859375
        = 0.000000000000000000000000000000000000000000000010110100001001001101110000110101000010010101110011011b
10^+-15 = 0.00000000000000100000000000000007770539987666107923830718560119501514549256171449087560176849365234375
        = 0.00000000000000000000000000000000000000000000000001001000000011101011111001111011100111010101100001011b
10^+-16 = 0.00000000000000009999999999999999790977867240346035618411149408467364363417573258630000054836273193359375
        = 0.00000000000000000000000000000000000000000000000000000111001101001010110010100101111101100010001001101111b
10^+-17 = 0.0000000000000000100000000000000007154242405462192450852805618492324772617063644020163337700068950653076171875
        = 0.0000000000000000000000000000000000000000000000000000000010111000011101111010101000110010001101101010010010111b
10^+-18 = 0.00000000000000000100000000000000007154242405462192450852805618492324772617063644020163337700068950653076171875
        = 0.00000000000000000000000000000000000000000000000000000000000100100111001001011101110100011101001001000011101011b
10^+-19 = 0.000000000000000000099999999999999997524592683526013185572915905567688179926555402943222361500374972820281982421875
        = 0.000000000000000000000000000000000000000000000000000000000000000111011000001111001001010011111011011011010010101011b
10^+-20 = 0.00000000000000000000999999999999999945153271454209571651729503702787392447107715776066783064379706047475337982177734375
        = 0.00000000000000000000000000000000000000000000000000000000000000000010111100111001010000100001100100100100100001000100011b

现在10的负幂只打印相关的十进制数字样式(我更习惯这个样式)为64位 双打 :

10^+ -1 = 0.1
10^+ -2 = 0.01
10^+ -3 = 0.001
10^+ -4 = 0.0001
10^+ -5 = 0.00001
10^+ -6 = 0.000001
10^+ -7 = 0.0000001
10^+ -8 = 0.00000001
10^+ -9 = 0.000000001
10^+-10 = 0.0000000001
10^+-11 = 0.00000000001
10^+-12 = 0.000000000001
10^+-13 = 0.0000000000001
10^+-14 = 0.00000000000001
10^+-15 = 0.000000000000001
10^+-16 = 0.0000000000000001
10^+-17 = 0.00000000000000001
10^+-18 = 0.000000000000000001
10^+-19 = 0.0000000000000000001
10^+-20 = 0.00000000000000000001

希望有帮助:)

-2

Steven Sudit 14 年前

你不知道。你能做到的最接近的就是转储字节。