Controle van een kwadraat, zonder deze te berekenen?

[JWvdVeer]

Dag allen,

Op het moment ben ik een klein programmaatje in C aan het schrijven. Het programmaatje moet voor mij priemgetallen kunnen berekenen. Dit wil ik uiteraard zo groot mogelijk doen.

Op het moment schijf ik het programma voor het datatype int, maar het vraagstuk zou ook voor een willekeurig ander datatype kunnen gelden. Dus een antwoord als `juggle het geheel naar een ander datatype` is niet het gewenste antwoord.

Mijn probleem is het volgende:

Priemgetallen boven de drie hebben een aantal eigenschappen, die relatief snel controleerbaar zijn.

\(p = 6n\pm1\)

\(p = 4n\pm 1\)

\(p² = 24n + 1\)

Nu wil het geval dat vooral de laatste problemen oplevert.

Het probleem behelst het bereik van datatype. In een int(eger) op C kun je maximaal het getal

\(2^{32}-1 = 4294967295\)

opslaan. Dit is het kwadraat van het getal 65535 (omlaag afgerond). Als ik deze controle er dus in houdt kan ik dus enkel getallen tot 65535 controleren op het zijn van een mogelijk priemgetal. Op zich kan dat allemaal wel, dat is het probleem niet. Maar zoals je zult snappen is een dergelijke controle veel sneller dan het aflopen van de rij met priemgetallen die je al eerder berekend hebt.

Dus is mijn vraag: hoe kan ik van getal n controleren of het kwadraat voldoet aan de regel

\(24n + 1\)

zonder werkelijk dat kwadraat te berekenen?

PS: Mochten jullie andere -snelle- controles kennen, dan hoor ik die ook graag .

[EvilBro]

Priemgetallen boven de drie hebben een aantal eigenschappen, die relatief snel controleerbaar zijn.

\(p = 6n\pm1\)

\(p = 4n\pm 1\)

\(p² = 24n + 1\)

Alleen de eerste eigenschap is zinnig. Als de eerste eigenschap geldt dan gelden de andere twee voorwaarden ook. Als de eerste eigenschap niet geldt dan maakt het niet uit of de overige eigenschappen gelden.

Maar zoals je zult snappen is een dergelijke controle veel sneller dan het aflopen van de rij met priemgetallen die je al eerder berekend hebt.

De eigenschap garandeert niet dat een getal met de eigenschap een priemgetal is. Je hoeft alleen minder getallen te controleren, maar je zult ze nog steeds moeten controleren.

De winst om een gegeven getal te controleren is marginaal. De eerste eigenschap is equivalent met controleren of een getal deelbaar is door 2 of 3. In plaats van simpel even te delen door 2 en/of 3 ga je er eerst 1 afhalen (of bij optellen) om vervolgens te delen door 6. Niet echt zinnig...

Dus is mijn vraag: hoe kan ik van getal n controleren of het kwadraat voldoet aan de regel

\(24n + 1\)

zonder werkelijk dat kwadraat te berekenen?

Dat weet ik niet, maar de hele controle is overbodig...

[JVV]

Je moet je realiseren dat er velen zijn die zoiets al een keer hebben gedaan, maar het is wel een leuk project om zoiets zelf in elkaar te knutselen. De truc zit hem natuurlijk in het zo efficient mogelijk maken. Maak zoveel mogelijk gebruik van de eigenschappen van de type priemgetallen die jij noemden.

Wellicht bekend, wanneer 4n+1 een priem is dan geldt; 4n+1 = a^2 + b^2.

Als 6n-1 geen priemgetal is dan geldt; 6n - 1 = a^2 - b^2

Dit is even wat me direct te binnen schiet als eigenschap van die priemgetallen. Wellicht dat er personen zijn die er nog meer kennen.

[kee]

Ik zie ook niet goed welke kant je opwil met die formules. Ik snap ook niet goed het opzet "priemgetallen berekenen". Wil je voor een bepaald getal controleren of het priem is of wil je alle priemgetallen tot een bepaald getal vinden?

