c - 如何打印 float 的精确值？

Question

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

也就是说，每个可能的浮点值都恰好对应于一个二元有理数(一个有理数 p/q，其中 q 是 2 的幂)，这反过来具有精确的十进制表示。

我的问题是:如何有效地找到这个精确的十进制表示形式？ sprintf 等函数通常只指定最多有效数字的个数来唯一确定原始浮点值；他们不一定打印出精确的十进制表示。我知道我使用过的一种算法，但它非常慢，O(e^2) 其中 e 是指数。这是一个大纲:

1. 将尾数转换为十进制整数。您可以通过将位分开以直接读取尾数来执行此操作，或者您可以编写一个困惑的浮点循环，首先将值乘以 2 的幂以将其置于 1<=x<10 范围内，然后拉动通过转换为 int、减去并乘以 10，一次去除一个数字。
2. 通过重复乘以或除以 2 来应用指数。这是对您生成的十进制数字的字符串 的运算。每 ~3 次乘法都会在左边添加一个额外的数字。每除一次都会在右边增加一个额外的数字。

这真的是最好的吗？我对此表示怀疑，但我不是浮点专家，而且我找不到一种方法来对数字的浮点表示进行以 10 为底的计算，而不会遇到不精确结果的可能性(乘以或除以除了 2 的幂之外，任何东西都是 float 的有损运算，除非你知道你有可用的位。

Answer 1

这个问题有官僚部分和算法部分。 float 在内部存储为 (2^e × m)，其中 e 是指数(本身二进制)，m 是尾数。问题的官僚部分是如何访问这些数据，但 R. 似乎对问题的算法部分更感兴趣，即转换 (2^e × m) 到小数形式的分数 (a/b)。几种语言的官僚问题的答案是 frexp(这是一个有趣的细节，我今天之前不知道)。

的确，乍一看，只需要 O(e²) 的工作量就可以写出 2 ^e 十进制，尾数还有更多时间。但是，多亏了 Schönhage–Strassen 的魔力快速乘法算法，您可以在 Õ(e) 时间内完成，波浪号表示“最多对数因子”。如果您将 Schönhage–Strassen 视为魔法，那么想做什么就不难了。如果 e 是偶数，您可以递归计算 2^e/2，然后使用快速乘法对其求平方。另一方面，如果 e 是奇数，您可以递归计算 2^e−1 然后将其加倍。您必须小心检查在 base 10 中是否有 Schönhage–Strassen 的版本。虽然它没有被广泛记录，但它可以在任何 base 中完成。

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

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

如果问题是关于标准的 64 位 float ，那么它对于花哨的 Schönhage–Strassen 算法来说太小了。在此范围内，您可以使用各种技巧来节省工作。一种方法是将 2^e 的所有 2048 个值存储在查找表中，然后使用非对称乘法(在长乘法和短乘法之间)处理尾数。另一个技巧是以 10000 为基数(或 10 的更高次幂，取决于架构)而不是以 10 为基数。但是，正如 R. 在评论中指出的那样，128 位 float 已经允许足够大的指数调用查询查找表和标准长乘法。实际上，长乘法是最快的几位数字，然后在相当大的中间范围内可以使用 Karatsuba multiplication或 Toom–Cook multiplication ，然后是 Schönhage–Strassen 的变体不仅在理论上而且在实践中都是最好的。

其实就是大整数包GMP已经有了 Õ(N) 次基数转换，以及选择乘法算法的良好启发式方法。他们的解决方案和我的唯一区别在于，他们不是在以 10 为基数的情况下进行任何大的算术运算，而是在以 2 为基数的情况下计算 10 的大次方。在这个解决方案中，他们还需要快速除法，但这可以通过任何快速乘法获得几种方式。