2

我正在尝试继续我之前的问题，在该问题中我正在尝试使用 Benet 算法计算斐波那契数。为了以任意精度工作，我发现mpmath. 然而，实现似乎在某个值以上失败。例如第 99 个值给出：

218922995834555891712

这应该是（参考）：

218922995834555169026

这是我的代码：

从 mpmath 导入 *

定义披（）：
    返回 (1 + sqrt(5)) / 2

定义 phi():
    返回 (1 - sqrt(5)) / 2

定义 F(n):
    返回 (power(Phi(), n) - power(phi(), n)) / sqrt(5)

开始 = 99
结束 = 100

对于范围内的 x（开始，结束）：
    打印（x，int（F（x）））
4

3 回答 3

3

mpmath提供任意精度（如 中设置mpmath.mp.dps），但计算仍然不准确。例如，mpmath.sqrt(5)不准确，因此基于此的任何计算也是不准确的。

要获得准确的结果sqrt(5)，您必须使用支持抽象计算的库，例如http://sympy.org/。

要获得斐波那契数的准确结果，最简单的方法可能是使用仅执行整数运算的算法。例如：

def fib(n):
  if n < 0:
    raise ValueError

  def fib_rec(n):
    if n == 0:
      return 0, 1
    else:
      a, b = fib_rec(n >> 1)
      c = a * ((b << 1) - a)
      d = b * b + a * a
      if n & 1:
        return d, c + d
      else:
        return c, d

  return fib_rec(n)[0]
于 2014-09-07T21:19:20.987 回答
3

mpmath 确实执行任意精度数学，并且如果您使用的是任意精度数学模块而不是默认行为，它确实可以精确到任何精度（如上所述）。

mpmath 有多个模块来确定结果的准确性和速度（根据您的需要进行选择），并且默认情况下它使用 Python 浮点数，我相信您在上面看到了这一点。

如果您调用 mpmath 的 fib() 并设置了足够高的 mp.dps，您将得到如上所述的正确答案。

>>> from mpmath import mp
>>> mp.dps = 25
>>> mp.nprint( mp.fib( 99 ), 25 )
218922995834555169026.0
>>> mp.nprint( mpmath.fib( 99 ), 25 )
218922995834555169026.0

然而，如果您不使用 mp 模块，您将只能获得与 Python double 一样准确的结果。

>>> import mpmath
>>> mpmath.dps = 25
>>> mpmath.nprint( mpmath.fib( 99 ), 25
218922995834555170816.0
于 2016-08-16T16:32:52.183 回答
1

实际上 mpmath 的默认精度是 15，如果您想获得高达 21 位精度的结果，我认为这还不够。

您可以做的一件事是将精度设置为更高的值，并使用 mpmath 定义的算术函数进行加法、减法等。

    from mpmath import mp
    mp.dps = 50
    sqrt5 = mp.sqrt(5)
    def Phi():
        return 0.5*mp.fadd(1, sqrt5)

    def phi():
        return 0.5*mp.fsub(1, sqrt5)

    def F(n):
        return mp.fdiv(mp.power(Phi(), n) - mp.power(phi(), n), sqrt5)

    print int(F(99))

这会给你

    218922995834555169026L
于 2016-08-22T01:51:48.733 回答