alkulukualgoritmi
Jarmo N.
vai ei? (vähiten tietokoneaikaa vievä).
Itselläni mielessä seuraava yksinkertainen algoritmi:
1)lasketaan onko luku jaollinen 2:lla
2)lasketaan onko joku luku jaollinen 3:lla
3)jatketaan kunnes tullaan lukuun, joka on tutkittava luku jaettuna kahdella
(enää on turha laskea, koska luku ei ole tietenkään jaollinen toisella
luvulla, jonka arvo on
yli puolet alkuperäisestä luvusta). Miten laskentaa voi vielä tehostaa? Onko
olemassa yksinkertaisia operaatioita millä voidaan tarkastaa automaattisesti
onko joku luku jaollinen vai ei ( laskematta raa'asti )?
Hannu Koskenvaara
"Jarmo N." wrote:
>
> Mikä on paras tapa laskea, onko joku (pienehkö, alle miljoona) luku alkuluku
> vai ei? (vähiten tietokoneaikaa vievä).
> Itselläni mielessä seuraava yksinkertainen algoritmi:
> 1)lasketaan onko luku jaollinen 2:lla
> 2)lasketaan onko joku luku jaollinen 3:lla
Tuo toimii ihan hyvin miljoonan kokoisilla luvuilla. En sitten tiedä,
että onko se ehdottomasti nopein olemassaoleva tapa. Jos ohjelmassa voi
taulukoida alkulukuja, kannattaa tietenkin kokeilla jakaa vain niillä.
> 3)jatketaan kunnes tullaan lukuun, joka on tutkittava luku jaettuna kahdella
> (enää on turha laskea, koska luku ei ole tietenkään jaollinen toisella
> luvulla, jonka arvo on
> yli puolet alkuperäisestä luvusta). Miten laskentaa voi vielä tehostaa? Onko
> olemassa yksinkertaisia operaatioita millä voidaan tarkastaa automaattisesti
> onko joku luku jaollinen vai ei ( laskematta raa'asti )?
Riittää, kun kokeilet jakajia testattavan luvun neliöjuureen asti. Jos
luvun joku tekijä on suurempi kuin luvun neliöjuuri, muiden tekijöiden
tulo on luvun neliöjuurta pienempi ja paljastaa luvun jaolliseksi
testauksen aikaisemmassa vaiheessa.
Hannu Koskenvaara
Jori Mantysalo
> Mikä on paras tapa laskea, onko joku (pienehkö, alle miljoona) luku alkuluku
> vai ei? (vähiten tietokoneaikaa vievä).
Onko tehtävänä "onko luku 1234 alkuluku" vai "tulosta alkuluvut väliltä
1-1234"? Vaikka viimeksimainittu on erittäin yksinkertainen ratkaista,
kun tiedetään ratkaisu ensinmainittuun, on näin saatava algoritmi paljon
hitaampi. Vai halutaanko tietää esimerkiksi mitkä sadasta satunnaisesta
luvusta väliltä 1-1000000 ovat alkulukuja?
> Itselläni mielessä seuraava yksinkertainen algoritmi:
> 1)lasketaan onko luku jaollinen 2:lla
> 2)lasketaan onko joku luku jaollinen 3:lla
> 3)jatketaan kunnes
Parillisia lukuja on turha testata, pl. tietysti kahdella jaollisuus.
Testausta nopeuttaa, jos esimerkiksi sata ensimmäistä alkulukua on valmiiksi
taulukoitu. Tällöin voidaan kokeilla ensin näillä jakamista, eikä turhaan
tarvitse kokeilla jakamista luvulla 25 sen jälkeen kun on todettu että luku
ei ole luvulla 5 jaollinen.
Teen itse jatkokysymyksen: jos ohjelma saa syötteenä N satunnaisesti
valittua lukua väliltä 1-M, ja ohjelman tulee mahdollisimman nopeasti
kertoa mitkä syötteen luvuista ovat alkulukuja, niin miten pitkälle
ohjelman kannattaa ensin laskea pienimpiä alkulukuja valmiiksi taulukkoon?
Oletetaan, että mitataan keskimääräistä suoritusaikaa, ja että ohjelma ei
saa sisältää valmista alkulukutaulukkoa.
--
- "Peppi Pitkätossu on tosi vahva. Se jaksaa nostaa sinutkin."
- "Se on sitten varmaan syönyt joka aamu kaurapuuroa."
- "Nii-in. Ja saanut joka päivä jäätelön!"
-- Eerika, ovela nelivuotias
jj
Jarmo N. wrote in message ...
Mielenkiintoinen (ei tehokas suurille luvuille) tapa testata onko luku n
alkuluku vai ei on käyttää Wilsonin lausetta:
Luonnollinen luku n on alkuluku silloin ja vain silloin kun
(n-1)!+1=0 (mod n)
Valitettavasti (n-1)! on laskennollisesti hankala suurilla n:n arvoilla.
Toinen mielenkiintoinen tapa on käyttää Fermat'n pikkulausetta:
Jos n on alkuluku ja a on n:llä jaoton, niin
a^(n-1)=1 (mod n) (*)
Voidaan valita a=2 (tai jokin muu luku) ja testata onko kongruenssi yhtälö
(*) voimassa. Jos se ei ole, niin automaattisesti n on tällöin yhdistetty
luku. Valitettavasti on olemassa yhdistettyjä lukuja n (pseudoalkulukuja),
jotka toteuttavat yhtälön (*).
Terveisin, Jake
Mika R S Kojo
"Jarmo N." <ja...@yahoo.com> writes:
> Mikä on paras tapa laskea, onko joku (pienehkö, alle miljoona) luku
> alkuluku vai ei? (vähiten tietokoneaikaa vievä).
Pyydät aika paljon. Jos pyytäisi parasta asymptoottisessa mielessä
asia olisi selvä, mutta nyt pitäisi pystyä laskeamaan menetelmien
toteutusten täsmällisiä kompleksisuuksia. Tämä lisäksi riippuu
valtavasti esimerkiksi siitä missä laitteessa ne toteutetaan.
> Onko olemassa yksinkertaisia operaatioita millä voidaan tarkastaa
> automaattisesti onko joku luku jaollinen vai ei ( laskematta
> raa'asti )?
On olemassa yksinkertaisia operaatioita, joilla voi tarkistaa onko
joku luku jaollinen. Hieman monimutkaisempia, joilla todistaa että se
ei ole.
Yksinkertaisin esimerkki. Fermat'n pieni lause (tai alkeellinen
ryhmäteoria) sanoo
a^(p-1) == 1 (mod p),
jos p on alkuluku ja 0 < a < p. Täten se oleellisesti sanoo, että jos
a^(p-1) /= 1 (mod p) niin silloin p on jaollinen epätriviaaleihin
tekijöihin. Tässä a'n voi valita vapaasti annetulta väliltä, mutta a =
1 tai a = p - 1 eivät anna epätriviaalia tietoa (siis oleellisesti
haluat valita 1 < a < p - 1).
Tämän testin (naiivi) kompleksisuus on O((log p)^3). Siis tämä vaatii
naiivisti toteutettuna c.(log p)^3 operaatiota, jossa c on jokin
vakio. Nyt siivilä vaatii naiivisti toteutettuna d.Sqrt(p)
operaatiota, jossa d on jokin vakio. Täten halutaan
c.6^3 < d.1000,
siis jos pätee
c/d < 1000/216
niin Fermat'n pieni lause voi auttaa. Tässä c,d riippuvat
toteutuksesta, laitteistosta, käytetystä ohjelmointikielestä, sen
kääntäjästä, tuulen suunnasta ja paikastamme maailmankaikkeudessa. Tai
ehkä ei noista kahdesta viimeisestä.
Tälläiset vakiot alkavat menettää merkitystään kun tutkittavat luvut
kasvavat tarpeeksi suuriksi. Mutta ehkä miljoonan tietämillä niitä ei
voi täysin unohtaa.
Mika
Risto Paasivirta
Jarmo N. <ja...@yahoo.com> wrote:
>Mikä on paras tapa laskea, onko joku (pienehkö, alle miljoona) luku alkuluku
>vai ei? (vähiten tietokoneaikaa vievä).
>Itselläni mielessä seuraava yksinkertainen algoritmi:
>1)lasketaan onko luku jaollinen 2:lla
>2)lasketaan onko joku luku jaollinen 3:lla
>3)jatketaan kunnes tullaan lukuun, joka on tutkittava luku jaettuna kahdella
>(enää on turha laskea, koska luku ei ole tietenkään jaollinen toisella
>luvulla, jonka arvo on
Tarkistat että luku ei ole jaollinen 2:lla eikä parittomilla luvuilla
luvun neliöjuureen saakka. Jos tarvitsee testata paljon pieniä lukuja
kannattaa tehdä etukäteen taulukko/bittikartta alkuluvuista <= maksimi-
luvun neliöjuuri ja tarkistaa niillä.
>yli puolet alkuperäisestä luvusta). Miten laskentaa voi vielä tehostaa? Onko
>olemassa yksinkertaisia operaatioita millä voidaan tarkastaa automaattisesti
>onko joku luku jaollinen vai ei ( laskematta raa'asti )?
On olemassa suhteellisen yksinkertaisia operaatioita, joilla voi
todistaa, että luku _ei_ ole alkuluku. (Todistuksen epäonnistuessa
on suuri todennäköisyys, että luku on alkuluku.) On myös algoritmeja,
joilla voidaan tehdä haluttua suuruusluokkaa olevia alkulukuja. Luvun
todistaminen alkuluvuksi, jos se on niin suuri että testi alkuluvuilla
luvun neliöjuureen saakka ei ole käytännöllinen, on monimutkaisempaa.
Pienillä luvuilla, esm. luokkaa 2^32, raaka voima on nopein tapa:
2^16 yksikköä työtä vie sekunnin murto-osan pöytä-PC:llä.
Risto
Risto Paasivirta
Risto Paasivirta <r...@horus.co.jyu.fi> wrote:
>In article <a96ftt$f0q$1...@phys-news1.kolumbus.fi>,
>Jarmo N. <ja...@yahoo.com> wrote:
>>Mikä on paras tapa laskea, onko joku (pienehkö, alle miljoona) luku alkuluku
>>vai ei? (vähiten tietokoneaikaa vievä).
>kannattaa tehdä etukäteen taulukko/bittikartta alkuluvuista <= maksimi-
>luvun neliöjuuri ja tarkistaa niillä.
Ja sitäpaitsi jos luvut ovat <= 100000 ja niitä on paljon ja on tosi
kiirus, niin kannattaa tehdä bittikartta niistä kaikista; C:llä:
#include <math.h>
#define maxtest 1000000
unsigned char primebitmap[maxtest/8+1];
int is_prime(int x)
{
return (primebitmap[x / 8] & (1 << (x % 8)));
}
void init_primebitmap()
{
int i, j, l;
for (i = 0; i < maxtest/8+1; i++)
primebitmap[i] = 0xFF;
l = (int)(sqrt((double)maxtest)+1);
for (i = 2; i < l; i++)
if (is_prime(i))
for (j = i; (j += i) < maxtest;)
primebitmap[j / 8] &= ~(1<< (j % 8));
}
so. kutsu ensin init_primebitmap() kerran, testaa is_prime(luku)
En kokeillut kääntää enkä testannut. Bittikartan koko pitäisi
tässä olla vain noin 122 kilotavua. (Parilliset luvut voi optimoida
pois, jolloin koko puolittuu ja bittikartan voi toki tehdä valmiiksi
ja kääntää mukaan ohjelmaan. HT.)
Risto
Tuomas Yrjövuori
>
> Mikä on paras tapa laskea, onko joku (pienehkö, alle miljoona) luku alkuluku
En tiedä mikä on paras tapa, mutta tässä omat versioni:
<URL: http://www.hut.fi/u/tpyrjovu/primes.c>
<URL: httP://www.hut.fi/u/tpyrjovu/factors.c>
Ensimmäinen listaa alkulukuja kolmosesta alkaen (kakkosen puuttuminen on
virhe - kyllä). Se testaa vain parittomat luvut. Testifunktiota en
laittanut edelliseen keskusteluun viitaten vieläkään (erinäisistä
syistä) terminoitumaan neliöjuuri n:ään. Sen voi siihen lisätä ja
kellottaa ohjelman ajoa jos kiinnostaa.
Jälkimmäinen listaa luvun tekijät. Mikäli luku on alkuluku, se listaa
vain tämän kyseisen luvun.
* Kyhäelmät toimivat vain unsigned long -luvuilla. *
Joku ohjelmointia oikeasti osaava voisi kokeilla laajentaa ensimmäistä
versiota Erastotheneen seulaksi ja kokeilla kellottaa ohjelman ajoa
todetakseen hyödyttääkö tämä. Minä en sitä kokeillut.
--
T. Yrjövuori
Kimmo Laine
viestissä:3CBAB3DB...@cc.hut.fi...
Tuo koodi primes.c vaikutti todella kummalliselta, mutta jätettäköön
kommentoimatta sen kummemmin kun en ole testannut toimiiko se. Varmastikin
toimii, mutta on sen verran hankala lukea että heti ei hoksaa mistä on
kysymys. Esim se, että funktio osaa palauttaa ainoastaan nollan herättää
hämmäennystä. Jos vaihtoehtoina on että arvon palauttava funktio on
palauttamatta arvoa tai palauttaa nollaan, on hämmästyttävää että se voisi
koskaan palauttaa nollasta poikkeavan totuusarvon, mutta ilmeisesti näin
kuitenkin on. Lisäksi olisi kiva tietää mihin perustuu silmukan
pysäyttäminen arvoon (number/2+2).
No, oli miten oli, tässä kuitenkin minun ratkaisuni javascriptillä. Sen
pitäisi olla aika selkokielinen muutamaa javascriptille ominaista seikkaa
lukuunottamatta.
function prime(x)
{
var limit=0;
var div=2;
var x_limit = Math.sqrt(x);
while (x%div!=0 && div<x_limit)
{
div++;
}
is_prime = !(x%div==0 && x!=div);
return is_prime;
}
Tässä ei julisteta muuttujille sen kummemmin tyyppejä, ne ovat vain
variableja, (esim. var x). Math.sqrt(x) palauttaa x:n neliöjuuren. Ja ihan
perustellusti kyllä, en näe mitään ongelmaa siinä etteikö silmukkaa voisi
päättää siihen. En ole lukenut keskustelua johon viittaat, koska ei ollut
mitään referenssiä, joten anteeksi jos nyt kusen jonkun kukkasille.
Ilmeisesti edellisestä versiosta poiketen tämä hoitaa arvon palautuksen myös
arvoille 0,1 ja 2, palauttaen nollan kahdella ensimmäisellä, ykkösen
jälkimmäisellä, muistaakseni.
--
_ _
______/(.)(.)\_______________________________
Kimmo "Soulman" Laine kklaine at surfeu.fi
http://members.surfeu.fi/kklaine/main.html
"My God, it's full of stars!" - David Bowman
Tuomas Yrjövuori
>
> variableja, (esim. var x). Math.sqrt(x) palauttaa x:n neliöjuuren. Ja ihan
> perustellusti kyllä, en näe mitään ongelmaa siinä etteikö silmukkaa voisi
> päättää siihen. En ole lukenut keskustelua johon viittaat, koska ei ollut
Henkilökohtainen syyni neliöjuuren poisjättämiseen oli se, että en
saanut neliöjuurifunktiota toimimaan. Eräs muista syistä voisi olla
vaikka se, että en ole vielä kuullut riittäviä perusteluja sen käyttöön.
Monet gurut ovat minusta järjestelmällisesti unohtaneet sen, että
neliöjuuren laskeminenkin tuottaa kompleksisuutta. Mikä on C:n
sqrt-funktion kompleksisuus? Älkääkä vain sanoko että se on neliöjuuri
n. Toki sqrt-funktion kompleksisuus olisi pienempi (?) kuin puolikkaan
testi-funktioni kompleksisuus, mutta minusta on eduksi jos voi pelata
kokonaisluvuilla. Tällöin pseudonomaisesti käyttämäni koodinpätkän
porttaaminen vaikka assemblerille olisi helpompaa. Älkääkä vain sanoko,
että nykyajan hienot pentiumit laskevat neliöjuuria yhdessä
kellojaksossa (vaikka se olisikin totta).
Eräs tapa luoda, terminointikohta testifunktiolle, voisi olla
Erastotheneen seulalla luodun taulukon suurimman alkuluvun käyttäminen
jakajana testifunktiossa tyyliin "number / suurin tunnettu alkuluku + 2"
tai jotain sinne päin. Tämäkään ei varmastikaan olisi järkevää, mutta
toimisi vielä näin pienillä luvuilla.
Toki olen ollut laiska, kun en ole kokeillut kaikkia mahdollisia tapoja.
Näin aion kyllä vielä tehdä. Koska en ole vielä tarpeeksi teoreettisella
tasolla ajattelussani, niin kokeilen mieluummin monia eri versioita
kompleksisuuksien laskemisten sijaan. Minusta Mika Kojo totesi erittäin
mainiosta, että kompleksisuudet riippuvat myös käytettävästä alustasta.
Minä aion henkilökohtaisesti unohtaa niiden laskemiset siihen asti
kunnes olen saavuttanut tarpeellisen tietojenkäsittelynteorian tason.
--
T. Yrjövuori
Hannu Koskenvaara
Tuomas Yrjövuori wrote:
>
> Kimmo Laine wrote:
> >
> > variableja, (esim. var x). Math.sqrt(x) palauttaa x:n neliöjuuren. Ja ihan
> > perustellusti kyllä, en näe mitään ongelmaa siinä etteikö silmukkaa voisi
> > päättää siihen. En ole lukenut keskustelua johon viittaat, koska ei ollut
>
> Henkilökohtainen syyni neliöjuuren poisjättämiseen oli se, että en
> saanut neliöjuurifunktiota toimimaan. Eräs muista syistä voisi olla
> vaikka se, että en ole vielä kuullut riittäviä perusteluja sen käyttöön.
>
> Monet gurut ovat minusta järjestelmällisesti unohtaneet sen, että
> neliöjuuren laskeminenkin tuottaa kompleksisuutta. Mikä on C:n
> sqrt-funktion kompleksisuus? Älkääkä vain sanoko että se on neliöjuuri
> n. Toki sqrt-funktion kompleksisuus olisi pienempi (?) kuin puolikkaan
> testi-funktioni kompleksisuus, mutta minusta on eduksi jos voi pelata
> kokonaisluvuilla. Tällöin pseudonomaisesti käyttämäni koodinpätkän
> porttaaminen vaikka assemblerille olisi helpompaa. Älkääkä vain sanoko,
> että nykyajan hienot pentiumit laskevat neliöjuuria yhdessä
> kellojaksossa (vaikka se olisikin totta).
Neliöjuuren voi laskea myös kokonaisluvuilla muutamalla sadalla käskyllä
32 bittisestä luvusta. Algoritmejä löytynee netistä, minulla oli joskus
tuollainen assemblerohjelma Amigalle. Pienillä luvuilla nopein tapa on
kertoa testattava jakaja itsellään ja verrata tuloa jaettavaan. Se vie
kertolaskun testiä kohti. Ellei käyttämässäsi prosessorissa ole nopeaa
kertolaskukäskyä, neliöönkorotukset vievät aika äkkiä neliöjuuren
laskemiseen kuluvan ajan. En tosin muista, että oliko
neliöjuurialgoritmissä paljon kertolaskuja. Samoin jakamisiin kuluu niin
paljon aikaa, että miljoonan kokoluokassa kannattaa laskea se
neliöjuuri.
Karkean approksimaation neliöjuurelle saat myös laskemalla mikä on
korkein bitti, joka on asettunut juurrettavassa luvussa. Jaa bitti
kahdella ja lisäätulokseen yksi. Muodosta luku, jossa on näin saatu
bitti asetettuna ja muut nollia. Esimerkki:
Luku olkoon 7424. Binäärisenä se on 1110100000000. Korkein asettunut
bitti on 12 (alin on 0). Lisätään jaetaan kahdella ja lisätään yksi ->
saadaan 7. Neliöjuuri on siis 2^7 eli 128. Oikea arvo on vähän yli 86.
Säästät paljon aikaa laskemalla 128 jakolaskua 3712:n sijasta.
Hannu Koskenvaara
Risto Paasivirta
Tuomas =?iso-8859-1?Q?Yrj=F6vuori?= <tpyr...@cc.hut.fi> wrote:
>neliöjuuren laskeminenkin tuottaa kompleksisuutta. Mikä on C:n
>sqrt-funktion kompleksisuus? Älkääkä vain sanoko että se on neliöjuuri
>n. Toki sqrt-funktion kompleksisuus olisi pienempi (?) kuin puolikkaan
Jotain luokkaa neliöjuuri 2^n bitin luvusta vie n/2
iteraatiota. (Jos ei käytä valmiina prosessorissa olevaa
versiota.)
>testi-funktioni kompleksisuus, mutta minusta on eduksi jos voi pelata
>kokonaisluvuilla. Tällöin pseudonomaisesti käyttämäni koodinpätkän
>porttaaminen vaikka assemblerille olisi helpompaa. Älkääkä vain sanoko,
>että nykyajan hienot pentiumit laskevat neliöjuuria yhdessä
>kellojaksossa (vaikka se olisikin totta).
Joka tapauksesa googlella haulla 'integer square root C
source' löytyy vino pino sälää.
(Esm http://remus.rutgers.edu/~rhoads/Code/isqrt.c)
ja hieman tarkemmalla haulla löytynee optimoitu assembler-
toteutus lähes mille vain prosessorille.
>toimisi vielä näin pienillä luvuilla.
>T. Yrjövuori
Risto
Kimmo Laine
viestissä:3CBBD1FA...@cc.hut.fi...
> Kimmo Laine wrote:
> >
> > variableja, (esim. var x). Math.sqrt(x) palauttaa x:n neliöjuuren. Ja
ihan
> > perustellusti kyllä, en näe mitään ongelmaa siinä etteikö silmukkaa
voisi
> > päättää siihen. En ole lukenut keskustelua johon viittaat, koska ei
ollut
>
> Henkilökohtainen syyni neliöjuuren poisjättämiseen oli se, että en
> saanut neliöjuurifunktiota toimimaan. Eräs muista syistä voisi olla
> vaikka se, että en ole vielä kuullut riittäviä perusteluja sen käyttöön.
Eikös neliöjuuri ole aika helppo laskea Newtonin menetelmällä? Itse kysyin
neliöjuuren kaavaa tässä ryhmässä jokin aika sitten ja vastaukseksi sain
muistaakseni viittauksen Newtonine menetelmään. Sehän on nopeasti suppeneva
rekursiivinen kaava. Kuvittelisin että parilla kymmenellä iteraatiolla saisi
laskettua riittävän tarkan neliöjuuren, jos alkuarvaus on hyvä. Tällä
voitetaan paljon aikaa kun mietimme vaihtoahtoa pysäyttää silmukka
puoliväliin. luvun puolikkaan ja neliöjuuren väliin mahtuu monta hyvää
numeroa suurilla kokonaisluvuilla. Neliöjuurenhan ei missään nimessä
tarvitse olla absoluuttisen tarkka, sillä yhden tai kahden numeron heitto
ylöspäin ei ole merkittävä, joskin kriittinen alaspäin. Toisin sanoen, jos
silmukka pysäytetään pari numeroa neliöjuuren jälkeen, ollaan saavutettu
haluttu tulos, mutta jos pari numeroa ennen neliöjuurta, saattaa esimerkiksi
25 mennä alkuluvusta jos tarkistetaan vain neloseen asti, kun olisi pitänyt
vähintään yli viitosen mennä jotta oltaisin havaittu että 25 jakautuu
tekijöihin 5*5.
Tuomas Yrjövuori
>
> olisi vaikka 500 x unsigned long, niin mitkä luvut siihen
> tallennettaisiin? 500 pienintä alkulukua vai 500 viimeisintä vai
sata == 500 :)
Taulukon koko tietysti optimoitaisiin käytettävän alustan mukaan.
Käytettäköön 500 esimerkkinä.
--
T. Yrjövuori
Tuomas Yrjövuori
>
> Eikös neliöjuuri ole aika helppo laskea Newtonin menetelmällä?
Kyllähän se on.
> ylöspäin ei ole merkittävä, joskin kriittinen alaspäin. Toisin sanoen, jos
> silmukka pysäytetään pari numeroa neliöjuuren jälkeen, ollaan saavutettu
Joo. Nimenomaan tarkkaa neliöjuuren arvoa ei tarvita. Eikä sitä voisi
hyödyntääkään kun kuitenkin pitää toimia kokonaisluvuilla. Voi olla,
että optimaalisin algoritmi olisi juuri tämäntapainen; kompromissi
tarkan neliöjuuren ja ylimääräisten testien väliltä. Toki se varmasti
kallistuisi tarkan neliöjuuren puolelle.
Vielä jää vaivaamaan ajatus jo laskettujen alkulukujen hyödyntämisestä.
Eräs tapa voisi olla laajentaa algoritmi sittenkin Erastotheneen
seulaksi ja tallentaa taulukkoon vain osajoukko alkuluvuista. Kaikkia ei
voi missään nimessä tässä tapauksessa taulukoida, kun taulokointikin
hidastaa ajoa. Ainakin suurilla alkuluvuilla tästä tulisi mahdotonta.
Siinä, mitkä alkuluvut taulukoidaan, tarvittaisiin sitten
todennäköisyyksien ja tilastomatematiikan tuntemusta. Jos taulukon koko
olisi vaikka 500 x unsigned long, niin mitkä luvut siihen
tallennettaisiin? Sata pienintä alkulukua vai sata viimeisintä vai
jotain muuta? Uskon, että näin saataisiin aikaan jo aikamoinen
alkulukujenmurskaaja.
--
T. Yrjövuori
Kari Pasanen
> Vielä jää vaivaamaan ajatus jo laskettujen alkulukujen hyödyntämisestä.
> Eräs tapa voisi olla laajentaa algoritmi sittenkin Erastotheneen
> seulaksi ja tallentaa taulukkoon vain osajoukko alkuluvuista. Kaikkia ei
> voi missään nimessä tässä tapauksessa taulukoida, kun taulokointikin
> hidastaa ajoa. Ainakin suurilla alkuluvuilla tästä tulisi mahdotonta.
Käytännössä et voi taulukoida kaikkia alkulukuja siihen rajaan asti, mihin
niitä tarvitset alkulukutestin jakajaehdokkaina, koska alkulukuja on paljon.
Jos haluat yksinkertaisella jakamisalgoritmilla testata 2n-bittisiä lukuja,
että onko alkuluku vai ei, suorittamatta yhtään ylimääräistä jakolaskua,
tarvitsisit taulukkoon kaikki n-bittiset alkuluvut, joita on suunnilleen
vakio * 2^n / n kappaletta. Näet, että alkulukujen määrä kasvaa niiden
pituuden suhteen eksponentiaalisesti, ja siksi suurilla n jakamisalgoritmi
on käy toivottoman tehottomaksi. On pakko käyttää tehokkaampia menetelmiä!
Vain pienillä n, esim. n = 32, algoritmin saa hyvällä toteutuksella nopeassa
koneessa toimimaan siedettävässä ajassa. Kun n on suuri, vaikkapa n = 1024,
ei auta koneen nopeus eikä äärimmäisen taitavasti tehty algoritmin
toteutuskaan.
> Siinä, mitkä alkuluvut taulukoidaan, tarvittaisiin sitten
> todennäköisyyksien ja tilastomatematiikan tuntemusta. Jos taulukon koko
> olisi vaikka 500 x unsigned long, niin mitkä luvut siihen
> tallennettaisiin? Sata pienintä alkulukua vai sata viimeisintä vai
> jotain muuta? Uskon, että näin saataisiin aikaan jo aikamoinen
> alkulukujenmurskaaja.
Vaikka tyytyisit pieneen ennalta muodostettuun alkulukutaulukkoon ja
alkulukutestissä jakaisit turhaankin yhdistetyillä luvuilla, algoritmista ei
tule käytännöllistä.
Tunnetuista jakamisalgoritmia tehokkaammista menetelmistä, kuten Millerin -
Rabinin tai Solovayn - Strassenin testeistä, ehkä jokin nimi on täällä
mainittu. Itse testiä ei selitetä helposti news-artikkelissa; pitäisi
paremminkin antaa linkki sivuille, josta saat tietoa. Minä en nyt vaivaudu
tietojen etsintään netistä puolestasi.
Koska ilmeisesti opiskelet TKK:ssa, saat myös siellä aikanaan opetusta
paremmista alkulukualgoritmeista.
Kari Pasanen
Tuomas Yrjövuori
>
> Käytännössä et voi taulukoida kaikkia alkulukuja siihen rajaan asti, mihin
> niitä tarvitset alkulukutestin jakajaehdokkaina, koska alkulukuja on paljon.
Ei tietenkään. Ohjelman olisikin tarkoitus jatkaa kokeilemalla kaikki
tietyn rajan jälkeen. Raja olisi se, missä taulukko loppuu. Kysymyshän
on kompromissin luomisesta prosessoriajan ja muistintarpeen välille.
Pienellä taulukolla nopeutettaisiin hieman ohjelmaa. Todennäköisesti
taulukkoon kannattaisi tallentaa pieniä alkulukuja? Tilastollisesti
kaikista luvuista löytyy varmaankin kakkonen tekijänä useammin kuin
esimerkiksi alkuluku 180001.
(Mikäli lukee tarkkaavaisesti tätä viestiä niin ei voi missään
tapauksessa saada käsitystä, että olisin väittämässä alkuluvuista
löytyvän tekijöitä. Kumma kun näitä Disclaimereita joutuu nykyään joka
paikkaan tunkemaan.)
Pitää muistaa, että parittomien lukujen jättäminen kokeilematta on
Erastotheneen seulan esiaste. Kakkonenkin on alkuluku niin kuin tiedät.
Parittomien lukujen unohtaminen on paljon helpompaa (ainakin C-kielellä)
kuin taulukon luominen, mutta aion vielä todistaa algoritmin
nopeutumisen toteuttamalla em. taulukon. Mitään kompleksisuuksia en enää
yritä esittää kunnen niitä hallitse. Osaan kyllä kuitenkin jotenkuten
ajatella matematiikkaa maalaisjärjellä.
--
T. Yrjövuori
Kimmo Laine
viestissä:3CBD287D...@cc.hut.fi...
> Kimmo Laine wrote:
> >
> > Eikös neliöjuuri ole aika helppo laskea Newtonin menetelmällä?
>
> Kyllähän se on.
>
Ja eikös se ollutkin tämmöinen, se nyyttonin metodi neliöjuurelle:
c:n neliöjuuri :
Xn+1 = 1/2*(Xn + c/Xn)
25:n neliöjuuri löytyi vaivaisella 5 iteraatiolla kun alkuarvaukseni X0 oli
12.5 eli 25/2. Tämä kyllä oli aika simppeli. huomattavaa kuitenkin että jo
kolmas arvaus oli 5.0 yhden desimaalin tarkkudella, seuraava neljän
desimaalin tarkkudella ja viides 10 desimaalin, kuudes oli jo kokonaisluku
5. ja sanotaan että toivottavaa olis päästä tarkkuuteen neliöjuuri+20, eli
noin kilometrin päähän oikeasta arvosta pienillä luvuilla, mutta senttien
päähän totuudesta suurten lukujen kyseessä ollessa. Hahmottelin liittäväni
epätarkan neliöjuuren funktion alkulukutestiini,mutta pitää aluksi
tarkastella hieman tuon funktion käyttäytymistä, ja alkuarvauksen valinnan
vaikutusta...
Kimmo Laine
viestissä:3cbf...@news.vip.fi...
> Tuomas Yrjövuori <tpyr...@cc.hut.fi> kirjoitti
> viestissä:3CBD287D...@cc.hut.fi...
> > Kimmo Laine wrote:
> > >
> > > Eikös neliöjuuri ole aika helppo laskea Newtonin menetelmällä?
> >
> > Kyllähän se on.
> >
>
> Ja eikös se ollutkin tämmöinen, se nyyttonin metodi neliöjuurelle:
>
> c:n neliöjuuri :
> Xn+1 = 1/2*(Xn + c/Xn)
>
Alustavassa testissäni neliäjuuri tuli laskettua pienillä luvuilla (1..100)
noin kymmenellä iteraatiolla. Siitä eteenpäin yksi tai kaksi iteraatiota
lisää per dekadi. 1 000 000:n neliöjuuri ratkennee alle 20 iteraatiolla.
kertaluokka on jotain O(log n), sen perusteella mitä itse testasin
javascrip-versiota. Tämä jossain määrin kumoaa T.Y:n alkuperäisen teesin
jättää neliöjuuren lasku pois ja katkaista silmukka mielummin n/2:n kuin
sqrt(n):ään.
Jos suoritetaan 20 iteraatiota joilla ratkaistaan neliöjuuri voidaan
silmukka esim. miljoonan kohdalla katkaista tuhanteen. Jos taas katkaistaan
silmukka 1000000/2 eli 5000000 suoritetaan 5000000-1000-20 turhaa laskua.
Eli käytännössä n. 50% laskuista turhia. En haluaisi sanoa "I told you so",
mutta kovasti tekee mieli.
Tässä funktioni pseudokoodina, siitä kukin rakentakoon toimivan version
lempiohjelmointikielelleen jos haluaa.
funktio quicksqrt(x){
// alustukset
liukulukumuuttuja oldh;
liukulukumuuttuja h = x/2;
// rekursiivinen algoritmi, neliöjuuren etsintä Newtonin metodilla
tee niin kauan kuin (h on erisuuri kuin oldh)
{
oldh = h;
h = (oldh + x/oldh)/2;
}
palauta h;
Tuomas Yrjövuori
>
> Eli käytännössä n. 50% laskuista turhia. En haluaisi sanoa "I told you so",
> mutta kovasti tekee mieli.
Sen minä olen tiennyt alusta alkaen, että alunperin postaamani linkin
algoritmissa _yli_ 50% jakolaskuista oli turhia. Myöhemmin postaamassani
(tähän säikeeseen) alle 50% on turhia (turhia = n / 2 - sqrt(n)). Entä
sitten? Emmehän kävisi tätä keskustelua jos olisin postannut
"täydellisen" algoritmin?
Muuta en väittänyt, mutta en tosin ollut varma noiden
neliöjuurifunktioiden kompleksisuuksista.
Nyt kun testifunktion kompleksisuus on optimoitu täysin
(vakiokertoimella) niin voimme ryhtyä ratkaisemaan Erastotheneen seulan
ongelmaa pääfunktion silmukassa. Nyt voin taas todeta, että aikaisempaan
säikeeseen [alkuluvut (oli: piin desimaaleissa toistoa) - tai jotain
sinne päin] postaamani koodinpätkä ei jättänyt parittomia lukuja
testaamatta (se oli hölmösti toteutettu - kyllä). Tähän säikeeseen
postaamani jättää, mutta se ei riitä. Sen pitäisi jättää testaamatta
kolmella jaolliset, viidellä jaolliset, seitsemällä jaolliset jne...
Sitä voi kukin kehittää omassa sopessaan. Keskustelu varmaankin pitäisi
siirtää *ohjelmointiin, mutta en tiedä onko siinäkään mitään järkeä.
--
T. Yrjövuori
Mika R S Kojo
"Kimmo Laine" <nikke_kn...@yahoo.co.uk> writes:
>
> funktio quicksqrt(x){
> // alustukset
> liukulukumuuttuja oldh;
> liukulukumuuttuja h = x/2;
> // rekursiivinen algoritmi, neliöjuuren etsintä Newtonin metodilla
> tee niin kauan kuin (h on erisuuri kuin oldh)
> {
> oldh = h;
> h = (oldh + x/oldh)/2;
> }
> palauta h;
> }
Oletko varma, että on aina olemassa liukuluku h, jolla pätee
h = (h + x/h)/2?
Jos kokonaisluvut jotain opettavat niin sen, että tämä ei ole
itsestään selvää. Mieti vaikka tilannetta x = 3 ja h = 1. Nyt saamme
oldh = 1, h = (1 + (3/1))/2 = 2;
seuraava iteraatio
oldh = 2, h = (2 + (3/2))/2 = 1.
Täten algoritmi ei koskaan pysähdy. Tietysti tässä esimerkissä
kokonaisluku operaatiot ovat oleellisia, mutta tämä viittaa
samankaltaiseen mahdollisuuteen myös liukuluvuilla. Huomaa lisäksi,
että liukuluvut käyttäytyvät yleensä eritavoin eri ympäristöissä.
Mika
Valmari Antti
Säikeessä "alkulukualgoritmi" Kimmo Laine kirjoitti:
> Alustavassa testissäni neliäjuuri tuli laskettua pienillä luvuilla (1..100)
> noin kymmenellä iteraatiolla. Siitä eteenpäin yksi tai kaksi iteraatiota
Jos Sinulla vielä riittää tarmoa mittailla neliöjuurialgoritmien
nopeuksia, niin koetapa alla olevia. Arvelisin että varsinkin B-versio
tulee selviämään paljon alkukarsintoja pitemmälle. Kiinnostaisi tietää,
missä määrin se pärjää Newtonin iteraatiolle.
--- Antti Valmari ---
#include <iostream>
typedef unsigned long luonn_luku;
using std::cout; using std::endl;
/* Laskee kokonaislukutyyppisen luvun neliöjuuren biteittäin kerto-
ja jakolaskujen avulla. */
luonn_luku njuuriA( luonn_luku nn ){
/* Käsitellään 0 poikkeustapauksena. */
if( !nn ){ return 0; }
/* Etsitään suurin vastauksen alalikiarvo, jonka biteistä tasan yksi
on ykkönen. */
luonn_luku vast = 1, apu = nn / 4;
while( apu ){ vast *= 2; apu /= 4; }
/* Lasketaan juuren bitit yksi kerrallaan. */
luonn_luku vajaus = nn - vast * vast, delta = vast / 2;
while( delta ){
if( vajaus >= 2 * vast * delta + delta * delta ){
vajaus -= 2 * vast * delta + delta * delta; vast += delta; }
delta /= 2;
}
return vast;
}
/* Tämän tulos pitäisi hakea kirjastosta <limits>, mutta kääntäjäni ei
tunne sitä. */
luonn_luku suurin_neljan_potenssi(){
luonn_luku apu1, apu2 = 1;
do{ apu1 = apu2; apu2 = apu1 << 2; }while( apu2 );
return apu1;
}
/* Laskee kokonaislukutyyppisen luvun neliöjuuren ilman kertolaskuja. */
const luonn_luku TAIKA = suurin_neljan_potenssi();
luonn_luku njuuriB( luonn_luku nn ){
/* Käsitellään 0 poikkeustapauksena. */
if( !nn ){ return 0; }
/* Etsitään suurin syötteen alalikiarvo, joka on nelosen potenssi. */
luonn_luku vast = TAIKA;
while( vast > nn ){ vast >>= 2; }
/* Lasketaan juuren bitit yksi kerrallaan. */
luonn_luku vajaus = nn - vast, delta = vast >> 2;
while( delta ){
if( vajaus >= vast + delta ){
vajaus -= vast + delta; vast >>= 1; vast += delta;
}else{ vast >>= 1; }
delta >>= 2;
}
return vast;
}
void testaa( luonn_luku nn ){
luonn_luku tulos = njuuriB( nn );
if( nn <= 20 || nn % 1000000 == 0 ){
cout.width( 10 ); cout << nn << ": ";
cout.width( 5 ); cout << tulos << endl;
}
if( tulos * tulos > nn || ( tulos + 1 ) * ( tulos + 1 ) <= nn ){
cout << "Hupsista! " << nn << ": " << tulos << endl; exit( 1 );
}
}
int main(){
testaa( 0 );
for( luonn_luku nn = 1; nn > 0; ++nn ){ testaa( nn ); }
}
Valmari Antti
Itse itseäni korjaten:
> if( tulos * tulos > nn || ( tulos + 1 ) * ( tulos + 1 ) <= nn ){
> cout << "Hupsista! " << nn << ": " << tulos << endl; exit( 1 );
> }
Tuossa tulee ylivuoto, kun (32-bittisillä luvuilla) tulos saavuttaa
65535, jolloin virhehälytys laukeaa turhan päiten. Huomasin, kun
testiajoni ehti lukuun 4294836225 eli 65535^2 saakka.
Koska virhe oli vain testiympäristössä eikä itse koodissa, en
ala sitä korjaamaan. Versio B jäi nyt testaamatta luvuille
4294836225, ..., 4294967295. Se toimi kuitenkin luvuille
0, ..., 4294836224, ja se toimi kaikille luvuille kun lukutyyppi
oli 16-bittinen unsigned int, joten enpä usko sen kompastuvan
noihin 131071 testaamattomaan lukuun. (Versiota A en ole testannut
yhtä perusteellisesti, riittävästi kumminkin.)
--- Antti V. ---
Kimmo Laine
viestissä:slrnac03hs...@e.math.helsinki.fi...
> In article <3cbf3513$1...@news.vip.fi>, Kimmo Laine wrote:
> > Alustavassa testissäni neliäjuuri tuli laskettua pienillä luvuilla
(1..100)
> > noin kymmenellä iteraatiolla. Siitä eteenpäin yksi tai kaksi iteraatiota
> > lisää per dekadi. 1 000 000:n neliöjuuri ratkennee alle 20 iteraatiolla.
>
> aina luvun neliöjuureen asti, niin neliöjuurta ei tarvitse laskea.
> Jos muuttuja n sisältää testattavan luvun neliöjuuren kokonaisosan
> ja s sisältää luvun (n+1)^2-1, niin kun on päästy testissä s:ään asti,
> voidaan inkrementoida n:ää yhdellä ja s:ää 2n+3:lla.
Tämä oli muuten ihan sama juttu mitä tulin tänään ajatelleeksi... En vain
tiennyt suoraa kaavaa, mutta tulin miettineeksi että kun tiedetään edeltävä
luku ja sen neliöjuuri, niin voitaisiin laskea jotenkin päätellä seuraava
neliöjuuri tarvitsematta laskea sitä varsinaisesti. Tämä oli erittäin hyvä
huomio.
Tapio
"Valmari Antti" <ava@.c.s...t.u.t...f.i.invalid> wrote in message
news:a9p44q$61f$1...@news.cc.tut.fi...
>
> Säikeessä "alkulukualgoritmi" Kimmo Laine kirjoitti:
> > Alustavassa testissäni neliäjuuri tuli laskettua pienillä luvuilla
(1..100)
> > noin kymmenellä iteraatiolla. Siitä eteenpäin yksi tai kaksi iteraatiota
>
> Jos Sinulla vielä riittää tarmoa mittailla neliöjuurialgoritmien
> nopeuksia, niin koetapa alla olevia. Arvelisin että varsinkin B-versio
> tulee selviämään paljon alkukarsintoja pitemmälle. Kiinnostaisi tietää,
> missä määrin se pärjää Newtonin iteraatiolle.
Vinkki:
http://www.etheron.net/usuarios/dgomez/default.htm
Tapio
Valmari Antti
Tapio kirjoitti:
> Vinkki:
> http://www.etheron.net/usuarios/dgomez/default.htm
Mitä sieltä pitäisi löytyä? Löysin kyllä liudan erilaisia iteraatiokaavoja
x_(n+1) = f( x_n ) juurten likiarvojen x_n laskemiseen, mutta en löytänyt
mitään mainintoja muunlaisista laskutavoista, saatika nopeusvertailuja.
(Sivumennen sanoen, sivu antoi itsestään epäluotettavan vaikutelman.)
--- Antti V. ---