你如何打印浮点数的精确值? [英] 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.

这真的是最好的吗?我对此表示怀疑，但我不是浮点专家，我找不到一种方法来对数字的浮点表示进行以 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).几种语言的官僚问题的答案是 freexp(这是我今天之前不知道的一个有趣的细节).

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(e²)的工作^e 十进制，还有更多时间用于尾数.但是，感谢 Schönhage–Strassen 快速乘法算法，您可以在 Õ(e) 时间内完成，其中波浪号表示最多对数因子".如果您将 Schönhage-Strassen 视为魔术，那么不难想到该怎么做.如果 e 是偶数，则可以递归计算 2^e/2，然后使用快速乘法对其进行平方.另一方面，如果 e 是奇数，您可以递归计算 2^e−1 然后将其加倍.您必须仔细检查是否存在 Base 10 中的 Schönhage–Strassen 版本.虽然它没有被广泛记录，但可以在任何基础中完成.

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.

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