浮点数计算ceil(integer log2)的失效场景及最小失效正整数

问题描述 #

给出两个实现以2为底整数对数向上取整的Python函数：

from math import *

def ilog2_ceil_alt(i: int) -> int:
    # 存在错误的实现
    return ceil(log2(i))

def ilog2_ceil(i: int) -> int:
    # 正确的实现
    if i <= 0:
        raise ValueError("math domain error")
    return (i-1).bit_length()

其中ilog2_ceil_alt依赖浮点数运算，理论上会因64位double的有限精度出现舍入错误，但测试大量数值（包括2**32、2**64 + 9999等）后未发现失效，因此需要明确：

1. 浮点数实现ceil(log2(i))何时会失效？
2. 导致错误函数失效的最小正整数输入是什么？

解答 #

失效本质原因 #

64位double类型的尾数只有53位，这意味着它只能精确表示小于等于2^53的所有整数。当整数i超过2^53后，相邻整数会被映射到同一个double值（即无法精确存储）。

对于ilog2_ceil_alt来说，当i被舍入后的double值对应的log2结果，其向上取整值与真实的ilog2_ceil(i)不符时，函数就会失效：比如某个数实际是2^k +1，但被舍入成2^k，此时log2计算结果为k，ceil(k)得到k，但正确结果应该是k+1。

最小失效正整数 #

导致ilog2_ceil_alt失效的最小正整数是2^53 + 1，验证如下：

• 正确函数结果：ilog2_ceil(2**53 + 1) = (2**53).bit_length() = 54（因为2^53的二进制是1后面跟53个0，bit_length为54）
• 错误函数结果：2^53 +1无法被double精确表示，会被舍入为2^53，因此log2(2**53 +1)实际计算的是log2(2^53)=53，ceil(53)=53，与正确结果54不符。

而所有小于等于2^53的整数都能被double精确存储，log2计算结果准确，因此ilog2_ceil_alt在这些数值上都能得到正确结果。

其他失效场景 #

所有大于2^53且无法被double精确表示的整数，只要满足“舍入后的double值的log2向上取整结果与真实值不符”，都会触发失效。比如2^53 +3、2^53 +5等（因为超过2^53后，double的存储间隔变为2，奇数无法被精确表示）。

内容的提问来源于stack exchange，提问作者JamesTheAwesomeDude