## Don't waste hours on micro-optimizing, just choose better algorithm

Everything that doesn't really have to do with Hollywood
jalih
Posts: 254
Joined: Fri Jun 18, 2010 8:08 pm
Location: Finland

### Don't waste hours on micro-optimizing, just choose better algorithm

I stumbled upon coding challenge on Rasberry Pi forums about calculating fibonacci number with million digits. I chose to use 8th programming language as it directly supports big numbers (I am lazy!). My first version was simply naive iterative version of fibonacci, it took 2.8 hours to complete, but I got the right answer. Then I found about "Fast doubling algorithm" and decided to try it out:

Code: Select all

``````\
\ Fibonacci with million digits
\

: fibo-loop
>r                             \ Put loop counter on r-stack
\ a b
2dup 2 n:*                     \ a b a 2b
over n:-                       \ a b a (2b-a)
n:* -rot                       \ d=(2b-a)*a a b
dup n:* swap dup n:* n:+       \ d=(2b-a)*a e=b*b+a*a
r> r@ swap n:shr 1 n:band if
dup  \ a b b
rot  \ b b a
n:+  \ b c=b+a
then ;

: fibo  \  n -- fibo(n)
>r    \ Put n on r-stack
0 1   \ a b
' fibo-loop 0 31 loop-
rdrop
drop ;  \ a

: app:main
d:msec >r
4784969 fibo
d:msec r> n:- >r
n:bfloat "%.f" strfmt \ Convert result to just an 'int' string.
s:len . " digits:" . cr
dup 40 s:lsub . " upper 40 digits" . cr
40 s:rsub . " lower 40 digits" . cr
r> . " msec" . cr
bye ;
``````
And the result was:

Code: Select all

``````C:\temp\fibo>8th fibo.8th
1000000 digits:
1072739564180047722936481359622500432190 upper 40 digits
3407167474856539211500699706378405156269 lower 40 digits
273 msec
``````
From 2.8 hours to 273 millisecs, not bad...

Juan Carlos
Posts: 673
Joined: Mon Sep 06, 2010 1:02 pm
Contact:

### Re: Don't waste hours on micro-optimizing, just choose better algorithm

What is the use of this fibonacci number?