Kirjoittaja: jalski
Kirjoitettu: 15.04.2019 – 15.06.2020
Tagit: matematiikka, koodi näytille, vinkki, yleispätevä
Alla 8th toteutus fibonaccin luvun laskemiseksi, missä on miljoona numeroa. Käyttää "Fast Doubling" algoritmia. Omalla koneellani iteratiivisen "perinteisen" toteuksen ajo kesti 2.8 tuntia. Alla olevan toteutuksen ajo vie vain 275 millisekuntia.
Toimii samalla hyvänä esimerkkinä, miten eliminoida lokaalit muuttujat pois 8th koodista.
\
\ Fibonacci with million digits
\
: bits? \ n -- nbits-1
n:ln 2 n:ln n:/ n:int ;
: 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
n:sqr swap n:sqr 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 r@ bits? loop-
rdrop
drop ; \ a
: app:main
d:msec >r
1000000 n#
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 ;Ohjelman suorituksen tulos on:
C:\temp\fibo>8th fibo.8th 1000000 digits: 1072739564180047722936481359622500432190 upper 40 digits 3407167474856539211500699706378405156269 lower 40 digits 273 msec
Edit:
Raspberrypi.org foorumeilla kreidl nimimerkkiä käyttävä käyttäjä huomioi, että käyttämässäni koodissa lasketaan fibo(4784969) lisäksi myös fibo(4784970). Tämä ei tietenkään ole optimitilanne, jos haetaan nopeutta laskentaan. Pienellä muokkauksella ohjelman suoritusaika putosi peräti 175 millisekuntiin.
\
\ Fibonacci with million digits
\
: bits? \ n -- nbits-1
n:ln 2 n:ln n:/ n:int ;
: 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
n:sqr swap n:sqr 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 1 r@ bits? loop-
\ a b
r> 1 n:band if
n:sqr swap n:sqr n:+ \ b*b+a*a
else
2 n:* over n:- n:* \ (2b-a)*a
then ;
: app:main
d:msec >r
1000000 n#
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 ;Linkin kuvassa on laskettu Julian joukko vakiolla:
-0.17739528514720775960 + 0.64973522230360247760i
https://www.tiede.fi/comment/2642701#comment-2642701
Lisäys: Oho, viesti tuli väärään ketjuun, mutta kuitenkin fibonaccin luvuilla ja Julian joukoilla on kaukaista tekemistä toistensa kanssa.
Muokkasin koodivinkkiä toimimaan tuoreimmalla 8th versiolla. Suurten lukujen laskentaan käytetty kirjasto muuttui ja samalla ohjelman suoritusaika putosi omalla koneellani 175 ms -> 113 ms.