Software bugs aren't inevitable

Carl Friedrich Bolz cfbolz at googlemail.com
Thu Sep 15 13:46:54 CEST 2005


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



More information about the Python-list mailing list