Version 6 of Fibonacci numbers

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 :)

NEM They also give different answers:

 % fibo(i) 30
 514229
 % ::math::fibonacci 30
 832040

You can also generalise the (tcllib) proc to generate the similar Lucas numbers too:

 proc Fibish {first second n} {
   if {$n == 0} {
     return $first
   } else {
     for {set i 1} {$i < $n} {incr i} {
       set tmp $second
       incr second $first
       set first $tmp
     }
     return $second
   }
 }
 interp alias {} Fib {} Fibish 0 1
 interp alias {} Lucas {} Fibish 2 1

This appears to be identical in speed to the tcllib version (which it is just a slight generalisation of).

 % proc showfirst {f n} {
   set ret [list]
   for {set i 0} {$i <= $n} {incr i} { lappend ret [$f $i] }
   return $ret
 }
 % showfirst Fib 30
 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
 % showfirst Lucas 30 
 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127 24476 39603 64079 103682 167761 271443 439204 710647 1149851 1860498

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