Discussion:
Alkulukujen etsiminen ja etsinnän nopeuttaminen
(too old to reply)
Lasse Liehu
2004-11-30 14:00:34 UTC
Permalink
Niin. Tarkotus olis tehä alkulukuja etsivä ohjelma (harrastus). Kaikki menee
muuten hyvin, mutta nopeus on liian hidas. Ohjelmasta pitäisi saada
nopeampi.

Siis minun käsitykseni mukaan ohjelman pitäisi pystyä etsimään alkulukuja
mahdollisimman pienillä laskutoimitusmäärillä. Osuinko oikeaan? No,
kuitekin. Onko kenelläkään ideoita? Kaikki ideat ovat tervetulleita.

Tiedän tällä hetkellä jo muutamia nopeuttavia asioita:

Testaamalla tutkittavaa arvoa vain luku/2 pienempiä (tai yhtä
suuria) olevia alkulukuja. Samalla voidaan nopeutta saada paremmaksi
testaamalla vain parittomat luvut, koska kaikki parilliset (paitsi 2) eivät
ole koskaan alkulukuja.

Myös katsomalla tutkittavan luvun jakojäännöstä voidaan päätellä tietojeni
mukaan jotain.

Onko siis lisäideoita?

Ohjelmointikieli on C++.

Terveisin,
Lasse Liehu
***@kolumbus.fi

PS: En ole erityisesti koodin optimoimisen kannalla, vaan tekniikan
parantamisen kannalla.
Niko Hälvä
2004-11-30 14:24:01 UTC
Permalink
Moi

Törmäsin tähän nettisivuun pari viikkoa sitten ja siitä luulisi löytyvän
iloa myös sinun alkuluvun metsästykseesi.
http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
Post by Lasse Liehu
Niin. Tarkotus olis tehä alkulukuja etsivä ohjelma (harrastus). Kaikki menee
muuten hyvin, mutta nopeus on liian hidas. Ohjelmasta pitäisi saada
nopeampi.
Siis minun käsitykseni mukaan ohjelman pitäisi pystyä etsimään alkulukuja
mahdollisimman pienillä laskutoimitusmäärillä. Osuinko oikeaan? No,
kuitekin. Onko kenelläkään ideoita? Kaikki ideat ovat tervetulleita.
Testaamalla tutkittavaa arvoa vain luku/2 pienempiä (tai yhtä
suuria) olevia alkulukuja. Samalla voidaan nopeutta saada paremmaksi
testaamalla vain parittomat luvut, koska kaikki parilliset (paitsi 2) eivät
ole koskaan alkulukuja.
Myös katsomalla tutkittavan luvun jakojäännöstä voidaan päätellä tietojeni
mukaan jotain.
Onko siis lisäideoita?
Ohjelmointikieli on C++.
Terveisin,
Lasse Liehu
PS: En ole erityisesti koodin optimoimisen kannalla, vaan tekniikan
parantamisen kannalla.
Jouko Holopainen
2004-11-30 15:12:40 UTC
Permalink
Post by Lasse Liehu
Testaamalla tutkittavaa arvoa vain luku/2 pienempiä (tai yhtä
suuria) olevia alkulukuja.
Kyllä neliöjuuri(luku) on ihan riittävä yläraja.
Post by Lasse Liehu
Samalla voidaan nopeutta saada paremmaksi
testaamalla vain parittomat luvut, koska kaikki parilliset (paitsi 2) eivät
ole koskaan alkulukuja.
Ja hyppäämällä yli kaikki 3:lla ja viidellä jne jaolliset.
--
@jhol

