如何打印浮点数的 EXACT 值? [英] How do you print the EXACT value of a floating point number?

问题描述

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

First of all, this is not a floating point newbie question. I know results of floating point arithmetic (not to mention transcendental functions) usually cannot be represented exactly, and that most terminating decimals cannot be represented exactly as binary floating point numbers.

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

That said, each possible floating point value corresponds exactly to a diadic rational (a rational number p/q where q is a power of 2), which in turn has an exact decimal representation.

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

My question is: How do you find this exact decimal representation efficiently? sprintf and similar functions are usually only specified up to a number of significant digits to uniquely determine the original floating point value; they don't necessarily print the exact decimal representation. I know one algorithm I've used, but it's very slow, O(e^2) where e is the exponent. Here's an outline:

1. 将尾数转换为十进制整数.您可以通过拉开位直接读取尾数来做到这一点，或者您可以编写一个凌乱的浮点循环，首先将值乘以 2 的幂以将其置于范围 1<=x<10，然后拉通过强制转换为 int、减法和乘以 10，一次去掉一个数字.
2. 通过重复乘以或除以 2 来应用指数.这是对您生成的十进制数字的字符串 的运算.每约 3 次乘法都会在左侧添加一个额外的数字.每一格都会在右边多加一个数字.

1. Convert the mantissa to a decimal integer. You can either do this by pulling apart the bits to read the mantissa directly, or you can write a messy floating point loop that first multiplies the value by a power of two to put it in the range 1<=x<10, then pulls off a digit at a time by casting to int, subtracting, and multiplying by 10.
2. Apply the exponent by repeatedly multiplying or dividing by 2. This is an operation on the string of decimal digits you generated. Every ~3 multiplications will add an extra digit to the left. Every single dividion will add an extra digit to the right.

这真的是最好的吗?我对此表示怀疑，但我不是浮点专家，我无法找到一种方法来对数字的浮点表示进行 base-10 计算，而不会遇到不精确结果的可能性(乘以或除以除了 2 的幂之外的任何操作都是浮点数的有损运算，除非您知道您有空闲位可以使用).

Is this really the best possible? I doubt it, but I'm not a floating-point expert and I can't find a way to do the base-10 computations on the floating point representation of the number without running into a possibility of inexact results (multiplying or dividing by anything but a power of 2 is a lossy operation on floating point numbers unless you know you have free bits to work with).

推荐答案

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

This question has a bureaucratic part and an algorithmic part. A floating point number is stored internally as (2^e × m), where e is an exponent (itself in binary) and m is a mantissa. The bureaucratic part of the question is how to access this data, but R. seems more interested in the algorithmic part of the question, namely, converting (2^e × m) to a fraction (a/b) in decimal form. The answer to the bureaucratic question in several languages is frexp (which is an interesting detail that I didn’t know before today).

确实，乍一看，写2^{需要O(e2)工作e} 十进制，还有更多时间用于尾数.但是，感谢 Schönhage–Strassen 快速乘法算法，您可以在 Õ(e) 时间内完成，其中波浪号表示最多对数因子".如果您将 Schönhage-Strassen 视为魔术，那么想出该怎么做并不难.如果 e 是偶数，则可以递归计算 2^e/2，然后使用快速乘法对其进行平方.另一方面，如果 e 是奇数，您可以递归计算 2^e−1 然后将其翻倍.您必须小心地检查 base 10 中是否存在 Schönhage–Strassen 版本.虽然没有广泛记录，但可以在任何 base 中完成.

It is true that at first glance, it takes O(e²) work just to write 2^e in decimal, and more time still for the mantissa. But, thanks to the magic of the Schönhage–Strassen fast multiplication algorithm, you can do it in Õ(e) time, where the tilde means "up to log factors". If you view Schönhage–Strassen as magic, then it’s not that hard to think of what to do. If e is even, you can recursively compute 2^e/2, and then square it using fast multiplication. On the other hand if e is odd, you can recursively compute 2^e−1 and then double it. You have to be careful to check that there is a version of Schönhage–Strassen in base 10. Although it is not widely documented, it can be done in any base.

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

Converting a very long mantissa from binary to base 10 is not exactly the same question, but it has a similar answer. You can divide the mantissa into two halves, m = a × 2^k + b. Then recursively convert a and b to base 10, convert 2^k to base 10, and do another fast multiplication to compute m in base 10.

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

The abstract result behind all of this is that you can convert integers from one base to another in Õ(N) time.

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

If the question is about standard 64-bit floating point numbers, then it’s too small for the fancy Schönhage–Strassen algorithm. In this range you can instead save work with various tricks. One approach is to store all 2048 values of 2^e in a lookup table, and then work in the mantissa with asymmetric multiplication (in between long multiplication and short multiplication). Another trick is to work in base 10000 (or a higher power of 10, depending on architecture) instead of base 10. But, as R. points out in the comments, 128-bit floating point numbers already allow large enough exponents to call into question both lookup tables and standard long multiplication. As a practical matter, long multiplication is the fastest up to a handful of digits, then in a significant medium range one can use Karatsuba multiplication or Toom–Cook multiplication, and then after that a variation of Schönhage–Strassen is best not just in theory but also in practice.

实际上，大整数包GMP已经有Õ(N)-时间基数转换，以及选择乘法算法的良好启发式.他们的解决方案和我的解决方案之间的唯一区别是，他们不是在以 10 为基数进行任何大的算术运算，而是在以 2 为基数计算 10 的大幂.在这个解决方案中，他们还需要快速除法，但这可以从任何情况下的快速乘法中获得多种方式.

Actually, the big integer package GMP already has Õ(N)-time radix conversion, as well as good heuristics for which choice of multiplication algorithm. The only difference between their solution and mine is that instead of doing any big arithmetic in base 10, they compute large powers of 10 in base 2. In this solution, they also need fast division, but that can be obtained from fast multiplication in any of several ways.

这篇关于如何打印浮点数的 EXACT 值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！