CODEWITHSUNDEEP
pythonperformancealgorithmrecursionfibonacci
reem
reem

Reputation: 7236

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

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?

Upvotes: 4

Views: 1319

Answers (2)

Tim Peters
Tim Peters

Reputation: 70592

Just for interest, since my decimal comments were apparently inscrutable ;--), here's the code:

import decimal
from decimal import Decimal as D
DO = D(0)
D1 = D(1)

def fibonacci(num):
    from math import log10
    if num >= 0:
        ndigits = int(log10(1.62) * num + 100)
        decimal.getcontext().prec = ndigits
        decimal.getcontext().Emax = ndigits
        return fib_helper(num)[0]

def fib_helper(num):
    if num == 0:
        return (D0, D1)
    elif num == 1:
        return (D1, D1)

and the rest of fib_helper() is unchanged (see the original message). In Python 3, decimal is implemented in C, and computation time is comparable to using native (binary) integers. But the point is the time for output conversion to a decimal string: instead of being a huge bottleneck, it becomes a trivial part of the runtime.

For example, fibonacci(100000000) (a hundred million) takes about 30 seconds on this box, but after that:

>>> from time import clock as now # on this box, `clock()` is wall-clock time
>>> if 1:
...    t = now()
...    print(len(str(x)))
...    print(now()-t)
...
20898764
0.10466078789343337

So a tenth of a second to produce the string of 20+ million decimal digits. For argument one billion, about 0.9 seconds to produce the 208,987,640-digit decimal string: clearly linear in the number of decimal digits.

Note: decimal is really aiming at decimal floating- and fixed-point calculations. While it can be used fine for high precision integer calculations, you have to specify the number of digits you'll need, and the maximum exponent, in advance. It has no "unbounded" mode. The code above uses that fibonacci(n) is approximately equal to 1.618**n.

Upvotes: 3

John La Rooy
John La Rooy

Reputation: 304147

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 (>10200000). 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

Upvotes: 9

Related Questions