双精度十进制表示中连续的零数 [英] Number of consecutive zeros in the decimal representation of a double

问题描述

在IEEE 754双精度数字的精确十进制表示中，连续的非前导非尾随零（或9）的最大数目是多少？

Context

考虑将 double 转换为十进制的问题，将其舍入（倒数）只有原始的，你能够使用的是一个现有的功能，转换为最近的（正确四舍五入任何所需的位数）。

你可以得到一些额外的数字和删除他们自己。例如，要将> 1.875 向下舍入到点之后的一个数字，可以将其转换为最近的十进制表示形式，在点之后有两个或三个数字（ 1.87 或 1.875 ），然后自行清除数字以获得预期的答案， 1.8

对于一些数字和可选择的附加数字来打印，这种方法会产生错误的结果。例如，对于最接近 0.799999996 的 double ，转换为十进制，舍入到最接近的2，3或点后4位数产生 0.80 ， 0.800 和 0.8000 。当转换结果为 0.7 。

$时，擦除转换后的附加数字会产生结果 0.8 b
$ b double 的数量是有限的，在初始转换中按顺序存在足够多的数字总是在截取得到的十进制表示之后计算正确的结果。这个数字与在一个 double 的精确十进制表示中可能出现的最大九或零点数有关。

< h2>相关

这个问题涉及到这个关于将 double 转换为十进制的问题，并且是这个问题关于正确的四舍五入十进制表示转换为双打。

解决方案

[短版：答案是20.重新找到问题的方式找到良好的理性近似形式的数字 2 ^ e / 10 ^ d ;然后使用连续分数来找到每个合适的 d 和 e 的最佳近似值。]

答案似乎是 20 ：也就是说，有一些IEEE 754 binary64浮点数的例子，其十进制数的展开式为 20 连续的零，但在它们的十进制扩展（不包括前导零和尾随零）中没有 21 连续的零。对于九弦字符串也是如此。

对于第一部分，我需要做的就是展示这样一个浮点数。 0x1.9527560bfbed8p-1000 的值可以精确地表示为binary64浮点数，而其十进制扩展包含一个20个零的字符串：

1.-301

对于有关九个问题的部分，的nsion 0x1.c23142c9da581p-405 包含20九的字符串：

2.12818792307269553358078502102171540639252016258831784842556110831434197718043638405555406495645619729155240037555858106390933161420388023706431461384056688295540725831155392678607931808851292893574214797681879999999999999999999941026584542575391157788777223962620780080784703190447744595561259568772261019375946489162743091583251953125E-122

为了解释我如何找到上面的数字，并且显示没有连续21个零的例子，我们需要更加努力。对于一些整数 a，一个具有9或0的长字符串的小数展开式的实数具有（a + eps）* 10 ^ d 和 d 和实数 eps ，其中 a 非零（我们不妨假定 a 正数）和 eps 非零和小数。例如，如果 0 < abs（eps） 10 ^ -10 然后 a + eps 在小数点后至少有10个零（如果 eps 是正值），或小数点后10位（如果 eps 为负值）。乘以 10 ^ d 可以改变零或九个字符串的位置。



对上述表单的数字感兴趣，可以同时表示为IEEE 754 binary64浮点数;换句话说，对于整数 b 和<$ c $也是形式为 b * 2 ^ e 的数字使用 e 2 ^ 52 <= b <= 2 ^ 53 $ c>范围有限（一旦我们进入低于正常范围，对 b 有一些额外的限制，但我们可以在后面担心）。
$ b

因此，结合这个，我们正在寻找解决方案（a + eps）* 10 ^ d = b * 2 ^ e 整数 a ， b ， d 和 e 使得 eps 很小， a 是正数， > 2 ^ 52 <= b <= 2 ^ 53 （我们将担心 d 和 e 稍后）。重新排列，我们得到 eps / b = 2 ^ e / 10 ^ d - a / b 。换句话说，我们正在寻找有理分式的近似值，分母的分母是 2 ^ e / 10 ^ d 。这是连续分数的经典应用：给定 d 和 e ，可以高效地找到分母有界的最佳有理逼近通过 2 ^ 53 。

所以一般的解决方案是：
$对于每个适当的d和e：
，b $ b

 找到分母≤2 ^ 53的最佳有理逼近a / b到2 ^ e / 10 ^ d 
 if（在这个有理逼近中的误差足够小）：
＃我们有一个候选
检查b * 2 ^ e 
  

我们只有大约2000个e值来检查，最坏的情况是每个这样的e有几百d，所以整个事情是计算上是非常可行的。

现在细节：够小是什么意思？哪个 d 和 e 是适当的？

