Kirjautuminen

Haku

Tehtävät

Koodivinkit: 8th: Suuren Fibonaccin luvun laskeminen

Kirjoittaja: jalski

Kirjoitettu: 15.04.2019 – 26.06.2019

Tagit: matematiikka, 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
  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
  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 ;

Kommentit

jone2712 [24.04.2019 15:38:38]

Lainaa #

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.

Kirjoita kommentti

Muista lukea kirjoitusohjeet.
Tietoa sivustosta