phpprintf浮点数算法效力改良浮点数的printf展现

浮点数如何呈现为文本字符串？

这是一个非常棘手的难题，上次办理方案还是自1990年旁边。

在斯蒂尔和怀特（Steele and White）的“如何准确打印浮点数”之前，的实现printf和类似的渲染功能尽了最大努力来渲染浮点数，但是它们的表现办法差异很大。
例如，诸如1.3之类的数字可能会呈现为1.29999999，或者如果将一个数字放入要写出的反馈循环中并读回其书面表示形式，则每个连续结果都可能与原始结果越来越远。

斯蒂尔和怀特命名为“ Dragon4”的聪明算法（“ Dragon”算法的第四个版本）有效地办理了这个问题。
Dragon4算法在各种措辞运行时之间迅速传播，以至于如今很少有程序员理解这是一个问题。
确实，但是问题如何办理？Dragon4及其派生类非常繁芜，并且由于依赖于任意精度整数算法来打算其结果，因此它们具有很高的性能本钱。

2010年，Florian Loitsch揭橥了一篇精彩的论文，“用整数快速而精确地打印浮点数”，这是该领域20年来的最大一步：他紧张想出了如何利用机器整数来进行精确渲染！
为什么说“大部分”？由于只管Loitsch的“ Grisu3”算法非常快，但它放弃了大约0.5％的数字，在这种情形下，必须退回Dragon4或派生产品。

Grisu3比printfGNU libc中利用的算法快大约5倍。
一些措辞实现者已经把稳到了这一点：Google聘任了Loitsch，而Grisu家族在V8和Mozilla Javascript引擎中均充当默认渲染算法（取代了David Gay已有17年的dtoa代码）。
Loitsch已将其Grisu算法的实现发布为一个名为的库double-conversion。

当然，在不提及Haskell的情形下，不能不谈性能：利用了Loitsch的库并编写了一个Haskell接口，据丈量，该接口的速率比Haskell运行时库中利用的默认渲染器快30倍。
这具有一些不错的连锁效果。

任意双精度二进制浮点数的精确十进制等效项常日看起来很笨，如下所示：

0.1000000000000000055511151231257827021181583404541015625

常日，打印浮点数时，不肯望看到其所有数字。
无论如何，它们中的大多数都是“不关心的信息”。
但是，你须要几位数？想要一个短字符串，但是你希望它足够长，以便它标识原始浮点数。
打算机科学的一个众所周知的结果是，须要17位有效的十进制数字来标识任意双精度浮点数。
如果要将任何浮点数的精确十进制值四舍五入为17个有效数字，则将有一个数字，当转换回浮点数时，该数字将为您供应原始的浮点数。
也便是说，这个数字是来回可逆的。
这里的示例数字为0.10000000000000001。

但是17位数字是最坏的情形，这意味着在许多情形下，更少的数字（乃至少至一位）就可以事情。
所需的数字取决于特定的浮点数。
在我们的示例中，短字符串0.1可以办理问题。
这意味着至少就其浮点表示而言，0.1000000000000000055511151231257827021181583404541015625和0.10000000000000001和0.1相同。

以下，举例解释可以和不能缩短的十进制字符串的示例

让我们仔细看一下0.1的例子。
此双精度浮点数线图解释了其事情事理：

示例：最短的十进制字符串为1位数字

蓝色是三个浮点数的精确十进制值：中间的一个是示例数，左边的一个是在其前面的浮点数，而右边的一个是在其后的浮点数。
用灰色标记了示例编号与其邻居之间的中点。
这些中点之间的任何值都将四舍五入为示例数字。
从中可以看出，只管0.10000000000000001更近，但0.1仍在舍入范围内；因此，从最短的不雅观点出发，优选0.1。

浮点数50388143.0682372152805328369140625不能四舍五入为小于17位的数字，并且仍旧是双向的。
四舍五入为17位数字，即50388143.068237215，它将转换回浮点数。
舍入到16位数字是50388143.06823722，但是它更靠近下一个浮点数：

示例：最短的十进制字符串为17位

不存在较短的字符串，由于四舍五入到较短的长度只会引入更多的偏差。

浮点数54167628.179999999701976776123046875可以四舍五入到10位数字，但不少于10位。
四舍五入到10位数字为54167628.18。
四舍五入为9位数字，它是54167628.2，来回间隔中间相隔着2,684,354个二进制浮点数。

示例：最短的十进制字符串为10位

示例4：仅须要15位数字

浮点数9161196241250.05078125可以四舍五入到15位（9161196241250.05），并且仍旧是双向的。
当然，它也将四舍五入为17位数字（9161196241250.0508）和16位数字（9161196241250.051），这已在图中显示。

示例：最短的十进制字符串为15位

在此示例中，四舍五入为17位数字表示一个17位数字的字符串，四舍五入为16位数字表示为16位数字的字符串，而四舍五入为15位数字则为15位数字的字符串。
这与示例3不同，示例3中无论将其舍入为17、16、15、14、13、12、11或10位，都将54167628.17999999970970776776123046875舍入到10位字符串54167628.18。

接下来来阐明下为什么？