至于足够小：假设我们正在寻找至少19个零或9个字符串，所以我们正在寻找解决方案，其中 0 < abs（eps）<= 10 ^ -19 。因此，对于每个 d 和 e ，所有 a 和 b 使得 abs（2 ^ e / 10 ^ d -a / b）<= 10 ^ -19 * 2 ^ -52 。请注意，由于 b 的限制，只能有一个这样的分数 a / b ;如果存在另一个这样的 a'/ b'那么我们具有 1/2 ^ 106 <= 1 /（b * b'）< = abs（a / b - a'/ b'）<= 2 * 10 ^ -19 * 2 ^ -52 ，这是一个矛盾。因此，如果存在这样的分数，它必然是给定分母界限的最佳有理逼近。
$ b 对于 d 和 e ：为了覆盖二进制64范围，包括子正常，我们希望 e 范围从 -1126 到 971 （含）。如果 d 太大，那么 2 ^ e / 10 ^ d 会比 2 ^ -53 并没有解决方案的希望; d <= 16 + floor（e * log10（2））是一个实际的界限。如果 d 太小（或太负），那么 2 ^ e / 10 ^ d 将是一个整数，没有解决方案;为了避免这种情况，我们需要 d> min（e，0）。

有了这些，我们来编写一些代码。 Python解决方案非常简单，部分归功于 Fraction.limit_deminator 方法，它完全可以在限定范围内找到最合理的近似值。

pre $ code > from fractions进口分数
从itertools进口groupby
从数学进口楼log10
$ b $ def longest_run（s，c）：
长度最长运行给定字符c在字符串s中。
runs = [list（g）for v，g in groupby（s，lambda k：k == c）if v]
return max（len（run（run）run in runs）if else else 0

def nearest_fraction（d，e）：
最接近2 ** e / 10 ** d分母最多2 ** 53。
f =分数（2 ** max（ed，0）* 5 ** max（-d，0），2 ** max（0，de）* 5 ** max（0，d））
approx = f.limit_denominator（2 ** 53）
return approx.numera （emin，emax + 1）：$约束分母

= set（）
emin = -1126
emax = 971
对于范围（dmin，dmax + 1）中的d，b $ b dmin = min（e，0）+ 1
dmax = int（floor（e * log10（2）））+ 16
：
num，den = nearest_fraction（d，e）
x = float.fromhex（'0x {：x} p {}'。格式（den，e））
＃避免重复。
如果看到x：
continue
seen.add（x）
digits ='{：.1000e}'。format（x）.split（'e'）[ 0] .replace（'。'，''）。strip（'0'）
zero_run = longest_run（digits，'0'）
如果zero_run> = 20：
print {} .x（十六进制），zero_run）
nine_run = longest_run（数字，'9'）
如果nine_run> = 20：
打印{}在其扩展中有9.format（x.hex（），nine_run）


<使用Python的分数模块将会是一个很好的开始:-);就目前而言，需要几分钟时间才能完成。结果如下：

pre $ 0x1.9527560bfbed8p-1000在其扩展中有20个零
0x1.fa712b8efae8ep-997在其扩展中具有20个零
0x1.515476ae79b24p-931在其扩展中具有20个9个
0x1.a5a9945a181edp-928在其扩展中具有20个9个
0x1.86049d3311305p-909其中具有20个零扩展
0x1.69c08f3dd8742p-883在其扩展中具有20个零
0x1.1b41d80091820p-861在其扩展中具有20个零
0x1.62124e00b5e28p-858在其扩展中具有20个零
0x1.ba96e180e35b2p-855在其扩展中具有20个零
0x1.31c5be6377c48p-786在其扩展中具有20个零
0x1.7e372dfc55b5ap-783在其扩展中具有20个零
0x1.7e89dc1c3860ap-555在其扩展中有20个9个
0x1.7e89dc1c3860ap-554在其扩展中有20个9个
0x1.7e89dc1c3860ap-553在其扩展中有20个9个
0x1.7e89dc1c3860ap-552在其中有20个9个扩展
0x1.30bd91ea994cbp-548在其扩展中有20个零
0x1.4a5f9de9ee064p -468在其扩展中有20个9个
0x1.9cf785646987dp-465在其扩展中有20个9个
0x1.c23142c9da581p-408在其扩展中有20个9个
0x1.c23142c9da581p-407有20个9个在其扩展中
0x1.c23142c9da581p-406在其扩展中有20个9
0x1.c23142c9da581p-405在其扩展中有20个9个
0x1.ba431f4e34be9p + 738在其扩展$ 20中有20个9个$ b

