Version 2 of Fibonacci numbers

Updated 2005-04-06 20:06:02 by suchenwi

if 0 {Richard Suchenwirth 2005-04-06 - Fibonacci numbers [L1 ] are a famous example for recursion. They are defined as

   fib(0) = 0
   fib(1) = 1
   fib(x) = fib(x-1) + fib(x-2)

As in all non-trivial cases it calls itself twice, tail call optimization (there's also Fibonacci code on that page) is not helping here. The straightforward implementation is very simple:}

 proc fibo(r) x {
    expr {$x<2? $x: [fibo(r) [- $x 1]] + [fibo(r) [- $x 2]]}
 }

# where expr operators are exposed as commands (not needed in Jim):

 foreach op {+ -} {proc $op {a b} "expr {\$a $op \$b}"}

if 0 {However, on moderate arguments it gets immoderately slow:

 % time {fibo(r) 30} 1
 168360042 microseconds per iteration

Trying to get faster by using incr - it changes x, so the second time we again de-increment by 1:}

 proc fibo(r2) x {
    expr {$x<2? $x: [fibo(r2) [incr x -1]] + [fibo(r2) [incr x -1]]}
 }

if 0 {But 93 seconds are still long:

 % time {fibo(r2) 30} 1
 93862895 microseconds per iteration

Iterative solutions (which avoid recursion) are expected to be much faster, and the art of tail call optimization is to convert elegant recursions into efficient iterations.

The iterative version I cooked up is more "imperative" and complex. The for loop looks a bit funny, because it initializes all but the "loop variable", but we use the single argument for that, and decrement it:}

 proc fibo(i) x {
    if {$x < 2} {return $x}
    for {set last 1; set prev 0} {$x>1} {incr x -1} {
        set  tmp  $last
        incr last $prev
        set  prev $tmp
    }
    set prev
 }

if 0 {Just for comparison, here's the iterative solution from Tcllib:}

 namespace eval math {} ;# to be independent of Tcllib itself...

 proc ::math::fibonacci {n} {
    if { $n == 0 } {
            return 0
    } else {
       set prev0 0
       set prev1 1
       for {set i 1} {$i < $n} {incr i} {
           set tmp $prev1
           incr prev1 $prev0
           set prev0 $tmp
       }
       return $prev1
    }
 }

if 0 {To my surprise, although it's lengthier, math::fibonacci runs still 5% faster than fibo(i) - tested again on on fib(30), which results in 514229 from all candidates (on my 200MHz Win95 box at home):

 % time {math::fibonacci 30} 5000
 255 microseconds per iteration
 % time {fibo(i) 30} 5000
 268 microseconds per iteration

Could it be that initialization in the for loop creates less efficient bytecode than if it's done outside it? But in any case, it's good to know that Tcllib users get the fastest version :)


See also Elegance vs. performance - Fibonacci coding


Category Mathematics | Arts and crafts of Tcl-Tk programming }