Fibonacci numbers

Fib in TAL ,by kbk ,2012-08-21

Fibonacci Numbers With the U Combinator ,by kbk ,2012-08-21

,kbk ,2012-08-21

Fibonacci numbers with coroutine, 2015-11-12

Richard Suchenwirth 2005-04-06 - Fibonacci numbers [1] 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}"}

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]]}
}

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>0} {incr x -1} {
       set  tmp  $last
       incr last $prev
       set  prev $tmp
   }
   set prev
}

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
    }
}

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 (RS: Oops - fixed in fibo(i)):

% 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

KPV If speed is the goal then forget the iterative approach and just compute the value directly using the formula:

F(i) = round(phi**i / sqrt(5))

proc Fib2 {n} {
   set r5 [expr {sqrt(5)}]
   set phi [expr {(1 + $r5) / 2}]
   return [expr {round(pow($phi, $n)/ $r5)}]
}

On my 700Mhz XP machine I get:

% time {Fib2 46} 5000
10 microseconds per iteration
% time {::math::fibonacci 46} 5000
74 microseconds per iteration
% time {fibo(i) 46} 5000
81 microseconds per iteration

MPJ: Using the above code and making it just one call to expr I was able to shave a microsecond or two.

proc Fib3 {n} {
    return [expr {round(pow(((1 + sqrt(5)) / 2), $n)/ sqrt(5))}]
}

NEM: And in-lining as much as possible yields:

proc Fib4 n { expr {round(pow(1.61803398875,$n)/2.2360679775)} }

which takes just 12 microseconds to compute Fib4 30 on my 800MHz G4 (compared to 21 µs for Fib3).

Toni: This algorithm, taken from a javascript source is a lot faster.

proc fibo {x} {
  if {$x<2} {
    return [list 0 1]
  } else {
    set l [fibo [expr $x-1]]
    set len [llength $l]
    lappend l [expr [lindex $l [expr $len-1]]+[lindex $l [expr $len-2]]]
    return $l
  }
}

Category Mathematics

Arts and crafts of Tcl-Tk programming