Fast Fibonacci slows to a crawl over 1,000,000

Question

I've written a pretty standard fibonacci function through fast doubling using an algorithm derived from the matrix exponentiation algorithm which should run in O(log(n)) time and calls, but stalls out at around over 1,000,000 - even when that should be just around 25 calls.

Code:

"""
O(log(n)) time fibonacci algorithm using fast doubling derived from the matrix
squaring algorithm for the same thing.
"""

def fibonacci(num):
    "O(log(n)) implementation of fibonacci using fast doubling."
    if num >= 0:
        return fib_helper(num)[0]

def fib_helper(num):
    "Helper function for fibonacci()."
    if num == 0:
        return (0, 1)
    elif num == 1:
        return (1, 1)
    else:
        f_k, f_k_1 = fib_helper(num // 2)
        f_k_even = f_k * (2 * f_k_1 - f_k)
        f_k_odd = f_k_1 * f_k_1 + f_k * f_k
        return (f_k_even, f_k_odd) if num % 2 == 0 else (f_k_odd, f_k_even +
                f_k_odd)

This code should only generate log(n) calls to fib_helper and one call to fibonacci. For numbers greater than 1,000,000 it just stalls out and doesn't return.

I've tried implementing a basic decorator to to count function calls which tells me that it is only running 32 calls for 2^32, but it still stalls out at the end.

Why is this slowing to a halt on large integers?

Answer 1

Try running you code like this

print "calculating fib(1000000)"
res = fib(1000000)
print "displaying the result..."
print res

The problem is that fib(1000000) is a quite large number (>10²⁰⁰⁰⁰⁰). Your computer can operate on these numbers quite quicky because everything is done in binary.

When you try to display the number, it needs to be converted to base 10. This can be very time consuming!

Converting to hex is much easier. The bits just need to be grouped into fours, so

print hex(res)

will start spitting stuff out quite quickly