Ropstah Ropstah - 3 months ago 20
Python Question

Python mpmath not arbitrary precision?

I'm trying to continue on my previous question in which I'm trying to calculate Fibonacci numbers using Benet's algorithm. To work with arbitrary precision I found

mpmath
. However the implementation seems to fail above certain value. For instance the 99th value gives:


218922995834555891712


This should be (ref):


218922995834555169026


Here is my code:


from mpmath import *

def Phi():
return (1 + sqrt(5)) / 2

def phi():
return (1 - sqrt(5)) / 2

def F(n):
return (power(Phi(), n) - power(phi(), n)) / sqrt(5)

start = 99
end = 100

for x in range(start, end):
print(x, int(F(x)))

pts pts
Answer

mpmath provides arbitrary precision (as set in mpmath.mp.dps), but still inaccuate calculation. For example, mpmath.sqrt(5) is not accurate, so any calculation based on that will also be inaccurate.

To get an accurate result for sqrt(5), you have to use a library which supports abstract calculation, e.g. http://sympy.org/ .

To get an accurate result for Fibonacci numbers, probably the simplest way is using an algorithm which does only integer arithmetics. For example:

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]