What is the maximum number of consecutive non-leading non-trailing zeros (resp. nines) in the exact decimal representation of an IEEE 754 double-precision number?

Context

Consider the problem of converting a double to decimal, rounding up (resp. down), when the only primitive you are able to use is an existing function that converts to the nearest (correctly rounded to any desired number of digits).

You could get a few additional digits and remove them yourself. For instance, to round 1.875 down to one digit after the dot, you could convert it to the nearest decimal representation with two or three digits after the dot (1.87 or 1.875) and then erase the digits yourself in order to obtain the expected answer, 1.8.

For some numbers and choices of an additional number of digits to print, this method produces the wrong result. For instance, for the double nearest to 0.799999996, converting to decimal, rounding to the nearest, to 2, 3 or 4 digits after the dot produces 0.80, 0.800 and 0.8000. Erasing the additional digits after the conversion produces the result 0.8, when the desired result was 0.7.

There being a finite number of double, there exists a number of additional digits that it is enough to print in the initial conversion in order to always compute the correct result after truncation of the obtained decimal representation. This number is related to the maximal number of nines or zeros that can occur in the exact decimal representation of a double.

Related

This question is related to this question about rounding down in the conversion of a double to decimal, and is dual of this question about the correctly rounded conversion of decimal representations to doubles.

解决方案

[Short version: The answer is 20. Recast the problem in terms of finding good rational approximations to numbers of the form 2^e / 10^d; then use continued fractions to find the best such approximation for each suitable d and e.]

The answer appears to be 20: that is, there are examples of IEEE 754 binary64 floats whose decimal expansion has 20 consecutive zeros, but there are none with 21 consecutive zeros in their decimal expansion (excluding leading and trailing zeros). The same is true for strings of nines.

For the first part, all I need to do is exhibit such a float. The value 0x1.9527560bfbed8p-1000 is exactly representable as a binary64 float, and its decimal expansion contains a string of 20 zeros:

1.4770123739081015758322326613397693800319378788862225686396638475789157389044026850930817635789180868803699741668118826590044503912865915000931065333265410967343958956370955236330760696646247901278074331738806828003156818618589682432778455224012594723731303304343292224317331720902511661748324604219378419442700000000000000000000740694966568985212687104794747958616712153948337746429554804241586090095019654323133732729258896166004754316995632195371041441104566613036026346868128222593894931067078171989365490315525401375255259854894072456336393577718955037826961967325532389800834191597056333066925969522850884268136311674777047673845172073566950098844307658716553833345849153012040436628485227928616281881622762650607683099224232137203216552734375E-301

For the part of the question about nines, the decimal expansion of 0x1.c23142c9da581p-405 contains a string of 20 nines:

2.12818792307269553358078502102171540639252016258831784842556110831434197718043638405555406495645619729155240037555858106390933161420388023706431461384056688295540725831155392678607931808851292893574214797681879999999999999999999941026584542575391157788777223962620780080784703190447744595561259568772261019375946489162743091583251953125E-122

To explain how I found the numbers above, and to show that there are no examples with 21 consecutive zeros, we'll need to work a bit harder. A real number with a long string of 9s or 0s in its decimal expansion has the form (a + eps)*10^d for some integers a and d and real number eps, with a nonzero (we might as well assume a positive) and eps nonzero and small. For example, if 0 < abs(eps) < 10^-10 then a + eps has at least 10 zeros following the decimal point (if eps is positive), or 10 nines following the decimal point (if eps is negative); multiplying by 10^d allows for shifting the location of the string of zeros or nines.

But we're interested in numbers of the above form that are simultaneously representable as an IEEE 754 binary64 float; in other words, numbers that are also of the form b*2^e for integers b and e satisfying 2^52 <= b <= 2^53, with e limited in range (and with some additional restrictions on b once we get into the subnormal range, but we can worry about that later).

So combining this, we're looking for solutions to (a + eps) * 10^d = b * 2^e in integers a, b, d and e such that eps is small, a is positive and 2^52 <= b <= 2^53 (and we'll worry about ranges for d and e later). Rearranging, we get eps / b = 2^e / 10^d - a / b. In other words, we're looking for good rational approximations to 2^e / 10^d, with limited denominator. That's a classic application of continued fractions: given d and e, one can efficiently find the best rational approximation with denominator bounded by 2^53.

So the solution strategy in general is:

for each appropriate d and e:
    find the best rational approximation a / b to 2^e / 10^d with denominator <= 2^53
    if (the error in this rational approximation is small enough):
        # we've got a candidate
        examine the decimal expansion of b*2^e

