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

[#] Next page

Go to full version