Software bugs aren't inevitable

[Carl Friedrich Bolz]

Hi!

2005/9/15, Jerzy Karczmarczuk <karczma at info.unicaen.fr>:

[snip]

> But, I have used myself the cascading version. It was done on purpose, in
> order to get to the following solution.
> [[I preferred to use a global dict, but other ways of doing it are also
> possible]].
> 
> fibdic={0:0,1:1}
> def fibd(n):
>     if not fibdic.has_key(n):
>         r=fibd(n-1)+fibd(n-2)
>         fibdic[n]=r
>     return fibdic[n]
> 
> And here the recursion limit won't get you!!
> But the memoization techniques are rarely taught nowadays...
> 
> =====
> 
> And the story doesn't end here. There are backtracking solutions, which
> in functional (lazy) languages can be emulated through co-recursion, and
> in Python by the use of generators.
> 
> Jerzy Karczmarczuk
> --
> http://mail.python.org/mailman/listinfo/python-list
> 

It is also possible to do a version that scales logarithmically with
n. It relies on the observation that calculation of the fibonacci
series can be done by taking the upper left entry of the following
matrix exponentiation:

       n
 /1 1\
 \1 0/

Since exponentiation can be done logarithmically this can be used to
calculate fibonacci series faster (at least for big values of n):

def mul(m1, m2):
    ((a, b), (c, d)) = m1
    ((e, f), (g, h)) = m2
    return [[a*e + b*g, a*f + b*h],
            [c*e + d*g, c*f + d*h]]

def expo(m, n):
    if n == 0:
        return [[1, 0], [0, 1]]
    if n % 2 == 0:
        r = expo(m, n//2)
        return mul(r, r)
    else:
        return mul(m, expo(m, n - 1))

def fib(n):
    return expo([[1, 1], [1, 0]], n)[0][0]

With this you can calculate really big fibonacci numbers without
increasing the recursion depth, even though the expo function is
recursively written.

Cheers,

Carl Friedrich Bolz