python - 为什么这个算法对于不是 2 的幂的整数会失败？

Question

基于 this answer ，我在 Python 3.x 中实现了一个简单的算法来确定一个整数 n 是否是另一个整数 base 的幂。但是，该算法不会返回正确的结果。链接答案中的代码是:

while (n % 3 == 0) {
    n /= 3;
}
return n == 1;

(A comment 表示检查 n == 0 在逻辑上也是必要的)。这是我的代码:

def is_power(n: int, base: int) -> bool:
    if n == 0:
        return false
    while (n % base == 0):
        n /= base
    return n == 1

我编写了简单的测试代码来测试一定范围的底数和指数，但它返回的结果不正确。测试代码:

for base in range(3, 10):
    print("Base: {0}".format(base))
    for exp in range(30, 40):
        b = is_power(pow(base, exp), base)
        if not(b):
            print("{: <3}: {: <5}".format(exp, str(b)))

我用更大的范围测试了这个，但为了输出，我在这个例子中限制了它。这输出:

Base: 3
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 4
Base: 5
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 6
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 7
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 8
Base: 9
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False

这显然是不正确的。我试过调试一个小例子，其中 n = pow(3, 35) 和 base = 3 在循环:

50031545098999707
1.6677181699666568e+16

循环结束，因为 50031545098999707/3 == 1.667718169966656 9 e+16(注意最后一位不同)。这是问题吗？ Python 的计算失败了吗？如果不是，这个算法有什么问题？

如果我改用 math.pow，算法也会失败得更多，但我并不一定对此感到惊讶，因为检查一个示例表明 pow 和 math.pow 并不总是返回相同的值。

import math
pow(3, 35) == math.pow(3, 35) # 50031545098999707 != 5.0031545098999704e+16

Answer 1

由于您使用的是 Python 3，因此您应该使用

def is_power(n: int, base: int) -> bool:
    if n == 0:
        return false
    while (n % base == 0):
        n //= base
    #     ^^ note two slashes
    return n == 1

在 Python 3.x 中，/ 操作始终执行“实数除法”并返回一个 float ，但在您链接到的算法中，它期望 / 进行整数除法，而这是通过 //(“floor division”)运算符完成的。

正如您所预料的那样，测试确实失败了，因为浮点运算缺乏精度。当 / 返回无限精度实数时，该算法仍然正确。以3.0³⁴为例，

3.0 ** 34 == 16677181699666569
          == 0b111011001111111100111011110011000100000011001010001001

默认的浮点格式只支持53位的精度，但是上面的数字需要54位来表示，所以我们要对最后一位进行四舍五入位(第 1)位，导致

             0b111011001111111100111011110011000100000011001010001000
                                                                    ^
          == 16677181699666568

对 3 取模将返回 2，这将打破循环并返回 false。

(我没有检查为什么它向下而不是向上舍入，但即使向上舍入模数仍然不为零，所以它仍然会返回 false。)