Kirjautuminen

Haku

Tehtävät

Keskustelu: Koodit näytille: 8th: Suuren Fibonaccin luvun laskeminen

Sivu 1 / 1

jalski [15.04.2019 20:35:11]

Lainaa #

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
\

: 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 ;

Ohjelman suorituksen tulos on:

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

Vastaus

Muista lukea kirjoitusohjeet.
Tietoa sivustosta