Kirjoittelin piruuttani Inferno käyttöjärjestelmän lähdekoodeissa mukana olevasta alkulukujen hakuohjelman Limbo lähdekoodista käännöksen 8th ohjelmointikielelle.
Toteutus on kohtuullisen nopea ja omalla Raspberry PI 4B tietokoneella ensimmäisen miljoonan alkuluvun hakemiseen menee aikaa:
root@DietPi:~# time /opt/8th/bin/rpi64/8th wheel.8th 0 15485863 >temp.txt real 0m57.158s user 0m45.213s sys 0m11.268s
\
\ Segmented wheel sieve
\
\ Adapted for 8th from the Inferno operating system sources:
\
\ https://github.com/inferno-os/inferno-os/blob/master/appl/math/primes.b
\
\ Subject to the Lucent Public License 1.02
\
9007199254740992 constant bigx
[ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,
157,163,167,173,179,181,191,193,197,199,211,223,227,229 ] constant pt
[ 10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,
6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2 ] constant wheel
8 constant BITS
1000 constant TABLEN
a:new ( 0 a:push ) TABLEN times constant table
[1,2,4,8,16,32,64,128] constant bittab
var nn
var limit
: ouch
"primes: limits exceeded\n" .
bye ;
: modf \ n -- int float
dup n:int swap n:frac ;
: mark \ n n --
2dup n:/ n:int
2dup n:* 3 pick n:- n:int
dup 0 n:< if
2 pick n:+
then
repeat
dup TABLEN BITS n:* n:< not if
break
else
table over 3 n:shr dup >r a:@ bittab 3 pick 7 n:band a:@ nip n:bor r> swap a:! drop
2 pick n:+
then
again
2drop 2drop ;
: app:main
argc not if
"usage: primes starting [ending]\n" .
bye
then
1 args bigx ?: >n limit !
0 args >n nn !
limit @ nn @ n:< if
bye
then
limit @ bigx n:> if
ouch
then
nn @ 0 n:< nn @ bigx n:> or if
ouch
then
nn @ 0 n:= if
2 nn !
then
nn @ 230 n:< if
( pt swap a:@ nip
dup nn @ n:< if
drop ;;
then
dup limit @ n:> if
bye
then
"%d\n" s:strfmt .
) 0 pt a:len n:1- nip loop
230 nn !
then
nn @ 2 n:/ n:int 2 n:* n:1+ nn !
repeat
\ Now run the sieve!
nn @ TABLEN BITS n:* n:+ n:sqrt
nn @ 3 mark
nn @ 5 mark
nn @ 7 mark
0
( nn @ swap mark
n:1+
dup wheel a:len nip n:< not if
drop 0
then
wheel over a:@ nip step
) 11 3 pick loop 2drop
( table over 3 n:shr n:int a:@ nip bittab 2 pick 7 n:band a:@ nip n:band if
drop
else
nn @ n:+ dup limit @ n:> if
bye
then
"%d\n" s:strfmt .
then
2 step
) 0 TABLEN BITS n:* n:1- loop
TABLEN BITS n:* nn n:+!
table ( drop 0 ) a:map= drop \ clear the sieve table
again ;Nopein tapa tuottaa alkulukuja on Eratostheneen seula. https://fi.wikipedia.org/wiki/
rebol[] print "odota" maxluku: 1000000 ;lasketaan Eratostheneen seulalla miljoonaa pienemmät alkuluvut neliöjuuri: Square-Root maxluku taulukko: array/initial maxluku true; oletetaan kaikki alkuluvuiksi taulukko/(1): false luku: 2 aika1: now/precise for ind luku maxluku luku [ taulukko/(ind): false ;poistetaan 2:n monikerrat ] while [luku < neliöjuuri][ while [(taulukko/(luku) = false) and (luku < neliöjuuri)][ ;etsitään seuraava alkuluku luku: luku + 1 ] for ind (luku + luku) maxluku luku [taulukko/(ind): false] ;poistetaan sen monikerrat luku: luku + 1 ] taulukko/(2): true aika2: now/precise print ["Aika kului ainoastaan" difference aika2 aika1] ;Nyt on taulukoitu miljoonaa pienemmät alkuluvut. Tulostetaan niistä tarkistuksen vuoksi sata ensimmäistä. for i 1 100 1 [ if taulukko/(i) [print i] ] halt
PetriKeckman kirjoitti:
Nopein tapa tuottaa alkulukuja on Eratostheneen seula. https://fi.wikipedia.org/wiki/
Eratostheneen_seula Mulla meni tehottomalla REBOL ohjelmointikielellä 1,283 sekuntia tuottaa miljoonaa pienemmät alkuluvut.
Segmentoitu versio on varmasti aina nopeampi, koska on äärimmäisen helppo lisätä tuki useammalle säikeelle. Lukkoja ei tarvita kun pystytään suoraan antamaan jokaiselle säikeelle oma lukualueensa. Lisäksi pystytään laskemaan hyvin nopeasti suoraan alkuluvut vaikka esimerkiksi väliltä: 100000000 - 100100000.
Sori. En ymmärrä "segmentoitu" "säie" "lukko". Mulle hepreaa :) Miksi sulla sitten on mennyt aikaa:
lainaus:
"real 0m57.158s
user 0m45.213s
sys 0m11.268s"
useita sekunteja, kun mulla meni 1.283 sekuntia miljoonan ekan alkuluvun tuottamiseen?
PetriKeckman kirjoitti:
Sori. En ymmärrä "segmentoitu" "säie" "lukko". Mulle hepreaa :) Miksi sulla sitten on mennyt aikaa:
lainaus:
"real 0m57.158s
user 0m45.213s
sys 0m11.268s"useita sekunteja, kun mulla meni 1.283 sekuntia miljoonan ekan alkuluvun tuottamiseen?
Tuotit ensimmäiset alle miljoonan olevat alkuluvut, eli 78498 alkulukua. Selvittääksesi ensimmäiset miljoona alkulukua sinun siis täytyisi selvittää alkuluvut lukuun 15485863 asti. Oma käännökseni tulostaa alkuluvut samalla kun käy niitä läpi ja iso osa ajasta menee tuohon.
Segmentoitu tarkoittaa sitä, että pystytään selvittämään alkuluvut tietyltä halutulta väliltä, kun taas segmentoimaton versio joutuu aloittamaan ja käymään lukuja läpi aina alusta lähtien.
Voit havannoida eron yrittämällä selvittää alkuluvut väliltä: 100000000 - 100100000
root@DietPi:~# time /opt/8th/bin/rpi64/8th primes.8th 100000000 100100000 >primes2.txt real 0m0.501s user 0m0.407s sys 0m0.092s
Segmentoimattomalla versiolla menee suoritukseen varmasti paljon pitempi aika.
Säie = thread ja niiden käyttäminen tarkoittaa sitä, että työmäärä voidaan jakaa useamman säikeen kesken, mitkä hyvässä tapauksessa pystyvät toimimaan yhtä aikaisesti. Lukolla voidaan suojata, että useampi säie ei yritä yhtä aikaa käsitellä tietoa. Tarkoittaa siis sitä, että muut säikeet odottavat sillä aikaa säiettä, jolla on "lukko".
Jalski kirjoitti:
Selvittääksesi ensimmäiset miljoona alkulukua sinun siis täytyisi selvittää alkuluvut lukuun 15485863 asti.
Hups! Sori. Alkeellinen ajatusvirhe mulla. No, nyt meni 26.9 sekuntia tuottaa miljoona ensimmäistä alkulukua ja kirjoittaa ne tiedostoon. EDIT: Taisit tarkoittaakin tulostusta konsoli-ikkunaan?! No, se olisi REBOL:lla tosiaan hidasta.
Tätä väliä 100000000 - 100100000 en nyt tähän hätiin tutki - onkos tuossa peräti 100 miljoonaa!! En tiedä riittääkö koneen kapasiteettikaan... Ehkä huomenna :) Hyvää yötä ja kiitokset selvityksistä :)
rebol[] print "odota" maxluku: 15485863 ;lasketaan Eratostheneen seulalla miljoona ensimmäistä alkulukua alkuluvut: copy[] neliöjuuri: Square-Root maxluku taulukko: array/initial maxluku true; oletetaan kaikki alkuluvuiksi taulukko/(1): false luku: 2 aika1: now/precise for ind luku maxluku luku [ taulukko/(ind): false ;poistetaan 2:n monikerrat ] while [luku < neliöjuuri][ while [(taulukko/(luku) = false) and (luku < neliöjuuri)][ ;etsitään seuraava alkuluku luku: luku + 1 ] for ind (luku + luku) maxluku luku [taulukko/(ind): false] ;poistetaan sen monikerrat luku: luku + 1 ] taulukko/(2): true ;Nyt on taulukoitu miljoonaa ensimmäistä alkulukua. Kirjoitetaan ne blockkiin for i 1 maxluku 1 [ if taulukko/(i) [ append alkuluvut i append alkuluvut " " ] ] write %alkuluvut.txt alkuluvut ;talletetaan blockki aika2: now/precise print ["Aika kului ainoastaan" difference aika2 aika1] halt
jalski kirjoitti:
Segmentoitu versio on varmasti aina nopeampi, koska on äärimmäisen helppo lisätä tuki useammalle säikeelle.
Yhdelläkin säikeellä ajettuna segmentointi nopeuttaa todella paljon, koska puskurin koko voidaan valita prosessorin välimuistin mukaan.
Jos megatavujen kokoista jättitaulukkoa käydään jatkuvasti alusta loppuun läpi, CPU viettää paljon aikaa odotellessa hidasta RAM:ia.
Aihe on jo aika vanha, joten et voi enää vastata siihen.