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: my code: #!/usr/bin/env python3 def calc_fib(n): if (n <= 1): return n root_5 =

Solution 1:

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)
    returnpow(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/

Solution 2:

I think you want to correct alpha_n according to the formula:

alpha_n = ((1 - root_5) / 2) ** n