python - 在 python 中记录精度

Question

以下是源代码，它检查一个数字是否可以用幂表示，但为什么代码对于 n = 76 ** 89 - 1 和 n = 76 ** 89。我该如何解决这个错误？对于这两个 n，它给出 x=log(n,2)/log(i,2)=89.0

from math import log,sqrt,floor
import sys
n= 76 ** 89 - 1
t=floor(sqrt(n))+1
flag=False


for i in range(2,t):
    x=log(n,2)/log(i,2)
    print(x)
    if x-int(x)<sys.float_info.epsilon:
        print("YESSSSSSSSSSSSS!")
        flag=True
        break

if not flag:
    print("Nooooooooooooooooooo!")

Answer 1

您的代码只查找候选人，但不检查他们是否真的匹配。 float 的不准确性使得您无法区分像这样的非常大的值和这个相同的值减一。

但由于 Python 内置了无限范围的整数算法，您可以检查您找到的是否真的匹配。

我的想法:找到幂后，计算理论数的幂(通过四舍五入)，然后计算整数幂，然后比较整数。

from math import log,sqrt,floor
import sys
n = 76 ** 89
t=floor(sqrt(n))+1
flag=False


for i in range(2,t):
    x=log(n,i)  # faster than x=log(n,2)/log(i,2)

    if x-int(x)<sys.float_info.epsilon:
        x = int(round(x))
        r = int(round(n**(1/x)))
        print("found candidate: ",x,r)
        if n == r**x:   # exact integer comparison with initial value & found values
            print("YESSSSSSSSSSSSS!")
            flag=True
            break
        else:
            print("but not exact")

if not flag:
    print("Nooooooooooooooooooo!")

使用 76 ** 89 - 1 值，您得到“但不准确”，因为计算的功率与 n 值不匹配。

另外:使用 x=log(n,i) 比 x=log(n,2)/log(i,2) 更快，而且可能由于涉及较少的 float 操作，因此也更准确。