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

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

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

Post by jalih »

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...
User avatar
Juan Carlos
Posts: 884
Joined: Mon Sep 06, 2010 1:02 pm

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

Post by Juan Carlos »

What is the use of this fibonacci number?
Post Reply