Jotkut pitävät armeijaa parhaana järjestelmänä joissakin tapauksissa.
He ovat oikeassa, armeija on paras järjestelmä Helvetin jälkeen.
Lasse Liehu
2004-11-30 18:57:27 UTC
Permalink
Post by Jouko Holopainen
Post by Lasse Liehu
Samalla voidaan nopeutta saada paremmaksi
testaamalla vain parittomat luvut, koska kaikki parilliset (paitsi 2) eivät
ole koskaan alkulukuja.
Ja hyppäämällä yli kaikki 3:lla ja viidellä jne jaolliset.
Juu, mut...eikös toikin aiheuta turhia laskutoimituksia?
Lasse Liehu
2004-11-30 19:10:05 UTC
Permalink
Post by Lasse Liehu
Post by Jouko Holopainen
Ja hyppäämällä yli kaikki 3:lla ja viidellä jne jaolliset.
Juu, mut...eikös toikin aiheuta turhia laskutoimituksia?
Perun äskeiset puheeni. Toihan voidana hoitaa yksinkertaisella laskurilla.
Jos laskurin arvo on jotain, ohitetaan luku ja siirrytään seuraavaan sekä
tehään laskurille jotain (en vielä jaksa miettiä mitä, riippuu
toteutustavasta).
Juha Laiho
2004-12-01 18:12:33 UTC
Permalink
Post by Lasse Liehu
Post by Lasse Liehu
Post by Jouko Holopainen
Ja hyppäämällä yli kaikki 3:lla ja viidellä jne jaolliset.
Juu, mut...eikös toikin aiheuta turhia laskutoimituksia?
Perun äskeiset puheeni. Toihan voidana hoitaa yksinkertaisella laskurilla.
Jos laskurin arvo on jotain, ohitetaan luku ja siirrytään seuraavaan sekä
tehään laskurille jotain (en vielä jaksa miettiä mitä, riippuu
toteutustavasta).
2:lla ja 3:lla jaolliset saa ohitettua kasvattamalla testattavaa arvoa
vuoronperään 2:lla ja 4:llä. 5:llä jaollisten poiminta menee jo
vaikeammaksi.
--
Wolf a.k.a. Juha Laiho Espoo, Finland
(GC 3.0) GIT d- s+: a C++ ULSH++++$ P++@ L+++ E- W+$@ N++ !K w !O !M V
PS(+) PE Y+ PGP(+) t- 5 !X R !tv b+ !DI D G e+ h---- r+++ y++++
"...cancel my subscription to the resurrection!" (Jim Morrison)
Juho Snellman
2004-12-01 18:58:00 UTC
Permalink
Post by Juha Laiho
Post by Lasse Liehu
Post by Lasse Liehu
Post by Jouko Holopainen
Ja hyppäämällä yli kaikki 3:lla ja viidellä jne jaolliset.
Juu, mut...eikös toikin aiheuta turhia laskutoimituksia?
Perun äskeiset puheeni. Toihan voidana hoitaa yksinkertaisella laskurilla.
Jos laskurin arvo on jotain, ohitetaan luku ja siirrytään seuraavaan sekä
tehään laskurille jotain (en vielä jaksa miettiä mitä, riippuu
toteutustavasta).
2:lla ja 3:lla jaolliset saa ohitettua kasvattamalla testattavaa arvoa
vuoronperään 2:lla ja 4:llä. 5:llä jaollisten poiminta menee jo
vaikeammaksi.
Kirjoitin sattumoisin juuri tuosta aiheesta lukiossa tutkielman (IB:n
extended essay), josta en tosin enää näin 6 vuotta myöhemmin ymmärrä
mitään. Ei tuo kuitenkaan mitenkään suhteettoman vaikeaa ole,
esimerkki kyseisellä optimoinnilla toteutetusta seulasta osoitteessa
<http://cs.helsinki.fi/u/jesnellm/tmp/sieve3.c>, ja tutkielma joka
saattaa selittää miksi/miten tuo toimii osoitteessa
<http://cs.helsinki.fi/u/jesnellm/tmp/sieve.ps>.

[ Em. osoitteet väliaikaisia, poistan nuo parin viikon sisällä. En viitsi
jättää noin hirveää koodia / tekstiä näkyviin pysyvästi, vaikka ne
ovatkin nuoruuden syntejä. :-) ]
--
Juho Snellman
"Premature profiling is the root of all evil."
Lasse Liehu
2004-12-02 05:32:42 UTC
Permalink
Post by Juho Snellman
Kirjoitin sattumoisin juuri tuosta aiheesta lukiossa tutkielman (IB:n
extended essay), josta en tosin enää näin 6 vuotta myöhemmin ymmärrä
mitään. Ei tuo kuitenkaan mitenkään suhteettoman vaikeaa ole,
esimerkki kyseisellä optimoinnilla toteutetusta seulasta osoitteessa
<http://cs.helsinki.fi/u/jesnellm/tmp/sieve3.c>, ja tutkielma joka
saattaa selittää miksi/miten tuo toimii osoitteessa
<http://cs.helsinki.fi/u/jesnellm/tmp/sieve.ps>.
Loistavaa. Jos mäkin nyt sit tajuaisin jotain, niin olis hyvä. Katotaan nyt.
Pitää mennä Linuxiin, kun en tiedä Windowsissa mitään, joka osais
lukee ps-tiedostomuotoa. No, ei voi mitään.
Post by Juho Snellman
[ Em. osoitteet väliaikaisia, poistan nuo parin viikon sisällä. En viitsi
jättää noin hirveää koodia / tekstiä näkyviin pysyvästi, vaikka ne
ovatkin nuoruuden syntejä. :-) ]
Ok. Hyvä vaan, että osoitteet ovat väliaikaisia. Mulla on jo omat kopiot
noista. Kai se on sallittua?
Panu Mantylahti
2004-12-02 08:44:59 UTC
Permalink
en tiedä Windowsissa mitään, joka osais lukee ps-tiedostomuotoa.
Ghostscript, Ghostview ja GSview:
http://www.cs.wisc.edu/~ghost/