In het eerste geval is een eenvoudige methode om het iets sneller te laten gaan in plaats dat je alle getallen tot de wortel overloopt (het lijkt me niet echt handig om alle priemgetallen te gaan opslaan, tenzij je dat net zou willen natuurlijk) is het uitfilteren van de veelvouden van 2,3,5,7,11 (verder zou ik niet gaan) uit de getallen waarmee je controleert, wat voor je de opslag vraagt van de de niet-gefilterde uit een rij van 2*3*5*7*11 getallen (wat prutswerk misschien om het helemaal goed te krijgen). Zo heb je als cadeau ook de factorisatie erbij (er zijn natuurlijk wel ook efficiëntere dingen, zeker aangezien je die factorisatie niet wilt).

In het tweede geval lijkt mij het beste om alles in één keer te berekenen met de zeef van Eratosthenes.

[JWvdVeer]

Alleen de eerste eigenschap is zinnig. Als de eerste eigenschap geldt dan gelden de andere twee voorwaarden ook. Als de eerste eigenschap niet geldt dan maakt het niet uit of de overige eigenschappen gelden.

Zou je dat kunnen laten zien? Dat zie ik namelijk niet zo...

Ik interpreteer jouw verhaal als:

\(k \in \nn \wedge (6n + 1 = k \vee 6n - 1 = k) \longrightarrow k² = 24p + 1\)

En ik zie vooral die implicatie even niet.

De eigenschap garandeert niet dat een getal met de eigenschap een priemgetal is. Je hoeft alleen minder getallen te controleren, maar je zult ze nog steeds moeten controleren.

Dat doe ik ook. Maar het fungeert als filter.

Ik had het progje eigenlijk geschreven naar aanleiding van het topic Priemgetal - n - priemgetal, kan altijd.

Code: Selecteer alles

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

long int realMod(long int iN, long int iT){

long iRem = (iN % iT);

return ((iRem < 0)? iRem : iRem);

}

int main(void){

long int *aiPrimes = malloc(100 * sizeof(long int));

if(aiPrimes == NULL) return 0;

aiPrimes[0] = 1;

aiPrimes[1] = 2;

aiPrimes[2] = 3;

int iPrimeIndex = 3;

long int iCount = 1;

long int iPrimer = 3;

long int iLastPrime = 3;

while(iCount <= 5000){

++iCount;

while(iLastPrime <= (2 * iCount)){

iPrimer += 2;

// if(realMod((iPrimes * iPrimes), 24) != 1) continue;

if(labs(realMod(iPrimer, 6) - 3) != 2) continue;

if(labs(realMod(iPrimer, 4) - 2) != 1) continue;

long int iSqrt = (long int) sqrt((double) iPrimer);

long int iIndex = 1;

int bDividable = 0;

while(!bDividable && (aiPrimes[iIndex] <= iSqrt)) bDividable = !(iPrimer % aiPrimes[iIndex++]);

if(!bDividable){

if(!(iPrimeIndex % 100)){

aiPrimes = (long int *) realloc(aiPrimes, (iPrimeIndex + 100) * sizeof(long int));

if(aiPrimes == NULL) return 0;

}

aiPrimes[iPrimeIndex++] = (iLastPrime = iPrimer);

}

}

int bNotFound = 1, iPos = (iPrimeIndex - 1);

while(aiPrimes[--iPos] >= iCount){

long int iRemainer = ((2 *  iCount) - aiPrimes[iPos]);

long int iSIndex = 0;

while(bNotFound && (aiPrimes[iSIndex] <= iRemainer)){

if(aiPrimes[iSIndex] == iRemainer){

bNotFound = 0;

printf("%li: %li + %li\r\n", iCount, iRemainer, aiPrimes[iPos]);

}

++iSIndex;

}

}

if(bNotFound){

printf("Geldt niet voor %li", iCount);

return 0;

}

}

}

