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:
And the result was:
From 2.8 hours to 273 millisecs, not bad...
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 ;
Code: Select all
C:\temp\fibo>8th fibo.8th
1000000 digits:
1072739564180047722936481359622500432190 upper 40 digits
3407167474856539211500699706378405156269 lower 40 digits
273 msec