-P
--
Thou shalt not follow the Null Pointer,
for at its end Madness and Chaos lie.
Lasse Liehu
2004-12-02 05:34:23 UTC
Permalink
Post by Juha Laiho
2:lla ja 3:lla jaolliset saa ohitettua kasvattamalla testattavaa arvoa
vuoronperään 2:lla ja 4:llä. 5:llä jaollisten poiminta menee jo
vaikeammaksi.
Mä taas vaan käyttäisin yksinkertaista laskuria, jonka avulla (jos sen
arvo olis tietty), niin se olis jaollinen jollakin.
Risto Paasivirta
2004-11-30 15:32:44 UTC
Permalink
Post by Lasse Liehu
Niin. Tarkotus olis tehä alkulukuja etsivä ohjelma (harrastus). Kaikki menee
muuten hyvin, mutta nopeus on liian hidas. Ohjelmasta pitäisi saada
nopeampi.
Siis minun käsitykseni mukaan ohjelman pitäisi pystyä etsimään alkulukuja
mahdollisimman pienillä laskutoimitusmäärillä. Osuinko oikeaan? No,
kuitekin. Onko kenelläkään ideoita? Kaikki ideat ovat tervetulleita.
Minkälaisia alkulukuja? Esimerkiksi bitmappi kaikista
parittomista alkuluvuista <= 10000000 vie alle megatavun,
kaikista 32-bittisistäkin vain 256M. Sen tekee lennostakin
(jos oikein muistan, täytä ensin ykkösbiteillä, parittomille
n >= 3..sqrt(maksimi), nollaa joka n:s bitti, jos (n-1)/2:s
asettunut: ei jakolaskuja!)
Post by Lasse Liehu
Testaamalla tutkittavaa arvoa vain luku/2 pienempiä (tai yhtä
Jos luku ei ole alkuluku, sillä on tekijä joka on pienempi
tai yhtäsuuri kuin luvun neliöjuuri. Siis 32-bit luvuille
tarvii testata vain alkuluvuilla < 65535 saakka, mikä vie
sekunnin murto-osan. (Ja 64-bittisille < 2^32 saakka, missä
ei vielä parta ehdi kasvamaan nykykoneilla.)
Post by Lasse Liehu
Onko siis lisäideoita?
Ohjelmointikieli on C++.
Perus-C++:ssa ei taida olla niin isoa kokonaislukutyyppiä että
sieve alkulukutaulukon/bittikartan kanssa ei riittäisi.
Post by Lasse Liehu
PS: En ole erityisesti koodin optimoimisen kannalla, vaan tekniikan
parantamisen kannalla.
Just. Optimoitu koodi on yleensä hitaampaa kuin optimoitu
algoritmi. (Mutta 2^muutamakymmenen operaatiota saa tehtyä
C++:lla hitaaksikin.)

Risto
--
main(int a,char**b){for(a=atoi(b[1]);printf("%d ",a),a>1;a=a&1?a*3+1:a/2);}
Lasse Liehu
2004-11-30 19:08:25 UTC
Permalink
Post by Risto Paasivirta
Minkälaisia alkulukuja? Esimerkiksi bitmappi kaikista
parittomista alkuluvuista <= 10000000 vie alle megatavun,
kaikista 32-bittisistäkin vain 256M. Sen tekee lennostakin
(jos oikein muistan, täytä ensin ykkösbiteillä, parittomille
n >= 3..sqrt(maksimi), nollaa joka n:s bitti, jos (n-1)/2:s
asettunut: ei jakolaskuja!)
Loistavaa! Vaikka tajuan tällä hetkellä suurinpiirtein vain puolet,
toi kuulostaa hyvältä. Ja mun tarkotus on vaan ettiä ihan
tavallisia alkulukuja alueelta 0 - 2^64. Käyttäjä saa ite
määritellä lukualueen, mut toi on max. Käytän siis 64-bittisiä
kokonaislukuja, jos tarpeen. Muuten käytän (mikäli mahdollista)
pienempiä tyyppejä. Tosin voidaan kuitenkin sanoa, et parillisia
alkulukuja ei tarvi testata. Niitähän on vaan yksi.
Post by Risto Paasivirta
Jos luku ei ole alkuluku, sillä on tekijä joka on pienempi
tai yhtäsuuri kuin luvun neliöjuuri. Siis 32-bit luvuille
tarvii testata vain alkuluvuilla < 65535 saakka, mikä vie
sekunnin murto-osan. (Ja 64-bittisille < 2^32 saakka, missä
ei vielä parta ehdi kasvamaan nykykoneilla.)
Selvennä vähän. Ei paljoo, mut vähän.
Post by Risto Paasivirta
Perus-C++:ssa ei taida olla niin isoa kokonaislukutyyppiä että
sieve alkulukutaulukon/bittikartan kanssa ei riittäisi.
Siis? Voisko tota hiukan selventää?
Post by Risto Paasivirta
Just. Optimoitu koodi on yleensä hitaampaa kuin optimoitu
algoritmi. (Mutta 2^muutamakymmenen operaatiota saa tehtyä
C++:lla hitaaksikin.)
Jaahas. Sä taidatkin olla asioiden expertti?
Tauno Voipio
2004-11-30 20:01:30 UTC
Permalink
Post by Lasse Liehu
Loistavaa! Vaikka tajuan tällä hetkellä suurinpiirtein vain puolet,
toi kuulostaa hyvältä. Ja mun tarkotus on vaan ettiä ihan
tavallisia alkulukuja alueelta 0 - 2^64. Käyttäjä saa ite
määritellä lukualueen, mut toi on max. Käytän siis 64-bittisiä
kokonaislukuja, jos tarpeen. Muuten käytän (mikäli mahdollista)
pienempiä tyyppejä. Tosin voidaan kuitenkin sanoa, et parillisia
alkulukuja ei tarvi testata. Niitähän on vaan yksi.
Lienee todistettu, että nopein alkulukujen haku alusta alkaen on
tuo Eratostheneen seula:

- tehdään bitmappi kaikille luvuille ja täytetään se
- nollataan joka toinen neljästä lähtien
- nollataan joka kolmas kuudesta lähtien
- nollataan joka neljäs kahdeksasta lähtien
- jne, kunnes koko mappi on käyty

Algoritmia on helppo optimoida puoleen ylläolevasta
jättämällä aluksikin bittikarttaan vain parittomat
luvut.

Lisätietoja saa Googlelle 'sieve of eratosthenes'.
--
Tauno Voipio
tauno voipio (at) iki fi
Risto Paasivirta
2004-11-30 21:52:05 UTC
Permalink
Post by Tauno Voipio
Post by Lasse Liehu
Loistavaa! Vaikka tajuan tällä hetkellä suurinpiirtein vain puolet,
toi kuulostaa hyvältä. Ja mun tarkotus on vaan ettiä ihan
tavallisia alkulukuja alueelta 0 - 2^64. Käyttäjä saa ite
määritellä lukualueen, mut toi on max. Käytän siis 64-bittisiä
kokonaislukuja, jos tarpeen. Muuten käytän (mikäli mahdollista)
pienempiä tyyppejä. Tosin voidaan kuitenkin sanoa, et parillisia
alkulukuja ei tarvi testata. Niitähän on vaan yksi.
Lienee todistettu, että nopein alkulukujen haku alusta alkaen on
- tehdään bitmappi kaikille luvuille ja täytetään se
- nollataan joka toinen neljästä lähtien
- nollataan joka kolmas kuudesta lähtien
- nollataan joka neljäs kahdeksasta lähtien
- jne, kunnes koko mappi on käyty
Algoritmia on helppo optimoida puoleen ylläolevasta
jättämällä aluksikin bittikarttaan vain parittomat
luvut.
Ja tehdessä bitmappia ei tarvitse putsata kuin alkuluvut.
Esimerkki sekoittaa enemmän kuin tuhat sanaa:
jätetääm parilliset pois
1357913579135...
1111111111111...
^ 3 alkuluku : nollataan joka 3. alkaen bitistä 2*3.
1111011011011...
^ 5 alkuluku : joka 5. alk. bitistä 2*5.
1111011011010...
^ 7 alkuluku : joka 7. alk 14.
1111011011010... :
^ 9 ei ole alkuluku!
^11 on: joka 11. alk 22.
jne. lukuun neliöjuuri(max.) saakka.
Post by Tauno Voipio
Lisätietoja saa Googlelle 'sieve of eratosthenes'.
Tauno Voipio
Risto
--
main(int a,char**b){for(a=atoi(b[1]);printf("%d ",a),a>1;a=a&1?a*3+1:a/2);}
Jouko Holopainen
2004-12-01 04:20:28 UTC
Permalink
Post by Tauno Voipio
- tehdään bitmappi kaikille luvuille ja täytetään se
- nollataan joka toinen neljästä lähtien
- nollataan joka kolmas kuudesta lähtien
- nollataan joka neljäs kahdeksasta lähtien
Koska luku neljä on jo merkattu k.o. bitmäpissä niin se voidaan
jättää väliin, se ei varmasti merkkaa yhtään lisää.
--
@jhol

Jotkut pitävät armeijaa parhaana järjestelmänä joissakin tapauksissa.
He ovat oikeassa, armeija on paras järjestelmä Helvetin jälkeen.
Aggro
2004-11-30 20:03:55 UTC
Permalink
Post by Lasse Liehu
toi kuulostaa hyvältä. Ja mun tarkotus on vaan ettiä ihan
tavallisia alkulukuja alueelta 0 - 2^64. Käyttäjä saa ite
Tuo taas ei kuulosta hyvältä.

Koska:
2^32 / 2 / 8 / 1024 / 1024 = 256 MB on vielä sellainen mikä PC:n
muistiin mahtuu, mutta

2^64 / 2 / 8 / 1024 / 1024 / 1024 = 1073741824 GB vaatii jo niin paljon
tilaa, että tuskin edes sinulla on niin hienoa konetta, että se sinne
mahtuisi. Eli jos haluat tuon kokoisia lukuja, niin bitmapin saat unohtaa.
Aggro
2004-11-30 20:06:02 UTC
Permalink
Post by Aggro
mahtuisi. Eli jos haluat tuon kokoisia lukuja, niin bitmapin saat unohtaa.
Tai saa sitä siis alkupään luvuille toki edelleen käyttää, jos haluaa,
mutta koko lukuvälille se on käytännössä mahdotonta.
Lasse Liehu
2004-12-01 04:45:42 UTC
Permalink
Post by Aggro
Post by Aggro
mahtuisi. Eli jos haluat tuon kokoisia lukuja, niin bitmapin saat unohtaa.
Tai saa sitä siis alkupään luvuille toki edelleen käyttää, jos haluaa,
mutta koko lukuvälille se on käytännössä mahdotonta.
Juuri näin aionkin tehdä. Alkupään luvuille. Mut onko toi bitmappi sit
nopeempi, kun testata jaollisuus ja tehä jakolaskuja? Ja montako kertaa
nopeempi se sit on?

Ja voisko joku selittää, mikä se tollanen bitmappi on? En meinaan tiedä.
Sampo Smolander
2004-12-01 05:52:30 UTC
Permalink
Post by Lasse Liehu
Ja voisko joku selittää, mikä se tollanen bitmappi on? En meinaan tiedä.
Se on helevetin pitkä jono bittejä.

Jokainen bitti toimii lippuna esittäen sitä lukua, joka saadaan kun
lasketaan että kuinka mones tuo bitti on tuossa jonossa.

Esimerkki: tässä on 16 bittiä pitkä bitmäppi:

1111111111111111

Eka ykkönen on siis luvun 1 lippu, toka ykkönen on luvun 2 lippu, ...,
ja vika ykkönen on luvun 16 lippu. Selkenikö?

Nyt alan käymään tuota bitmäppiä läpi:

(Eka luku, tarkoittaa ykköstä. Joo, ykkönen on alkuluku. Ei nollata
lippua.) Toka luku, joo kakkonen on alkuluku. Ei nollata lippua. Mutta
tästä eteenpäin nollataan joka kahdes lippu, sillä ne ovat jaollisia
kahdella eivätkä siten voi olla alkulukuja. Bitmäppi näyttää operaation
jälkeen tältä:

1110101010101010

Kolmas juku, joo, kolmonen on alkuluku. Mutta tästä eteenpäin nollataan
joka kolmas lippu. Saadaan:

1110101000101000

Neljäs luku, ahaa, sen lippu onkin jo nollattu. Siirrytään
seuraavaan. Paitsi että ei siirrytäkään, sillä 4 on bitmäppimme
pituuden, 16, neliöjuuri, joten homma on valmis.

Tästä bitmäpistä 1110101000101000 voidaan siis lukea että
alkulukuja ovat 1, 2, 3, 5, 7, 11, ja 13.


Onnistuiko selitys, vai selitetäänkö lisää?
Lasse Liehu
2004-12-01 06:18:21 UTC
Permalink
Post by Sampo Smolander
Se on helevetin pitkä jono bittejä.
Okei. Kuinkas pitkä helvetti sit on (vitsi)? Älä vastaa.
Post by Sampo Smolander
Jokainen bitti toimii lippuna esittäen sitä lukua, joka saadaan kun
lasketaan että kuinka mones tuo bitti on tuossa jonossa.
1111111111111111
Eka ykkönen on siis luvun 1 lippu, toka ykkönen on luvun 2 lippu, ...,
ja vika ykkönen on luvun 16 lippu. Selkenikö?
(Eka luku, tarkoittaa ykköstä. Joo, ykkönen on alkuluku. Ei nollata
lippua.) Toka luku, joo kakkonen on alkuluku. Ei nollata lippua. Mutta
tästä eteenpäin nollataan joka kahdes lippu, sillä ne ovat jaollisia
kahdella eivätkä siten voi olla alkulukuja. Bitmäppi näyttää operaation
1110101010101010
Kolmas juku, joo, kolmonen on alkuluku. Mutta tästä eteenpäin nollataan
1110101000101000
Neljäs luku, ahaa, sen lippu onkin jo nollattu. Siirrytään
seuraavaan. Paitsi että ei siirrytäkään, sillä 4 on bitmäppimme
pituuden, 16, neliöjuuri, joten homma on valmis.
Tästä bitmäpistä 1110101000101000 voidaan siis lukea että
alkulukuja ovat 1, 2, 3, 5, 7, 11, ja 13.
Onnistuiko selitys, vai selitetäänkö lisää?
Nooo. Oli toi aika hieno selitys. Ja toi on sit nopeeta?

Eli siis. Eka tehään bitmäppi jokaselle parittomalle luvulle (kun kaikki
alkuluvuthan
on parittomia lukuunottamatta lukua 2). Sit vaan aletaan käymään sitä läpi
(mäppi
varmaan kannattaa alottaa luvusta 3). Katotaan, onko luku 3 nollattu ja jos
ei oo,
on alkuluku. Sit nollataan kaikki 3:lla jaolliset luvut. Sen jälkeen
siirrytään lukuun
5 ja katotaan, onks se nollattu. Jos ei, on alkuluku ja nollataan kaikki
5:llä jaolliset.

Sit mitenkäs toi neliöjuurijuttu menis, kun on vaan parittomat luvut tossa
bitmäpissä?
Ja muuten...kannattaisko toi bitmäppi alottaa 1:stä vai 3:sta?
Aggro
2004-12-01 15:31:15 UTC
Permalink
Post by Lasse Liehu
Sit mitenkäs toi neliöjuurijuttu menis, kun on vaan parittomat luvut tossa
bitmäpissä?
Parilliset luvut poistetaan vain muistin säästämiseksi, sillä
kustannuksella että ne monimutkaistavat ohjelmaa. Sinun pitää huomioida
tämä kaikkialla koodissasi. Esim. kun etsit kolmella jaollisia lippuja,
sinun pitää muistaa, että bitmapista puuttuu parilliset, muuten
nollailet ihan vääriä lukuja vastaavia lippuja.

Eli neliöjuurikysymykseen: älä ajattele bitmapin pituutta, vaan ajattele
lukuväliä mitä tarkastelet. Eli mitä lukua viimeinen lippu edustaa.
Post by Lasse Liehu
Ja muuten...kannattaisko toi bitmäppi alottaa 1:stä vai 3:sta?
Muistin säästön kannalta sillä ei ole niin merkitystä, joten aloita
siitä mikä on sinulle helpointa. Suosittelisin tosin melkein sinua
harjoituksen kannalta tekemään tuon bitmappijutun ensin pienemmillä
luvuilla ja siten että jätät ne parilliset luvut siihen. Koska se on
siten helpompaa.
Lasse Liehu
2004-12-01 15:53:51 UTC
Permalink
Post by Aggro
Parilliset luvut poistetaan vain muistin säästämiseksi, sillä
kustannuksella että ne monimutkaistavat ohjelmaa. Sinun pitää huomioida
tämä kaikkialla koodissasi. Esim. kun etsit kolmella jaollisia lippuja,
sinun pitää muistaa, että bitmapista puuttuu parilliset, muuten
nollailet ihan vääriä lukuja vastaavia lippuja.
Juu...muistetaan.
Post by Aggro
Eli neliöjuurikysymykseen: älä ajattele bitmapin pituutta, vaan ajattele
lukuväliä mitä tarkastelet. Eli mitä lukua viimeinen lippu edustaa.
Eli siis. Jos viimeinen luku on vaikka 4 294 967 296 niin otetaan sen
neliöjuuri. Ok.
Post by Aggro
Muistin säästön kannalta sillä ei ole niin merkitystä, joten aloita
siitä mikä on sinulle helpointa. Suosittelisin tosin melkein sinua
harjoituksen kannalta tekemään tuon bitmappijutun ensin pienemmillä
luvuilla ja siten että jätät ne parilliset luvut siihen. Koska se on
siten helpompaa.
No, voihan sitä kokeilla. Mulla on kevääseen aikaa opetella C++
kunnolla ja tehä tää ohjelma. Mut on mulla opettelemistakin. Pitäis
meinaan vielä opetella graafiset ikkunat ja komponentit sun muut.

Ja oon jo päättäny, et mä alotan sen bitmäpin luvusta 3. Eks oliski
järkevämpi? Ja se on mulle myös tavallaan helpompi.

Monimutkasta tästä vielä tulee, mut antaa tulla vaan. On ainakin
haastetta aloittelevalle ohjemoijalle (jes!). Ainoat mahdolliset ongelmat
ohjelmaa tehdessä tulevat olemaan mun laiskuus ja mielenkiinnon
katoaminen (epätodennnäk.).
Risto Paasivirta
2004-11-30 22:14:08 UTC
Permalink
In article <coigf8$por$***@phys-news1.kolumbus.fi>,
Lasse Liehu <***@saunalahti.fi> wrote:
(sievestä edellisessä)
Post by Lasse Liehu
Post by Risto Paasivirta
Jos luku ei ole alkuluku, sillä on tekijä joka on pienempi
tai yhtäsuuri kuin luvun neliöjuuri. Siis 32-bit luvuille
tarvii testata vain alkuluvuilla < 65535 saakka, mikä vie
sekunnin murto-osan. (Ja 64-bittisille < 2^32 saakka, missä
ei vielä parta ehdi kasvamaan nykykoneilla.)
Selvennä vähän. Ei paljoo, mut vähän.
Siitä, että p <= q tai q <= p, seuraa että
p <= sqrt(p*q) tai q <= sqrt(p*q)
Post by Lasse Liehu
Post by Risto Paasivirta
Perus-C++:ssa ei taida olla niin isoa kokonaislukutyyppiä että
sieve alkulukutaulukon/bittikartan kanssa ei riittäisi.
Siis? Voisko tota hiukan selventää?
Jos haluat isompia kuin unsiged long long kokonaislukuja,
tarvit kirjaston joka toteuttaa semmoisen tyypin, kun sitä
ei ole C++:ssa valimiina. Ja unsiged long long luvun jakaa
tekijöihin raakasti paukuttamallakin.
Post by Lasse Liehu
Post by Risto Paasivirta
C++:lla hitaaksikin.)
Jaahas. Sä taidatkin olla asioiden expertti?
C++ on kyllä hiuk ruosteessa, en saanut vielä toimimaan
ohjelmaani, joka tekee jokaista bittikartan bitin vitkau-
tusta varten bittiolion... (ihan vain halusin tietää
_kuinka_ hidasta se olisi... ;-) )