Overigens is het niet bepaald in de C-codingstyle. Maar ik ben van origine een PHP-, Java-, C#- en VB(.NET)-amateur.

Ik zie ook niet goed welke kant je opwil met die formules. Ik snap ook niet goed het opzet "priemgetallen berekenen". Wil je voor een bepaald getal controleren of het priem is of wil je alle priemgetallen tot een bepaald getal vinden?

Voor het desbetreffende topic was het gewoon simpel: bereken een lijst met priemgetallen en ga na voor alle getallen uit verzameling N of ze voldoen aan de voorwaarde. Maar nu is het meer gewoon even de hobby om het goed te krijgen en het te bewaren voor een volgende keer, mocht ik weer iets dergelijks tegenkomen. Het gaat er gewoon even om dat ik er wat lol aan beleef en gelijk een snippet heb klaarliggen.

[dragonitor]

een vraagje, klopt het dik gedrukte:

1 alle getallen

2 helft van alle getallen(van 1)

3 1/3 van alle getallen(van 1)

4 helft van getallen van 2

5 1/5 van alle getallen(van 1)

6 helft van getallen van 3 + 1/3 van alle getallen van 2

7 1/7 van alle getallen(van 1)

ETC.

?

[EvilBro]

Zou je dat kunnen laten zien? Dat zie ik namelijk niet zo...

Stel er geldt voor een getal:

\(k = 6\cdot n \pm 1\)

dan kun je schrijven:

\(k = 6\cdot n \pm 1 = 4 \cdot n + 2 \cdot n \pm 1\)

Stel dat n even is:

\( = 4 \cdot n + 2 \cdot (2 \cdot m) \pm 1 = 4 \cdot n + 4 \cdot m \pm 1 = 4 \cdot (n + m) \pm 1\)

Dit heeft de vorm van eigenschap 2.

Stel dat n oneven is:

\( = 4 \cdot n + 2 \cdot (2 \cdot m + 1) \pm 1 = 4 \cdot n + 4 \cdot m + 2 \pm 1 = 4 \cdot (n + m) + 2 \pm 1\)

dan geldt dus:

\(4 \cdot (n + m) + 2 +1 \mbox{ of } 4 \cdot (n + m) + 2 - 1\)

\(4 \cdot (n + m) + 3 \mbox{ of } 4 \cdot (n + m) + 1\)

\(4 \cdot (n + m + 1) - 1 \mbox{ of } 4 \cdot (n + m) + 1\)

Dit heeft de vorm van eigenschap 2.

In beide gevallen (n even of n oneven) heeft het getal de vorm van eigenschap 2. Kortom:

\(k = 6 \cdot n \pm 1 \rightarrow k = 4 \cdot z \pm 1\)

Hetzelfde truukje kun je doen voor de derde eigenschap. Begin met:

\((6 \cdot n \pm 1)^2 = 36 \cdot n^2 \pm 12 \cdot n + 1 = 24 \cdot n^2 + 12 \cdot n^2 \pm 12 \cdot n + 1\)

\(= 24 \cdot n^2 + 12 \cdot n (n \pm 1) + 1\)

of

\(n\)

is even of

\(n \pm 1\)

is even en dus:

\(= 24 \cdot n^2 + 12 \cdot 2 \cdot m + 1 = 24 \cdot (n^2 + m) + 1\)

[JWvdVeer]

In het tweede geval lijkt mij het beste om alles in één keer te berekenen met de zeef van Eratosthenes.

Heb even gekeken, maar zie dat het een sterk memory-consuming methode is. Daarnaast is het wat rekentijd betreft zeker niet voordeliger dan de methode die nu al gehanteerd wordt (enkel de getallen die überhaupt kunnen worden gecontroleerd en meegenomen in de lijst).

Maar stel dat EvilBro gelijk heeft, dan hoef ik maar één controle te doen, die ik ook gewoon in kan bouwen door om en om 2 of 4 bij het vorige getal op te tellen (5 + 2 = 7, 7 + 4 = 11, 11 + 2 = 13, 13 + 4 = 17, 17 + 2 = 19, 19 + 4 = 23, 23 + 2 = 25, etc.) en daarna controleren aan de hand van de lijst die ik al heb..

