Re: Software bugs aren't inevitable

Hi!

2005/9/15, Jerzy Karczmarczuk <karczma@xxxxxxxxxxxxxxx>:

[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
.

Relevant Pages

  • [SUMMARY] Magic Fingers (#120)
    ... it will stall a loss as long as possible to increase ... hand of one finger and a right hand of two fingers is the same as a left of two ... def do_turn ... we see the code that controls when recursion stops. ...
    (comp.lang.ruby)
  • Re: Need help with Python scoping rules
    ... suggests that Python does not fully support class-level encapsulation. ... on recursion. ... def fact_rec: ...
    (comp.lang.python)
  • Re: Need help with Python scoping rules
    ... This is shown most clearly by the following elaboration of ... (Or you want to say that that languages also are not fully valuable ... *It has nothing to do with recursion.* ... def fact: ...
    (comp.lang.python)
  • Re: Software bugs arent inevitable
    ... > First of all, the recursive version of Fibonacci IS EXPONENTIAL in complexity, ... themselves part of a Fibonacci-like sequence. ... But it is a very common algorithm -- I have four or five textbooks at home ... > Such anti-advertizing of recursion says less about the recursion ...
    (comp.lang.python)
  • Re: Computing fibonacci numbers (rank newbie)
    ... I'm trying to define a function to compute Fibonacci numbers up to ten ... (cond ((< n 2) ... even right to use recursion? ... You're confusing iteration with recursion. ...
    (comp.lang.lisp)