Risto
--
main(int a,char**b){for(a=atoi(b[1]);printf("%d ",a),a>1;a=a&1?a*3+1:a/2);}
Joel Yliluoma
2004-12-07 10:39:37 UTC
Permalink
Post by Risto Paasivirta
C++ on kyllä hiuk ruosteessa, en saanut vielä toimimaan
ohjelmaani, joka tekee jokaista bittikartan bitin vitkau-
tusta varten bittiolion... (ihan vain halusin tietää
_kuinka_ hidasta se olisi... ;-) )
STL:ssä on tosin sellainenkin kuin std::bitset<num_bits>.
Säästää toteutusvaivan.

http://www.google.fi/search?q=bitset+stl&btnI=1
--
Joel Yliluoma - http://bisqwit.iki.fi/
: comprehension = 1 / (2 ^ precision)
Kai Nikulainen
2004-11-30 17:39:19 UTC
Permalink
Käytä Javan luokkaa BigInteger (
http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html )
ja sen metodia nextProbablePrime, joka palauttaa seuraavan todennäköisen
alkuluvun. Omalla algoritmillasi voit sitten tarkistaa onko ehdokas tosiaan
alkuluku. Näin et tule kuluttaneeksi aikaa todennäköisesti turhien
ehdokkaiden testaamiseen.

