Python mpmath not arbitrary precision?
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`. However the implementation seems to fail above
certain value. For instance the 99th value gives:

> 218922995834555891712

This should be ([ref](http://www.maths.surrey.ac.uk/hosted-
sites/R.Knott/Fibonacci/fibtable.html)):

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

