Faster Fibonacci Numbers

[chris-chan]

No language in title because this is more about the algorithms and not about any particular language. I will however use Python in the code examples.

I've noticed recently that everybody seems to use the same basic algorithm for computing Fibonacci numbers. This kinda bothers me because there are a few faster algorithms that aren't very complex but for some reason nobody seems to know about them.

Fibonacci numbers are often used to teach beginner programmers about recursion and caching or "memoization". The most basic recursive algorithm is something like this:

 

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

This solution is a pretty straightforward translation from the mathematical definition of the Fibonacci sequence. The problem with it is that it is extremely slow because every step recalculates the intermediate values many times. An easy way to make it faster is to use a cache so the function remembers values it has already calculated. In Python this is pretty simple:

 

from functools import cache


@cache
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

An iterative solution can save some memory space by avoiding the need for a cache, and it can also avoid extra function calls, thus being a bit faster:

 

def fib(n):
    a, b = 0, 1
    while n > 0:
        a, b = b, a+b
        n -= 1
    return a

And this is usually where people usually stop.  This is where I would have stopped before about a week ago, when I tried writing this in C using the GNU Multiple Precision arithmetic library (a.k.a. GMP). I was surprised when my basic translation of the iterative version into C was actually a bit slower than the Python version! I decided to read the manual a bit to see if I was doing something wrong when I found GMP's Fibonacci functions. Those ended up being much faster than my simple iterative Python solution. GMP explains the algorithm they use in this manual page. I tried implementing a similar algorithm in Python using some of the identities on the manual page and got a pretty fast Python function (though not as fast as GMP, still much faster than the other Python versions).
 

from functools import cache

SMALL_FIBS = [
    0, 1, 1, 2
    3, 5, 8, 13,
    21, 34, 55, 89,
    144, 233, 377, 610
]
SMALL_FIBS_LEN = len(SMALL_FIBS)

@cache
def fib(n):
    if n < SMALL_FIBS_LEN:
        return SMALL_FIBS[n]
    
    k = n//2
    fib_k = fib(k)
    fib_k1 = fib(k - 1)
    
    if n&1: # n is odd
        return (2 * fib_k + fib_k1) * (2 * fib_k - fib_k1) + 2*(-1)**k
    else:
        return fib_k * (fib_k + 2 * fib_k1)

What I don't get is why this version or something similar isn't more well known? It seems similar to exponentiation by squaring, which is a pretty well known way to quickly calculate powers of numbers. Anyway, I just wanted to share this somewhere other than Reddit lol.

[adm0n]

I'd assume it isn't that well known, because people usually don't need the Fibonacci numbers. So the only time you will stumble upon them is either while learning about a programming language or in some sort of toy problem. The latter being more rare.

 

And while learning a language, optimization isn't that big of a deal. So people like to go for the more easy to understand solutions.

[unkn0wn1]

In a DSP class in college we actually took the Fibonacci equation and solved it as a difference equation. I found that really interesting and I keep wondering why we only learn a basic method in programming classes. It is weird that they never really mention there are better ways to do it...

[dcgreen2k]

My guess as to why more those more complex versions aren't taught or as well known is because the basic version is already great for introducing recursion in programming, as OP said. Aside from that, I don't know how useful a blazing-fast Fibonacci sequence solver is in practical applications.

 

I'll also add that the caching solution you found is called dynamic programming. It's very useful for solving problems that can be modeled as a graph, which the Fibonacci sequence is.

 

[wanderingfool2]

3 hours ago, chris-chan said:

What I don't get is why this version or something similar isn't more well known? It seems similar to exponentiation by squaring, which is a pretty well known way to quickly calculate powers of numbers. Anyway, I just wanted to share this somewhere other than Reddit lol.

I think it's because in general most people don't care about the performance when writing fib, and it's a great tool to learn recursion and being able to translate a recursive function into a non-recursive function.

 

It's short and straightforward so it makes a great teaching tool.  From there though the question is why bother teaching a more complex form?

 

While it could teach about minimizing operations through creative math, I think the math behind why it would work is likely above the level at which people are learning the fib function.

 

Also fib isn't too useful in many applications, I don't think I've ever had to use it...or if I did I'd just be calling a std library anyways....or do the bad thing and just hardcode the first chunk of numbers.  Or just taking the hit as a function that is maybe called a few times it doesn't matter if it takes 1 microsecond vs 40 microseconds...if it is called enough though having the numbers already hardcoded would be the fastest anyways.

 

It's important to remember that fib grows very quickly very quickly.  For an UINT64 it can only hold up to fib(94)...even if you went to UINT128 fib(180 ish) you would be wrapping it around.

 

I'm sure someone could have a reason to want a fib at that height, but even if you stored it as UINT256 (fib 370ish) you are only talking about 11,840 bytes of information...more than small enough to just keep hardcoded in most applications.

 

If one doesn't care about exact precision though I always like the following implementation

double pre_calc_phi = (1 + sqrt(5)) / 2;
double pre_calc_sqrt_5 = sqrt(5);

int fib(int n) {
  return round(pow(pre_calc_phi, n) / pre_calc_sqrt_5);
}

 

[Sauron]

14 hours ago, chris-chan said:

What I don't get is why this version or something similar isn't more well known?

I'm sure it's well known in the world of people who need to implement fast fibonacci number functions, which probably doesn't include a lot of people  but do consider that whenever you need to calculate a sequence recursively it's pretty much always faster to precalculate as many numbers as possible. With the amount of RAM we have available these days there isn't much reason not to just have an array with the first 1000 fibonacci numbers.

[Franck]

7 hours ago, Sauron said:

these days there isn't much reason not to just have an array with the first 1000 fibonacci numbers.

amen. text files to the rescue

[wanderingfool2]

9 hours ago, Sauron said:

I'm sure it's well known in the world of people who need to implement fast fibonacci number functions, which probably doesn't include a lot of people  but do consider that whenever you need to calculate a sequence recursively it's pretty much always faster to precalculate as many numbers as possible. With the amount of RAM we have available these days there isn't much reason not to just have an array with the first 1000 fibonacci numbers.

I've given it thought and I can't think of any purposes in which utilizing more ram would not be the way to go...unless maybe a sat or something run on a super computer where you try minimizing the program size...but I can't see needing too much of fib either.

 

A note though, fib(1000) > 4 * 10^208, so you need 694 bits to store that number...so about 86kB of memory. [It tends to about 1 increment = 0.69 bits needed for the next step]

fib(10000) = roughly 8.6mB

[Sauron]

1 minute ago, wanderingfool2 said:

A note though, fib(1000) > 4 * 10^208, so you need 694 bits to store that number...so about 86kB of memory. [It tends to about 1 increment = 0.69 bits needed for the next step]

yeah, you probably need a lot fewer than 1000 fibs for any given practical purpose... I imagine the first 50 are more than enough.