Itse olen tyytyväinen seuraavaan tulokseen. Miten lienevät muut.
Tehtävänä oli laskea Eratostheneen seulan avulla taulukko, joka ilmoittaa kahdesta lähtien mikä on alkuluku ja mikä jaollinen luku. Lasku ulottui 4 miljardiin saakka (siihen saakka siksi, että taulukon lasku on suoritettu assemblerilla ja 2^32 on vain vähän yli 4 mljrd). Vasta ostetulla, tavallisella tietokoneella taulukon laskenta-aika on 75 sekuntia. Vanhalla koneella (3.5 v vanha) aikaa menee 200 sekuntia.
Jos joku haluaa tehdä tarkistuksen, niin välillä (2,4*10^9) pitäisi olla 189961812 alkulukua, ja viimeinen ennen päätepistettä on 3999999979. Alkulukupareja on samalla välillä 11944438 kpl. Tapauksia, jossa 4:n etäisyydellä alkuluvusta on alkuluku (esim 13,...,17) on 11946708 kpl (siis melkein sama määrä kuin alkulukuparejakin).
Tehtävänä oli laskea Eratostheneen seulan avulla taulukko, joka ilmoittaa kahdesta lähtien mikä on alkuluku ja mikä jaollinen luku. Lasku ulottui 4 miljardiin saakka (siihen saakka siksi, että taulukon lasku on suoritettu assemblerilla ja 2^32 on vain vähän yli 4 mljrd). Vasta ostetulla, tavallisella tietokoneella taulukon laskenta-aika on 75 sekuntia. Vanhalla koneella (3.5 v vanha) aikaa menee 200 sekuntia.
Jos joku haluaa tehdä tarkistuksen, niin välillä (2,4*10^9) pitäisi olla 189961812 alkulukua, ja viimeinen ennen päätepistettä on 3999999979. Alkulukupareja on samalla välillä 11944438 kpl. Tapauksia, jossa 4:n etäisyydellä alkuluvusta on alkuluku (esim 13,...,17) on 11946708 kpl (siis melkein sama määrä kuin alkulukuparejakin).
Vastaukset 5
Vanhimmat
Eli siis tulisiko ohjelman tehdä nuo kaikki tarkistuksetkin vai vain laskea alkuluvut 2^32 alueelta?
*epätietoinen*
Alkulukutaulutaulukon laskentaan menee mainittu aika. Kun se on laskettu, voi taulukkoa selata haluamastaan kodasta (selausohjelma näyttää taulukon graafisessa muodossa, koska pelkkinä lukuina ilmaistuna esitys ei olisi mitenkään havainnollinen). Ohjelma sisältää toimintoja, joilla voi laskea alkulukujen määrän, alkulukuparien tai muiden 'konfiguraatioiden' määrän jollakin alueeseen (2,4 mljrd) kuuluvalla välillä. Näiden lukumäärien laskenta-aika on n. 10 sekuntia (riippuu käytössä olevasta koneesta). Voi sillä tutkia myös Goldbachin väittämää, ja heti silmään pistää eräs kummallisuus.
Pistin 3 viikkoa sitten näitä ohjelmia internettiin ja näyttävät ne sinne ilmestyneen. Mutta jos näitä ohjelmia käyttää netin kautta, niin alkajaisiksi tulee ilmoitus suunnilleen että 'Jotkin ohjelmat voivat olla vaaraksi koneelle'. Jos kuitenkin 'Avaa' ohjelman, se lähtee käyntiin. (Uudessa tietokoneessa tulee kaksikin boksia). Olen näitä ohjelmia käyttänyt kokeeksi internetin välityksellä ja näyttävät kyllä ainakin toimivan. Itse nettisivuun viittaaminen ei aiheuta varoitusta, mutta varsinaisen sivulle sisältyvän ohjelman käyttö aiheuttaa. Jos ohjelmat pistää esim. CD-levylle ja käyttää niitä sieltä ei varoitusta tule. Näitä ohjelmia olen parin vuoden aikana tehnyt ja niitä paljon käyttänyt. Muuta en pysty sanomaan.
bsdgames-paketti sisältää C:llä kirjoitetun primes-ohjelman, joka luettelee alkuluvut myös Eratostheneen seulan avulla. Paketti on saatavissa monesta paikasta, mutta esimerkiksi täältä:
http://gentoo.osuosl.org/distfiles/bsd-games-2.17.tar.gz
Lukujen käyminen 2^32-1:een asti käy Linuxissa komennolla
primes 2 4294967295 >/dev/null
ja se kestää
- 56 sekuntia 2,1 GHz:n Core 2 Duolla
- 99 sekuntia 1,8 GHz:n Athlon XP:llä
- 111 sekuntia 1,5 GHz:n Pentium M:llä
mutta suuri osa ajasta kuluu tulostukseen (esim. Pentium M:llä tulostettavaa dataa kertyy n. 18 Mt/s). Jos löydettyjen lukujen tulostaminen jätetään pois, Pentium M:n suoritusaika putoaa 111 sekunnista 35 sekuntiin.
Suosittelen tutustumaan paketin sisällä primes-alihakemistossa olevaan primes.c-tiedoston koodiin. Luultavasti siellä on jokin optimointi, jota et vielä huomannut, ja jonka avulla saat omasta toteutuksestasi entistä nopeamman.
Tällaisen pikaisen asiaan tutustumisen perusteella vaikuttaa siltä, että sinulla on hyvä syy olla tyytyväinen toteutukseesi jo nyt.
Wikipedian mukaan Eratostheneen seulassa algoritmin ensimmäinen askel on kirjoittaa taulukkoon luvut kakkosesta viimeiseen testattavaan lukuun asti.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Jos taulukkoon laitetaan luvut 2, 3..., 2^32-1 ja jokainen luku esitetään 32 bittisenä etumerkittömänä kokonaislukuna (tilaa käytetään neljä tavua per luku), taulukko vie muistia yhteensä noin (2^32)*4/1024/1024/1024 = 16 gigatavua.
Hyvin varustellussa kotikoneessa saattaa olla 4 gigatavua muistia, joten loput 12 gigatavua käyttöjärjestelmä joutuisi kirjoittamaan levylle. Hyvin varusteltu kotikone pystyy kirjoittamaan levylle n. 60 Mt/s, joten pelkästään tuon 12 gigatavun kirjoittaminen kestää 204 sekuntia.
Tällä perusteella arvaan, ettet muodostanut 4 miljardin luvun pituista taulukkoa, niin kuin Eratostheneen seulassa tehdään. Käytitkö ehkä jotain muuta algoritmia? Vai käytitkö erilaista taulukkoa? Luulen, että 1 bitti/luku riittää, jos algoritmia muutetaan vähän. Näin muistintarve jäisi 512 megatavuun, mikä saattaisi löytyä 3,5 vuotta vanhasta koneestakin.
Tämä ohjelma tekee juuri sen mistä alussa mainitset, eli muodostaa 4 mljrd saakka ulottuvan jaollisuustaulukon. Ja menetelmä on se mistä loppukappaleessa mainitset, eli yhtä lukua koskeva tieto jaollisuudesta tallennetaan yhden muistipaikan yhteen bittiin (0 vastaa jaotonta lukua ja 1 jaollista). Parillisia lukuja ei tarvitse ottaa huomioon, koska vain 2 on alkuluku. Siis tarvitaan 4*10^9/16 (=250 Megaa) muistia itse taulukkoon. Sen lisäksi vielä jonkinverran ohjelmaan ja Windowsiin. Koneessa, jolla ohjelma on tehty, on 512 Megaa muistia. Periaatteena se on Eratostheneen seula, laskenta on suoritettu muistipaikat 'pilkkomalla'.
Tämä ohjelma (ja muitakin) on pantu nettiin ja löytyy esim. Google.fi hakusanalla 'Goldbachin väittämä' siinä 3:s juttu 'Matematiikkaan liittyviä ohjelmia'. Jos sitten ohjelmia arvaa mennä käyttämään ! On otettu aina monta kokoversiota eri ohjelmista, ja jos kone ei ole aivan uusi, saattaa olla paras aloittaa pienimmästä versiosta, muuten laskenta-aika voi olla minuutteja suurimmissa versioissa. Suurimmassa alkulukuversiossa koneen muistin on oltava vähintään 512 Megaa, ei toimi pienemmällä enkä tiedä mitä tapahtuu jos kuitenkin yrittää käyttää.