[thermo1945]

hoe kan ik van getal n controleren of het kwadraat voldoet aan de regel

\(24n + 1\)

zonder werkelijk dat kwadraat te berekenen?

Een kwadraat kan alleen maar eindigen op 9 00 1 4 25 en 6.

[kee]

Heb even gekeken, maar zie dat het een sterk memory-consuming methode is. Daarnaast is het wat rekentijd betreft zeker niet voordeliger dan de methode die nu al gehanteerd wordt (enkel de getallen die überhaupt kunnen worden gecontroleerd en meegenomen in de lijst).

Voordeliger qua rekentijd is het wel volgens mij (je hoeft eigenlijk geen enkele deling uit te voeren en alleen maar te schrappen met regelmatige tussenpozen). Memory-consuming is waar, maar echt onmogelijk? Je wil toch ook alle priemgetallen opslaan? Maar t kan wel dat het niet gaat, ik heb niet nagegaan op welke manier je dat efficiënt zou moeten programmeren dus misschien is het niet mogelijk.

Maar stel dat EvilBro gelijk heeft, dan hoef ik maar één controle te doen, die ik ook gewoon in kan bouwen door om en om 2 of 4 bij het vorige getal op te tellen (5 + 2 = 7, 7 + 4 = 11, 11 + 2 = 13, 13 + 4 = 17, 17 + 2 = 19, 19 + 4 = 23, 23 + 2 = 25, etc.) en daarna controleren aan de hand van de lijst die ik al heb..

Hij heeft wel gelijk denk ik (hoewel ik die uitwerking niet gelezen heb). Mijn methode (filteren van veelvouden van priemgetallen) is eigenlijk dezelfde als wat je hier zet, maar jij doet het enkel voor 2 en 3, terwijl ik voorstelde om het te doen voor 2,3,5,7 en eventueel ook 11.

[JWvdVeer]

Inderdaad, EvilBro, ik zie dat je gelijk hebt. Ik heb nu ik dit zie ook het idee dat die 24 vergelijking met de 24 veel inefficiënter is dan die met de 6:

Stel dat je alle opties aan de hand van die vergelijking met 24 uit zou proberen, dan moet je alle (n²+m) uitproberen. Deze is dus ruimer dan de vergelijking met de 6.

@Dragonitor:

Wat bedoel je?

[kee]