可以利用最多17个有效十进制数字来标识任何双精度浮点数。
这意味着，如果将浮点数转换为十进制字符串，将其（最靠近）四舍五入为17位数字，然后再将其转换回浮点数，则将恢复原始浮点数。
换句话说，转换是来回可逆的。

有时（很多）少于17位数字将用于来回；常日希望找到最短的此类字符串。
一些编程措辞天生最短的十进制字符串，但许多不天生。
确认措辞是什么规则的方法是，将浮点数四舍五入为递增长度的十进制字符串，然后每次检讨字符串来回是否可逆。
对付双精度，你须要四舍五入到15位数字，然后如果须要则四舍五入到16位数字，如果须要，末了四舍五入到17位数字。

让我们在2 -44上考试测验蛮力算法，该算法的十六进制浮点常量为0x1p-44，而全精度十进制值为5.684341886080801486968994140625e-14。
四舍五入为15位数字，它是5.6843418860808e-14，但这不是来回可逆的：它转换为0x1.ffffffffffffep-45。
四舍五入为16位数字，它是5.684341886080801e-14，但这也不是来回的：它转换为0x1.fffffffffffffp-45。
因此，必须利用17位标示数字5.6843418860808015e-14。

可是等等！
有来回的16位数字，我们错过了：5.684341886080802e-14。
为什么没有更靠近的16位数字，却要来回呢？

问题的根源在于二进制浮点数之间的间隙大小以两个边界的幂变革。
大于2的幂的间隙大小是小于2的幂的间隙大小的两倍。
这种不对称是必要的条件，但它本身并不会导致问题。
以及两个因子的幂附近的十进制数字之间的差距的大小。
对付双精度，有问题的十进制间隙大小仅涌如今16位数字上。

纵然对付16位数字，并不是所有的2的幂都表现出非常。
二进制和十进制数字必须以某种办法对齐。
对付初学者，最靠近的16位十进制数字必须低于2的幂，而下一个更高的16位十进制数字必须高于2的幂。
此外，最靠近的16位十进制数必须比下一个较低的53位二进制数大一半（不能为中位数，由于舍入至最靠近偶数会将其映射为2的幂），而下一个较高的16位十进制数不能超过下一个较高的53位二进制数的一半。
由于中途间隔在2的幂的任一侧都不相同，因此，越远的十进制数将映射到2的幂，但越小的十进制数则不会。

下图按比例绘制，描述了示例的情形：

示例：最短的十进制字符串不是最近的

该图显示了从2 -45指数到2 -44指数范围的53位二进制浮点数。
这在16位数浮点十进制数的10 -14范围内发生。
二进制间隙变革的从大小2 （-45 + 1-53） = 2 -97 ≈ 6.3×10 -30〜2 （-44 + 1-53） = 2 -96 ≈ 1.3×10 -29。
在该范围内的小数位间隔保持恒定为10 （-14 + 1-16） = 10 -29。
问题就在这里。
十进制间隙大小介于两个二进制间隙大小之间。

有问题的十进制间隙大小仅适用于16位十进制数字。
这是由于对付15位以下的十进制数字，十进制间隙大小大于最大的双精度二进制间隙大小，对付17位以上的十进制数字，十进制间隙大小小于最小的双精度大小。
二进制间隙大小。
后两个事实分别是来回十进制到浮点到十进制以及浮点到十进制到浮点转换的结果。

我编写了一个C程序来测试正常双精度范围内2的所有1046次幂：2 -1022到2 1023。
对付54，最靠近的16位数字不能来回，但是下一位数可以：

2 976，2 966，2 956，2 896，2 890，2 863，2 803，2 740，2 710，2 594，2 574，2 554，2 544，2 534，2 481，2 405，2 398，2 378，2 345，2 305，2 275，2 182，2 172，2 149，2 132，2 122，289，2 -24，2 -44，2 -77，2 -97，2 -140，2 -296，2 -366，2 -383，2 -489，2 -496，2 -499，2 -509， 2 -549，2 -569，2 -645，2 -652，2 -662，2 -695，2 -705，2 -778，2 -788，2 -791，2 -808，2 -921，2 - 957，2-1007，2 -1017

个中，有八个数字以15位四舍五入为整数，该数字来回：

2 966，2 956，2 890，2 740，2 149，2 -499，2 -569，2 -645

因此，如果利用蛮力测试算法，则非常行为仅在46个浮点数中起浸染。

（事实证明，对付这八种情形，15位四舍五入和非最近的16位数字是相同的。
）

同样的非常也适用于单精度，来回保护将舍入到6位或更少或9位或更多位，保留7和8位数字作为候选。

对付任何二进制精度，问题区域将位于“中间位置”，个中数字计数在两个来回边界之间。

对付负数，结果是相同的，只是图纸是镜像图像。

对Java，Python，PHP和Javascript进行了快速测试（C并没有真正的机制）。
彷佛只有Python（3）和Javascript（在Firefox，Chrome，Edge和Internet Explorer上经由测试）才被设计为返回最短的十进制字符串。
（实际上，我知道Python是这样设计的；我没有研究Javascript的设计和代码。
）