Page 1 of 1

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

Posted: Wed Apr 17, 2019 8:41 pm
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...

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

Posted: Mon Apr 22, 2019 11:42 pm
What is the use of this fibonacci number?