Kaitsu
Lasse Liehu
2004-11-30 18:56:58 UTC
Permalink
Post by Kai Nikulainen
Käytä Javan luokkaa BigInteger (
http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html )
ja sen metodia nextProbablePrime, joka palauttaa seuraavan todennäköisen
alkuluvun. Omalla algoritmillasi voit sitten tarkistaa onko ehdokas tosiaan
alkuluku. Näin et tule kuluttaneeksi aikaa todennäköisesti turhien
ehdokkaiden testaamiseen.
Mut miten ton algoritmin sais C++ kielelle? Kun mä en osaa yhtään Javaa.
Pitäis kyllä
joskus vielä opetella (ja tehä paljon muutakin).

Mut toi on tavallaan just sitä, mitä haen takaa. Mut toi Ristonkin vastaus
on tosi hyvä.
Saa nähdä, mitä tekniikoita tulen käyttämään.
Risto Paasivirta
2004-11-30 21:19:47 UTC
Permalink
Post by Kai Nikulainen
Post by Kai Nikulainen
Käytä Javan luokkaa BigInteger (
http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html )
ja sen metodia nextProbablePrime, joka palauttaa seuraavan todennäköisen
alkuluvun. Omalla algoritmillasi voit sitten tarkistaa onko ehdokas
tosiaan
Post by Kai Nikulainen
alkuluku. Näin et tule kuluttaneeksi aikaa todennäköisesti turhien
ehdokkaiden testaamiseen.
Mut miten ton algoritmin sais C++ kielelle? Kun mä en osaa yhtään Javaa.
Tarvitset sopivan kirjaston. Vaikka gmp (google gmp). Niita
on paljon muitakin.
Post by Kai Nikulainen
Saa nähdä, mitä tekniikoita tulen käyttämään.
Esimerkiksi Handbook of Applied Cryptography, (google hac)
luku 4 käsittelee mm. alkulukujen löytämistä. Oma suosikkini
alkulukujen kehittämiseen on 4.62 Maurerin algoritmi: about
yhtä nopea kuin todennäköisten alkulukujen etsiminen, mutta
tekee todistettuja alkulukuja.

