Läppärini pystyy varaamaan muistia 2^35 tavua Erastoteleen seulalle. Ensimmäiset 5 alkulukua, jossa aika pienenee. Sitten WinToosa alkaa sekoilla levymuistin kanssa ja sijoittaa suurimman osan taulukosta levylle, jolloin prosessorin tehot tippuvat 2-4 prosenttiin.
Ohessa on taulukkoa seulan alusta, josta näkee, että 11 kodalla seulan tekeminen oli kaikkein nopeinta millisekunneissa.
2 426787 ms 3 316763 ms 5 205235 ms 7 160940 ms 11 120058 ms * 13 132280 ms 17 157291 ms 19 184948 ms 23 197110 ms 29 201836 ms 31 203534 ms 37 207697 ms 41 211903 ms 43 216309 ms 47 222901 ms 53 224245 ms
Onko syyllinen Win10 vai Dev C++:lla tehty ohjelma. Onko Dev C++:ssa jotain projektikohtaisia asetuksia, millä sen saisi optimoitua muistille ja nopeudelle, tai onko WinToosassa jotain asetuksia.
Kaiken järjen mukaan Erastoteleen seulan generoiminen pitäisi nopeutua suhteessa alkuluvun kokoon, koska suuremmalla alkuluvulla askellettuna seulan läpikäynti on nopeampaa - paitsi jos muuttujat sijoitetaan levylle, kuten tässä tapauksessa.
Viidellä ensimmäisellä alkuluvulla ei käytetä levymuistia, mutta sitten alkaa levymuistin käyttö lisääntymään.
Mihin asiaan etsit syyllistä? Kun varaat muistia enemmän kuin koneesta löytyy, tietenkin loput tallennetaan levylle. Millään kääntäjän tai käyttöjärjestelmän asetuksella ei voi korjata oman koodin vikoja. Ohjelman saa optimoitua muistille ja nopeudelle, kun käyttää jotain parempaa algoritmia alkulukujen etsintään.
Voi olla niin päin, että Windows 10 on ”syyllinen” siihen, että ensimmäiset luvut toimivat nopeasti kaikesta huolimatta. Kun sama seulakuvio toistuu melko tiheästi, Windows 10 voi pakata muistia, ettei tarvitse jatkaa levylle. Kun alkulukuja tulee lisää, seulakuvio harvenee ja tehokas pakkaus ei enää onnistu. Tämä on tietysti spekulaatiota, kun Windows 10:n muistinpakkauslogiikasta ei ole tarkkaa tietoa. Netissä kerrotaan, että Tehtävienhallinnasta näkee pakatun muistin määrän ja että pakkauksen voi ottaa pois käytöstä PowerShell-komennolla Disable-MMAgent -mc.
Muistin ja CPU-ajan käytön täydellisen tasapainon etsiminenhän on koko laskentateorian ydinongelma.
Jos sinulla on enemmän muistia ja haluat päästä helpolla, niin työnnät kaiken aiemmin lasketun datan taulukkoon talteen ja säästä CPU-aikaa. Jos sinulla on taas on erittäin tehokas prosessori, niin voit säästää muistia laskemalla kaikki arvot aina uusiksi jokaisella iteraatiolla.
Mikäli sinulla ei ole erityisen paljon kumpaakaan, niin sitten joudut miettimään ihan itse, kuinka käyttää saatavilla olevat resurssit parhaiten. (Nykyaikana riittää myös syöttää kolmesta viiteen huolella valittua sanaa hakukoneeseen.)
Jos ongelman voisi ratkaista yksinkertaisesti napsaisemalla kääntäjästä jonkin vivun päälle, niin ihmiskunta olisi asuttanut puolet tästä galaksista jo 90-luvulla.
Metabolix kirjoitti:
Ohjelman saa optimoitua muistille ja nopeudelle, kun käyttää jotain parempaa algoritmia alkulukujen etsintään.
Olisi mielenkiintoista tietää, mikä tapa tuottaa alkulukuja on nopeampi, kuin Erastoteleen Seula.
Vaikkapa osoitteessa https://www.cs.purdue.edu/homes/hmaji/teaching/
Jaska kirjoitti:
Vaikkapa tapa.
Tuo tapa on yksittäisten (tai muutaman) suuren alkuluvun löytämiseen.
Jone taas hakee kaikkia alkulukuja tiettyyn rajaan asti. Tuo menetelmä ei sovellu siihen hyvin.
jone2712 kirjoitti:
Olisi mielenkiintoista tietää, mikä tapa tuottaa alkulukuja on nopeampi, kuin Erastoteleen Seula.
Erastoteleen seulaa nopeampi on esimerkiksi Atkinin seula. Atkinin seulan nopeus on luokkaa O(N) (jossa N on alkulukujoukon koko) kun Erastoteleen seulan nopeusluokka on O(N log log N)
Myöskin Erastoteleen seulaa voi optimoida toteutuksella joko pienemmälle muistille (bitti per luku) tai pienemmälle CPU-ajalle (muistiosoite per luku)
Olen optimoinut koodin muistille, koska bitin asettaminen tai pyyhkiminen tavusta ei kasvata kovin paljon prosessointiaikaa. Tuo 2^33 vielä menee ilman levymuistia.
#define ByteSize ((int64)1<<33) // tavujen määrä #define BitSize ((int64)ByteSize<<3) // tavujen määrä * 8
Aihe on jo aika vanha, joten et voi enää vastata siihen.