if 0 {[Richard Suchenwirth] 2005-04-06 - Fibonacci numbers
[http://mathworld.wolfram.com/FibonacciNumber.html] 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>0} {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 ''([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).
----
See also [Elegance vs. performance] - [Fibonacci coding]
----
[Category Mathematics] | [Arts and crafts of Tcl-Tk programming]
}