Search code examples
pythonfibonacci

How can I increase the accuracy of Fibonacci implementation for large n?

I'm using Binet's Formula to calculate Fibonacci number for large n

Binet's Formula: Binet's Formula:

my code:

#!/usr/bin/env python3
def calc_fib(n):
  if (n <= 1):
  return n

  root_5    = 5 ** 0.5
  phi_n   = ((root_5 + 1) / 2) ** n
  alpha_n = ((root_5 - 1) / 2) ** n

  fn = round((phi_n - alpha_n) / root_5)
  return fn

n = int(input())
print(calc_fib(n))

$ ./fibonacci.py 200 280571172992512015699912586503521287798784. (wrong)

the correct result is: 280571172992510140037611932413038677189525

the problem is that for very large n, say n = 200, the result is not accurate, I think because of the floating-point calculations, How can I change my code so I can get more accurate results?

Solution

  • The problem with Binet's formula is that you need increasing accuracy to do the calculations, and floating point doesn't give you that.

    There's a few ways to compute Fibonacci numbers efficiently. Here's my favourite, that isn't (explicitly) iterative, and has roughly the right runtime complexity:

    def fib(n):
    X = 1<<(n+2)
    return pow(X, n+1, X*X-X-1) % X

    This uses arithmetic with a number of bits that grows linearly with n, which I think is ok because the number of bits the result has grows linearly.

    Alternative log(n) approaches are to use doubling formulae, use an integer version of Binet's formula (typically in an algebraic ring), or matrix power. I have a blog post describing them in more detail: https://blog.paulhankin.net/fibonacci2/