@Dragonitor: dat klopt denk ik, waarvoor belangrijk? In die snelheid wordt het ook efficiënter als je veelvouden laat wegvallen ter controle (de niet-vetgedrukte dan). Bij de andere horen er ook nog "vetgedrukte" (extra's die al geschrapt zijn), maar die hebben ook niet veel zin (het wordt ook ingewikkeld dan misschien).

[JWvdVeer]

Voordeliger qua rekentijd is het wel volgens mij (je hoeft eigenlijk geen enkele deling uit te voeren en alleen maar te schrappen met regelmatige tussenpozen). Memory-consuming is waar, maar echt onmogelijk? Je wil toch ook alle priemgetallen opslaan?

Nee, het is zeker niet voordeliger qua rekentijd. Dat kan ik je vrij eenvoudig uitleggen.

Stel dat we de lijst: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 hebben.

Dan streep je eerst af (2):

2, 4, 6, 8, 10, 12, 14, 16, 18, 20 (hiervoor check je in totaal 18 getallen, je streept er 9 weg, houdt er 11 over).

Daarna streep je af (3):

9 (hiervoor check je in totaal 7 getallen, je streept er 1 weg, je houdt er 10 over).

Daarna streep je af (5):

15 (hiervoor check je in totaal 6 getallen).

Voor de overige getallen moet je nog 10x checken en streep je niets weg.

In totaal check je dan 18 + 7 + 6 + 10 = 41 getallen (met modulo, ofwel delingsrest). En schrap je er in totaal 9 + 1 + 1 = 11 (dat houdt dus ook in dat je 11x een geheugenblok moet gaan verplaatsen, omdat een getal gewist moet worden).

Uiteindelijk houdt je over:

1, 2, 3, 5, 7, 11, 13, 17, 19

In mijn geval, heb je eerst de voorwaarde (nu nog maar één). Ofwel, we beginnen de lijst met de getallen:

1, 2, 3, 5, 7, 11, 13, 17, 19 (sorry, maar per ongeluk allemaal priemgetallen. Maakt in feite niet zo veel uit).

Voor deze lijst worden er per getal twee berekeningen gedaan: 9x2 = 18 berekeningen.

Voor deze lijst worden er: 6 + 5 + 4 + 3 + 2+ 1 = 21 vergelijkingen gedaan.

Voor deze lijst worden er geen memoryblokken gekopiëerd en verplaatst, omdat de getallen pas toegevoegd worden na controle.

Memory-consuming is waar, maar echt onmogelijk? Je wil toch ook alle priemgetallen opslaan?

Niet echt onmogelijk. Maar een beetje irrealistisch om de getallen 1 - 2^31 op te slaan. Dat zou namelijk:

\(2^{31} \cdot 4 bytes = 8.6 \cdot 10^9 bytes = 8GB\)

kosten van het werkgeheugen (een getal kost vier bytes, op 64-bits machines soms 8 bytes). Dat is iets wat jij wss. ook niet in jouw kast hebt zitten en anders zeker niet overhebt voor enkel een afstreeplijst van priemgetallen.

Daarnaast kost een dergelijke lijst opstellen ook eerst heel veel rekentijd. Je moet namelijk eerst van 1 - 2^32-1 tellen. En daarna nog 2^32-1 + 2^32-2 + 2^31 ... om elke keer af te strepen.

Als je overigens ook op Wikipedia kijkt, zie je dat dit vooral een goede methode is voor snel de kleine priemgetallen te berekenen. Dat is dus ook wat ik min of meer denk dat het geval is. Al met al zou ik deze methode niet aanraden.

Maar sowieso bedankt voor het meedenken .

[kee]

Ja zo is het zeker niet voordeliger. Maar het is zo wel duidelijk dat het dan niet uitmaakt of je die in die of een andere volgorde wegschrapt op die manier. Dat was niet wat ik bedoelde. Het punt was dat het "checken" nogal eenvoudig wordt als je die allemaal laat staan, omdat je niets moet delen, want degene die eruitvallen staan op regelmatige afstanden van elkaar. Je moet enkel iets erbij tellen en dan op een of andere manier "markeren". Maar op die manier is het wellicht moeilijk praktisch te implementeren. En dan moet je nog meer "checken (markeren)", want je gaat veel getallen een heel aantal keer markeren, hoewel je met getaltheorie erbij te sleuren dat misschien wel zou kunnen vermijden als je dat eens bekijkt.

Een combinatie zou dan wel ook kunnen, bijvoorbeeld per blok van 10000 de zeef toepassen waarbij je 1 deling per controle moet toepassen om de rest te bepalen van het eerste getal van het blok bij die deling door dat controlegetal, terwijl de rest dan gewoon sprongen maken is. Maar het hangt ervan af of zoiets efficiënt geprogrammeerd kan worden in C denk ik. Als je een basisprogrammeertaal zou hebben (dichter bij de machinetaal) zou je het zo wel veel efficiënter kunnen programmeren denk ik. Nu is het wellicht niet mogelijk.

[kee]

Toch nog een extra toevoeging (ik blijf er maar mee bezig ): wat memory betreft kan je 8 "getallen" PER BYTE opslaan, omdat je enkel 1 of 0 zou moeten markeren als je alles in 1 keer doet (of in blokken) (je zet eerst alles 1 of zo en maakt de plaats 0 als je moet markeren), maar ik begrijp ook dat dat allemaal wellicht niet te implementeren valt.