为什么我的小 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() - 它们设计用于处理非常大的整数。

Answer 2

我用 Matlab 中的 mupad 生成的斐波那契数进行了检查（使用 numlib::fibonacci(n)）。是因为精准。 Python 无法检测超过 52 位的精度，因此对于大于 2^52 的数字，精度将丢失。你可以用76th fibonacci number和77th fibonacci number检查它以查看problem。第 76 个斐波那契数：3416454622906707 第 77 个斐波那契数：5527939700884757

Answer 3

与python52位（点前后共计）后精度松动有关。您必须使用从模块 gmpy2 导入的 gmpy2.square() 这是处理大数字的唯一方法。

Answer 4

正如已经指出的那样，问题完全出自 math.sqrt，这是一个 浮点数 运算，意味着不完全精确（与整数运算不同）。 python 中浮点数的精度约为 16，这意味着对超过 16 位数字的精度浮点运算总是变坏。

您可以使用标准库中包含的 decimal 模块中的 Decimal 类型，而不是使用浮点数（math.sqrt 将您的整数隐式转换为浮点数）。这是一种浮点类型，具有可变的、可控的精度。要修复您的程序，只需将您的 isPerfectSquare 函数替换为：

import decimal
def isPerfectSquare(x):
    # Set decimal precision and convert x to Decimal type
    decimal.getcontext().prec = len(str(x))
    x = decimal.Decimal(x)
    # Check if perfect square
    s = int(x.sqrt())
    boo = (s*s == x);
    return boo

此处精度设置为等于输入数字的位数，由输入数字的 str 表示形式的长度给出。

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

why is my little python fibonacci detector failed?

python

algorithm

fibonacci