可以影响双精度的最大小数位数 [英] Maximum number of decimal digits that can affect a double
问题描述
考虑 d1.d2d3d4d5...dnExxx 形式的十进制表示，其中 xxx 是任意指数，d1 和 dn 都不是零.
Consider decimal representations of the form d1.d2d3d4d5...dnExxx where xxx is an arbitrary exponent and both d1 and dn are nonzero.
是否已知最大 n 使得存在十进制表示 d1.d2d3d4d5...dnExxx 使得区间 (d1.d2d3d4d5...dnExxx, d1.d2d3d4d5...((dn)+1)Exxx)包含一个 IEEE 754 double?
Is the maximum n known such that there exists a decimal representation d1.d2d3d4d5...dnExxx such that the interval (d1.d2d3d4d5...dnExxx, d1.d2d3d4d5...((dn)+1)Exxx) contains an IEEE 754 double?
n 至少应为 17.问题是 17 高多少.
n should be at least 17. The question is how much above 17.
这个数字 n 与在像 strtod() 这样的十进制到双精度转换中足以考虑的位数有关.我查看了 David M. Gay 的实现 的源代码，希望在那里找到答案.有一个对40"的暗示，但不清楚这是一个合理的数学结果的结果，还是只是一个统计上的安全界限.此外，关于截断"的注释听起来像是 0.5000000000000000000000000000000000000000000000000001 在向上取整模式下可能会转换为 0.5.
This number n has something to do with the number of digits that it is enough to consider in a decimal-to-double conversion such as strtod(). I looked at the source code for David M. Gay's implementation hoping to find an answer there. There is an allusion to "40" but it is unclear whether this is a consequence of a sound mathematical result or just a statistically safe bound. Also the comment about "truncating" makes it sound like 0.5000000000000000000000000000000000000000000000000001 may be converted to 0.5 in round-upwards mode.
Musl 的实现 似乎读取了大约 125*9 位数字，即很多.然后切换到粘性"模式:
Musl's implementation seems to read approximately 125*9 digits, which is a lot. Then it switches to "sticky" mode:
if (c!='0') x[KMAX-4] |= 1;
最后，将包含一个 IEEE 754 双精度"替换为包含两个连续 IEEE 754 双精度精度的中点"时，答案有何变化?
Finally, how does the answer change when substituting "contains an IEEE 754 double" with "contains the midpoint of two consecutive IEEE 754 doubles"?
推荐答案
当你有一个奇数位的次正规数，即 2^(-1074) 的奇数倍时，你有一个数字，其十进制表示中的最后一个非零数字是小数点后的第 1074th.然后，小数点后面有大约 300 个零，因此该数字有大约 750-770 个有效十进制数字.最小的正次正规，2^(-1074) 有 751 位有效数字，最大的正次正规，(2^52-1)*2^(-1074)有 767 个有效数字(我认为这是最大值).
When you have a subnormal number with odd significand, that is, an odd multiple of 2^(-1074), you have a number whose last nonzero digit in the decimal representation is the 1074th after the decimal point. You then have around 300 zeros directly following the decimal point, so the number has around 750-770 significant decimal digits. The smallest positive subnormal, 2^(-1074) has 751 significant digits, and the largest positive subnormal, (2^52-1)*2^(-1074) has 767 significant digits (I think that is the maximum).
所以至少有一个十进制数字序列 d1, ..., d766 使得开区间中有一个 IEEE754 double
So there is at least one sequence d1, ..., d766 of decimal digits such that there is an IEEE754 double in the open interval
(d1.d2...d766E-308, d1.d2...(d766 + 1)E-308)
如果我们考虑包含两个连续 IEEE754 doubles 的中点"，答案不会有太大变化，因为次正规的 doubles 都具有大致相同数量的显着性十进制数字，以及两个连续数字的中点.
The answer does not change much if we consider "contains the midpoint of two consecutive IEEE754 doubles", since subnormal doubles have all roughly the same amount of significant decimal digits, and the midpoint of two consecutive such too.
在最坏的情况下，必须消耗整个数字序列(考虑 "0.5000000...0001" 在确定结果应为 0.5 的最后一个 1 之前有任意多个零+ 0.5^53 而不是 0.5 从零或向上舍入时).
In the worst case, the entire digit sequence must be consumed (consider "0.5000000...0001" with arbitrarily many zeros before the final 1 that determines that the result shall be 0.5 + 0.5^53 and not 0.5 when rounding away from zero or up).
但是，只有
floor(DBL_MANT_DIG * log 2 / log 10) + 2 = 17
用于区分不同 double 值的重要十进制数字，因此一种相对简单但可能不是很有效的解析方法是解析第一个(至少 17 个)数字(以及exponent) 到最接近的 double，并将输入字符串与该 double 值(及其邻居)的精确表示进行比较.
significant decimal digits necessary to distinguish between different double values, so a relatively easy, albeit probably not very efficient, method of parsing would be to parse the first (at least 17) digits (and the exponent) to the closest double, and compare the input string with the exact representation of that double value (and its neighbour).
这篇关于可以影响双精度的最大小数位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
