double的十进制表示中的连续零的数量

[简短版本:答案是20.重新解决问题,找到对形式数字的良好理性近似2^e / 10^d; 然后使用续流分查找每个合适的最好这样近似d和e.]

答案似乎是20:即,有一些IEEE 754 binary64浮点数的例子,其十进制扩展具有20连续的零,但21在它们的十进制扩展中没有连续的零(不包括前导零和尾随零).对于九个字符串也是如此.

对于第一部分,我需要做的就是展示这样的浮动.该值0x1.9527560bfbed8p-1000可以完全表示为binary64 float,其十进制扩展包含20个零的字符串:

1.-301

对于关于9的问题的部分,十进制扩展0x1.c23142c9da581p-405包含20个9的字符串:

2.12818792307269553358078502102171540639252016258831784842556110831434197718043638405555406495645619729155240037555858106390933161420388023706431461384056688295540725831155392678607931808851292893574214797681879999999999999999999941026584542575391157788777223962620780080784703190447744595561259568772261019375946489162743091583251953125E-122

为了解释我如何找到上面的数字,并表明没有21个连续零的例子,我们需要更努力地工作.与787-9或0,在其十进制扩展长长的一串实数的形式(a + eps)*10^d对一些整数a和d和实数eps,具有a非零(我们不妨假设a正)和eps非零和小.例如,如果0 < abs(eps) < 10^-10然后a + eps具有至少10个零的小数点以下的(如果eps是正的),或跟随在小数点10九(如果eps是负的); 乘以10^d允许移动零或九的串的位置.

但我们对上述形式的数字感兴趣,它们同时可以表示为IEEE 754 binary64 float; 换句话说,这也是形式的数字b*2^e为整数b和e满足2^52 <= b <= 2^53,用e有限的范围内(并与一些额外的限制,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.

所以解决方案策略一般是:

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

对于e来说,我们只有大约2千个值来检查,最坏的是每个这样的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了矛盾.因此,如果存在这样的分数,则必然是给定分母界限的最佳有理逼近.

对于d和e:要覆盖包括次正规的binary64范围,我们希望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方法的存在,它完全可以在极限范围内找到最佳有理逼近.

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)

那里有足够的性能改进空间(不使用Python的fractions模块将是一个良好的开端:-); 就目前而言,需要几分钟才能完成.以下是结果:

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