BASIC User Group > Code Challenges

fibonacci(4784969)

(1/22) > >>

jalih:
After following John on Rasberry Pi Forums and seen some people obsessed with fibonacci(4784969), I decided to try calculating that million digit number using 8th. Actually it was really easy and result is really fast. I used locals, so getting rid of those and utilizing stack should give even better performance.


--- Code: ---
\
\ Fibonacci with million digits
\

: fibo-loop
  "a" w:@ "b" w:@ 2 n:* "a" w:@ n:- n:* "d" w:!
  "a" w:@ dup n:* "b" w:@ dup n:* n:+ "e" w:!
  "d" w:@ "a" w:!
  "e" w:@ "b" w:!
  r@ swap n:shr 1 n:band if
    "a" w:@ "b" w:@ n:+ "c" w:!
    "b" w:@ "a" w:!
    "c" w:@ "b" w:!
  then ;


locals:
: fibo
  >r
  0 "a" w:!
  1 "b" w:!
  ' fibo-loop 0 31 loop-
  rdrop
  "a" w:@ ;


: app:main
  d:msec >r
  4784969 fibo
  d:msec r> n:- >r
  "%.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 ;

--- End code ---

Result is:


--- Code: ---C:\temp>8th fibo.8th
1000000 digits:
1072739564180047722936481359622500432190 upper 40 digits
3407167474856539211500699706378405156269 lower 40 digits
279 msec

--- End code ---

John:
It seems you have the best time so far.

Thanks for taking on the challenge!

jalih:

--- Quote from: John on April 15, 2019, 08:38:20 am ---It seems you have the best time so far.

--- End quote ---

Here is a little bit faster (a couple of msec) version. I eliminated all local variables and used just stack.


--- Code: ---\
\ 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
  F0 F1   \ 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 ;

--- End code ---

jalih:
I packaged a binary for RPI. Could someone test it with real Rasberry Pi hardware? I would love to know how fast it is.

John:
Works on my Raspberry Pi 3 B.


pi@RPi3B:~/rpi8th/rpi32 $ time ./fibo
1000000 digits:
1072739564180047722936481359622500432190 upper 40 digits
3407167474856539211500699706378405156269 lower 40 digits
1946 msec

real   0m2.090s
user   0m2.044s
sys   0m0.040s
pi@RPi3B:~/rpi8th/rpi32 $

Navigation

[0] Message Index

[#] Next page

Go to full version