Kirjautuminen

Haku

Tehtävät

Keskustelu: Koodit: 8th: Alkulukuja vauhdilla

jalski [22.05.2022 20:36:51]

#

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 ;

PetriKeckman [22.06.2022 20:46:43]

#

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.

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

jalski [22.06.2022 22:06:31]

#

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.

PetriKeckman [22.06.2022 22:37:05]

#

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?

jalski [22.06.2022 23:11:21]

#

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".

PetriKeckman [22.06.2022 23:50:08]

#

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

jlaire [23.06.2022 01:24:00]

#

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.

Vastaus

Muista lukea kirjoitusohjeet.
Tietoa sivustosta