Squeak中log2无guard实现整数幂判断的可行性问询

问题核心 #

我们需要找到或构造一对非2的幂的正整数i和正整数p，使得在Squeak trunk基于IEEE754双精度实现的log2函数下，满足以下两个不等式之一：

1. (i raisedTo: p) highBit / i log2 < p
2. ((i raisedTo: p) highBit - 1) / i log2 > p

这一问题的背景是优化Squeak中判断整数是否为完美幂的代码——当前实现使用guard逻辑提前终止循环，现在希望移除guard改用<=操作，需要验证是否存在反例会导致逻辑错误或性能问题。

关键概念与推导 #

首先明确几个核心计算的含义：

• 对于整数x = i^p，其highBit值为二进制位数，精确值为floor(p * log2(i)) + 1（记为H）
• i log2是Squeak基于IEEE754双精度的近似值（记为L），与真实值log2(i)的误差满足|L - log2(i)| ≤ ε，其中ε为双精度机器epsilon（约2^-53 ≈ 1e-16）

将两个不等式转化为误差相关的形式：

不等式1：H/L < p #

代入H = floor(p*log2(i)) + 1 = p*log2(i) - frac + 1（frac为p*log2(i)的小数部分，0 ≤ frac < 1），以及L = log2(i) + δ（|δ| ≤ ε），不等式可化简为：

1 - frac < p*δ

当δ > 0（即log2近似值略大于真实值），且p足够大时，p*δ会超过1-frac（例如δ=ε，p > (1-frac)/ε ≈ 1e15），此时不等式成立。

不等式2：(H-1)/L > p #

同理代入化简后得到：

p*δ < -frac

当δ < 0（近似值略小于真实值），且p足够大时，p*δ的绝对值会超过frac，不等式成立。

构造反例 #

以i=3为例（非2的幂，log2(3)为无理数）：

• 双精度下log2(3)的近似值L ≈ 1.5849625007211561，与真实值的误差δ ≈ 1e-16 > 0
• 取p=9e15，此时p*δ=0.9，根据Weyl均匀分布定理，必然存在这样的p使得p*log2(3)的小数部分frac=0.1，则1-frac=0.9 = p*δ，此时H/L = p；若取p=9e15+1，则p*δ=0.9+1e-16 > 0.9，满足1-frac < p*δ，此时：

  H = floor((9e15+1)*log2(3)) + 1
  H/L ≈ (9e15+1) - 1e-16/1.58 < 9e15+1 = p
  

  即满足第一个不等式。

实际代码影响 #

在完美幂判断的原有实现中：

isPerfectPower
    self <= 1 ifTrue: [^false].
    | highBit log2i p candidate |
    highBit := self highBit.
    log2i := self log2.
    2 to: highBit do: [:eachP |
        p := eachP.
        candidate := self nthRoot: p.
        candidate raisedTo: p = self ifTrue: [^true].
        (highBit / log2i < p or: [(highBit - 1) / log2i > p]) ifTrue: [^false]].
    ^false

guard的作用是提前终止无意义的循环——当p极大时，i^p的highBit与p*log2i的关系会触发guard，避免循环遍历到天文数字级的p。

如果移除guard改用<=操作：

isPerfectPower
    self <= 1 ifTrue: [^false].
    | highBit log2i p candidate |
    highBit := self highBit.
    log2i := self log2.
    2 to: highBit do: [:eachP |
        p := eachP.
        (highBit <= p * log2i) ifFalse: [^false].
        candidate := self nthRoot: p.
        candidate raisedTo: p = self ifTrue: [^true]].
    ^false

对于上述构造的大p反例，highBit <= p*log2i会成立，循环会继续执行到p=highBit，这在实际中会导致程序长时间无响应甚至卡死。

结论 #

• 理论上可以构造出满足条件的(i,p)，但均为p极大的极端情况；
• 实际代码中，移除guard会导致极端场景下的性能问题，因此不建议移除原有guard逻辑。

内容的提问来源于stack exchange，提问作者aka.nice