算法效率改进，浮点数的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倍。这具有一些不错的连锁效果。
17位有效的十进制数标示双精度浮点数任意双精度二进制浮点数的精确十进制等效项通常看起来很笨，如下所示：
0.1000000000000000055511151231257827021181583404541015625
通常，打印浮点数时，不希望看到其所有数字。无论如何，它们中的大多数都是“不关心的信息” 。但是，你需要几位数？想要一个短字符串，但是你希望它足够长，以便它标识原始浮点数。计算机科学的一个众所周知的结果是，需要17位有效的十进制数字来标识任意双精度浮点数。如果要将任何浮点数的精确十进制值四舍五入为17个有效数字，则将有一个数字，当转换回浮点数时，该数字将为您提供原始的浮点数。也就是说，这个数字是往返可逆的。这里的示例数字为0.10000000000000001 。
但是17位数字是最坏的情况，这意味着在许多情况下，更少的数字（甚至少至一位）就可以工作。所需的数字取决于特定的浮点数。在我们的示例中，短字符串0.1可以解决问题。这意味着至少就其浮点表示而言， 0.1000000000000000055511151231257827021181583404541015625和0.10000000000000001和0.1相同。
以下，举例说明可以和不能缩短的十进制字符串的示例
示例1：只需要一个数字让我们仔细看一下0.1的例子。此双精度浮点数线图说明了其工作原理：
文章插图
示例：最短的十进制字符串为1位数字
蓝色是三个浮点数的精确十进制值：中间的一个是示例数，左边的一个是在其前面的浮点数，而右边的一个是在其后的浮点数。用灰色标记了示例编号与其邻居之间的中点。这些中点之间的任何值都将四舍五入为示例数字。从中可以看出，尽管0.10000000000000001更近，但0.1仍在舍入范围内；因此，从最短的观点出发，优选0.1 。
示例2：17位数字是必需的浮点数50388143.0682372152805328369140625不能四舍五入为小于17位的数字，并且仍然是双向的。四舍五入为17位数字，即50388143.068237215 ，它将转换回浮点数。舍入到16位数字是50388143.06823722 ，但是它更接近下一个浮点数：
文章插图
示例：最短的十进制字符串为17位
不存在较短的字符串，因为四舍五入到较短的长度只会引入更多的误差。
示例3：仅需要10位数字浮点数54167628.179999999701976776123046875可以四舍五入到10位数字，但不少于10位。四舍五入到10位数字为54167628.18 。四舍五入为9位数字，它是54167628.2 ，往返距离中间相隔着2,684,354个二进制浮点数。