python - 为什么我的小 python 斐波那契检测器失败了？

Question

由于某些原因，我必须确定一个大数是否是一个斐波那契数，所以我从网上复制了一些代码并稍微修改了一下，输入大时似乎运行不佳。这是代码:

# python program to check if x is a perfect square

import math

# A utility function that returns true if x is perfect square
def isPerfectSquare(x):
    s = int(math.sqrt(x))
    boo = (s*s == x);
    return boo

# Returns true if n is a Fibinacci Number, else false
def isFibonacci(n):

    # n is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both
    # is a perferct square
    b = 5*n*n+4;
    c = 5*n*n-4;
    return isPerfectSquare(b) or isPerfectSquare(c)

# A utility function to test above functions

a = int(input("give me the number"));
print(isFibonacci(a))

当我输入 610 时，它按计划输出 true，但是当我输入

"215414832505658809004682396169711233230800418578767753330908886771798637" 

我知道这是我编写的另一个 Java 程序中的第 343 个斐波那契数。它输出错误令人惊讶。那么是不是因为数字太大所以出错了呢？但我认为 python 应该能够处理巨大的数字，因为它基于你拥有的内存？是我程序的问题还是因为输入太大？谢谢!

Answer 1

你失去了精度。对于 n > 1e45(大约)，(n**0.5)**2 != n。尝试使用模块 gmpy2 中的 gmpy2.isqrt() 和 gmpy2.square() - 它们设计用于处理非常大的整数。