We have only around 2 thousand values for e to check, and at worst a few hundred d for each such e, so the whole thing is computationally very feasible.

Now to details: what does "small enough" mean? Which d and e are "appropriate"?

As to "small enough": let's say that we're looking for strings of at least 19 zeros or nines, so we're looking for solutions with 0 < abs(eps) <= 10^-19. So it's enough to find, for each d and e, all a and b such that abs(2^e / 10^d - a / b) <= 10^-19 * 2^-52. Note that because of the limit on b there can be only one such fraction a / b; if there were another such a' / b' then we have 1 / 2^106 <= 1 / (b *b') <= abs(a / b - a' / b') <= 2 * 10^-19 * 2^-52, a contradiction. So if such a fraction exists it's necessarily the best rational approximation with the given denominator bound.

For d and e: to cover the binary64 range including subnormals, we want e to range from -1126 to 971 inclusive. If d is too large then 2^e / 10^d will be much smaller than 2^-53 and there's no hope of a solution; d <= 16 + floor(e*log10(2)) is a practical bound. If d is too small (or too negative) then 2^e / 10^d will be an integer and there's no solution; to avoid that, we want d > min(e, 0).

With all that covered, let's write some code. The Python solution is pretty straightforward, thanks in part to the existence of the Fraction.limit_deminator method, which does exactly the job of finding the best rational approximation within limits.

from fractions import Fraction
from itertools import groupby
from math import floor, log10

def longest_run(s, c):
    """Length of the longest run of a given character c in the string s."""
    runs = [list(g) for v, g in groupby(s, lambda k: k == c) if v]
    return max(len(run) for run in runs) if runs else 0

def closest_fraction(d, e):
    """Closest rational to 2**e/10**d with denominator at most 2**53."""
    f = Fraction(2**max(e-d, 0) * 5**max(-d, 0), 2**max(0, d-e) * 5**max(0, d))
    approx = f.limit_denominator(2**53)
    return approx.numerator, approx.denominator

seen = set()
emin = -1126
emax = 971
for e in range(emin, emax+1):
    dmin = min(e, 0) + 1
    dmax = int(floor(e*log10(2))) + 16
    for d in range(dmin, dmax+1):
        num, den = closest_fraction(d, e)
        x = float.fromhex('0x{:x}p{}'.format(den, e))
        # Avoid duplicates.
        if x in seen:
            continue
        seen.add(x)
        digits = '{:.1000e}'.format(x).split('e')[0].replace('.','').strip('0')
        zero_run = longest_run(digits, '0')
        if zero_run >= 20:
            print "{} has {} zeros in its expansion".format(x.hex(), zero_run)
        nine_run = longest_run(digits, '9')
        if nine_run >= 20:
            print "{} has {} nines in its expansion".format(x.hex(), nine_run)

There's plenty of scope for performance improvements there (not using Python's fractions module would be a good start :-); as it stands, it takes a few minutes to run to completion. And here are the results:

0x1.9527560bfbed8p-1000 has 20 zeros in its expansion
0x1.fa712b8efae8ep-997 has 20 zeros in its expansion
0x1.515476ae79b24p-931 has 20 nines in its expansion
0x1.a5a9945a181edp-928 has 20 nines in its expansion
0x1.86049d3311305p-909 has 20 zeros in its expansion
0x1.69c08f3dd8742p-883 has 20 zeros in its expansion
0x1.1b41d80091820p-861 has 20 zeros in its expansion
0x1.62124e00b5e28p-858 has 20 zeros in its expansion
0x1.ba96e180e35b2p-855 has 20 zeros in its expansion
0x1.31c5be6377c48p-786 has 20 zeros in its expansion
0x1.7e372dfc55b5ap-783 has 20 zeros in its expansion
0x1.7e89dc1c3860ap-555 has 20 nines in its expansion
0x1.7e89dc1c3860ap-554 has 20 nines in its expansion
0x1.7e89dc1c3860ap-553 has 20 nines in its expansion
0x1.7e89dc1c3860ap-552 has 20 nines in its expansion
0x1.30bd91ea994cbp-548 has 20 zeros in its expansion
0x1.4a5f9de9ee064p-468 has 20 nines in its expansion
0x1.9cf785646987dp-465 has 20 nines in its expansion
0x1.c23142c9da581p-408 has 20 nines in its expansion
0x1.c23142c9da581p-407 has 20 nines in its expansion
0x1.c23142c9da581p-406 has 20 nines in its expansion
0x1.c23142c9da581p-405 has 20 nines in its expansion
0x1.ba431f4e34be9p+738 has 20 nines in its expansion

这篇关于双精度十进制表示中连续的零数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！