Ropstah - 1 year ago 100

Python Question

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`

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)))

Answer Source

`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]
```