Risto
--
main(int a,char**b){for(a=atoi(b[1]);printf("%d ",a),a>1;a=a&1?a*3+1:a/2);}
Lasse Liehu
2004-12-01 04:54:45 UTC
Permalink
Post by Risto Paasivirta
Tarvitset sopivan kirjaston. Vaikka gmp (google gmp). Niita
on paljon muitakin.
Ok. Täytyy kattoa, jos tota todennäköisyysjuttua tarvin.
Post by Risto Paasivirta
Esimerkiksi Handbook of Applied Cryptography, (google hac)
luku 4 käsittelee mm. alkulukujen löytämistä. Oma suosikkini
alkulukujen kehittämiseen on 4.62 Maurerin algoritmi: about
yhtä nopea kuin todennäköisten alkulukujen etsiminen, mutta
tekee todistettuja alkulukuja.
Jaahas. Tekniikoita siis löytyy. Nyt vaan pitäis löytää nopein tekniikka,
jota käyttää. Onko toi noiden muiden selittämän bitmappitekniikka
nopeempi. Jos on, niin tuun käyttään sitä siihen saakka, kunnes loppuu
muisti ja sit jotain toista nopeeta tekniikkaa, joka ei kuluta paljoo
muistia.

Eli siis. Onko toi sun mainitsema Maurerin algoritmi nopeekin? Siis voikko
antaa noin arvion, et montako alkulukua se käy läpi sekunnissa. Ja jos
nopeus hidastuu lukujen kasvaessa, mainitse myös siitä.
Risto Paasivirta
2004-12-01 08:32:11 UTC
Permalink
Post by Lasse Liehu
Eli siis. Onko toi sun mainitsema Maurerin algoritmi nopeekin? Siis voikko
Samaa luokkaa kuin Miller-Rabin testi. Käytännöllinen
tuhansien bittien pituisten alkulukujen tekemiseen.
Post by Lasse Liehu
antaa noin arvion, et montako alkulukua se käy läpi sekunnissa. Ja jos
nopeus hidastuu lukujen kasvaessa, mainitse myös siitä.
http://groups.google.com/groups?selm=cai1sm%248cg%241%40nemesis.co.jyu.fi

Höh, tietysti nopeus hidastuu. Leiki ja mittaa. Käytännöllisyys
riippuu siitä, kuinka suuria alkulukuja tarvitset ja mihin
tarkoitukseen. Satabittisiin ei paljoa aikaa hurahda, parinkymmenen
miljoonan bittisen Mersennen luvun testaaminen Lucas-Lehmer testillä
kestää kuukausia (nopealla toteutuksella).

Risto
--
main(){char*a="main(){char*a=%c%s%c;printf(a,34,a,34);}";printf(a,34,a,34);}
Loading...