Python中的日志精度

Question

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

以下是检查一个数字是否可以表示为幂的源代码，但是为什么对于 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!")

- Demonking28

---

不错，但一个真正的[mcve]是没有交互性的。由于Python 3输入不执行计算，那我们该如何输入76 ** 89 - 1呢？ - Jean-François Fabre

@Jean 246836689407345097174578535562295942574178711461144990797750214379645671228733039816084061952588114546106170632976745994369878558718869787931874388378698664981274034176和246836689407345097174578535562295942574178711461144990797750214379645671228733039816084061952588114546106170632976745994369878558718869787931874388378698664981274034175 - Demonking28

你在尝试做什么？你只是展示了你实际问题的尾巴。 - user1767754

正如您所发现的那样，通常情况下，浮点数并不足以进行这些计算。一旦您确定了候选项，可以通过进行一次健全性检查来取得一些进展 - 计算 i ** x 并查看是否与原始值匹配。 - Oliver Charlesworth

@user1767754 - 这位用户似乎已经非常明确地表达了他们的目标-编写一个程序，确定一个整数是否为精确幂。 - Oliver Charlesworth

我正在研究类似的东西：https://math.stackexchange.com/questions/4476802/is-there-a-mapping-function-to-transform-mn-to-sum-i-in-k2i-any-power - juanmf

Answer 1

您的代码只是找到了候选项，但没有检查它们是否确实匹配。浮点数不准确会导致您无法区分非常大的值和这个值减去一的区别。

但由于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)更快，可能也更准确，因为涉及的浮点运算较少。

- Jean-François Fabre

---

好东西。但是我无法说服自己浮点数的限制也不会受到错误负面影响。 - Oliver Charlesworth

@OliverCharlesworth也许我们会错过一些四舍五入可能出错的情况(也许这就是你的意思，还需要找到这些情况)，但我们找到的那些情况肯定会起作用。 - Jean-François Fabre

@Jean-FrançoisFabre - 我在思考原始log / log计算 - epsilon阈值是否足以接受所有精确幂的结果？ - Oliver Charlesworth

@OliverCharlesworth，明确指定一个更大的 epsilon 不会有太大影响。这只会使速度变慢。另一个问题是，在某些时候 sqrt(n) 无法计算出平方根：“OverflowError: int too large to convert to float”。有趣的是，log 可以工作，但 sqrt 却不能。 - Jean-François Fabre

问：相对于log(n, 2)/log(i, 2)，使用log(n, i)在浮点数精度方面更好吗？我认为它会更准确和更快。 - Mr. T