Priemgetallen

[kH_]

//DELETED!!

[Roenes]

Maar nu, de grote fout die erin zit. Kijk eens goed naar die FOR loop. Daarin zie ik een kleine beginnersfout staan, die alleen wel fataal is voor de correcte werking van het programma:
for (var j=2; j <= (i-1); ++j)
Ik zie daar '++j' staan, wat betekent dat het j DIRECT wordt opgehoogd bij het ingaan van de loop. Effectievelijk betekent dit, dat een deling door 2 NOOIT getest zal worden. Daardoor zal 4 als priemgetal worden gezien, terwijl het toch degelijk geen priemgetal is. Die '++j' dus gewoon ff veranderen in 'j++' en el problemo es opgelosto ;)
Dit moet ik toch even ontkrachten :) Normaal gesproken heb je gelijk. ++j hoogt eerst j op voordat er mee gerekend wordt. Echter, in een for lus is dit niet:

for(var i = 2; i <= 10; ++i)
{
trace(i);
}
De trace levert netjes 2 t/m 10 op. Dit betekend dat i pas na de eerste ronde wordt opgehoogd. Waarom wordt er dan toch ++i gebruikt in for's? omdat dit sneller werkt als i++ Vraag me niet waarom want dat weet ik niet meer, ik weet alleen dat dit eerder een discussiepunt is geweest en dat deze conclusie eruit kwam.

De rest van je topic heb ik nog niet geheel gelezen maar zal ik later doen en er eventueel nog op reageren :)

[kH_]

Heej, inderdaad....je hebt gelijk ;)

Ik ben daar te snel vanuit gegaan denk ik dan :D

[Roenes]

Ik heb nog even de rest bekeken en dat klopt volgens mij allemaal wel. Alleen ben ik benieuwd naar 1 ding, wat zou sneller zijn? Dit:
if((i%j)==0)gedeeld=true;
of dit:
if(!(i%j))gedeeld=true;
En dan nog iets. In deze if moet ff een break gezet worden anders blijf je nog onnodige checks houden aangezien gedeeld al true is maar misschien is i nog niet op z'n eindwaarde. :)

[TheDutch]

De tweede code is sneller Roenes :).

[kH_]

In P-Code:

_push "i"
_getVariable
_push "j"
_getVariable
_modulo
_push 0
_equals2
_not
_if true goto #17

#17 _push "i"
_getVariable
_push "j"
_getVariable
_modulo
_not
_not
_if true goto #27
#27 _end


Tweede is NET iets sneller inderdaad, kost net 1 instructie minder. Maarja, tis altijd de vraag hoeveel CPU cycles iedere instructie kent. Ik weet wel vanuit mn asm achtergrond dat not operaties razendsnel zijn (een CMP, zoals de IF is simpelweg een substract operatie en die is trager ;)). Maarja, die ActionScript instructies worden voor een VM uigevoerd, dus geen idee naar welke native instructies alles vertaald wordt. Dus je kunt niet met zekerheid zeggen eigenlijk welke sneller is ;)

Roenes, voor wat betreft die break. Heb je inderdaad gelijk an :)

[Tha Narie]

Ik had destijds ook al een verbetering op dat stuk code gemaakt:

Versie van ThaNarie:


prAr = [];
counter = 1;

function getNextPrime()
{
++counter;

var pr = true;
var l = prAr.length
var c = Math.sqrt(counter);

for(var i=0; i<l && pr; ++i)
{
pr=(counter % prAr[i])
if(prAr[i] > c) break;
}

if(pr)
{
prAr.push(counter);
trace(counter);
}
else
{
getNextPrime();
}
}

priID = setInterval(getNextPrime, 100);

Werkt sneller omdat hij niet alle kleinere getallen gaat berekenen, maar enkel de kleinere priemgetallen. Deze slaat hij op in een Array (die dan dus uiteindelijk alle priemgetallen bevat).
Gaat nu door tot de wortel van het getal, dus is vele malen sneller.

Bovendien stopt deze zodra hij een deler heeft gevonden, en gaat dus niet onnodig de hele Array langs.
Ook is de deel-methode anders.
Deze kijkt naar de restwaarde (als deze 0 is, is er een deler)
De bovenstaande berekend de uitkomst, en rond deze af, en vergelijkt ze met elkaar om te kijken of hij een deler heeft.

[Roenes]

ehmz narie, counter wordt nu alleen steeds gemoduleerd door alle voorgaande priemgetallen. Maar hoe weet je dan dat dit systeem waterdicht is? Want een getal kan toch ook deelbaar zijn door een getal wat geen priemgetal is?

Of zie ik iets over het hoofd? :)

[Tha Narie]

Ik heb geen idee meer, want het is al een hele tijd geleden.
Waarschijnlijk omdat elk niet-priemgetal ook weer deelbaar is door een priemgetal.
Als iets bv deelbaar is door 14 (niet-priemgetal), is het ook deelbaar door 7 (priemgetal). Dus check ik alleen de priemgetallen, omdat die aan de basis staan, en daarmij alle delers af ga.

Op het moment dat hij deelbaar is door een getal, is het juist GEEN priemgetal.
Als hij NIET deelbaar is, is het juist WEL een priemgetal.

[kH_]

Hmmm, 1 klein (groot probleem). Jouw functie is recursief, dat is leuk en aardig, maar je gaat telkens opnieuw de vierkantswortel berekenen. Verder zou ik het fijn vinden als je mijn code doorneemt voordat je jouw verbeteringen geeft (aangezien ik die verbeteringen al heb aangegeven).
Dat met het delen door alleen de voorgaande priemgetallen is wel leuk trouwens. Ik ga alleen even zeuren door te zeggen dat dit alleen handig is voor niet al te grote getallen ;)

Dat met jouw methode (heb je dat zelf uitgevonden trouwens?) is gebaseerd op een karakter van priemgetallen. Ieder composiet-getal kan namelijk gemaakt worden door twee priemgetallen met elkaar te vermenigvuldigen. Heel logisch dus, als deze twee priemgetallen niet gevonden kunnen worden, dan hebben we te maken met een priemgetal. Dat is dan ook de verklaring voor Tha Narie's methode. Het bewijs dat ik hier geef is wel niet helemaal wiskundig correct, maar tekstueel is het wel juist.

Leuke methode!

[Roenes]

Waarschijnlijk omdat elk niet-priemgetal ook weer deelbaar is door een priemgetal.
Als iets bv deelbaar is door 14 (niet-priemgetal), is het ook deelbaar door 7 (priemgetal). Dus check ik alleen de priemgetallen, omdat die aan de basis staan, en daarmij alle delers af ga.
Op zich wel logisch jah :)

[Tha Narie]

Hmmm, 1 klein (groot probleem). Jouw functie is recursief, dat is leuk en aardig, maar je gaat telkens opnieuw de vierkantswortel berekenen.
Dat moet ook, want de couter wordt elke keer opgehoogd, dus krijg je elke keer een nieuwe 'c'.
Als ik het getal 49 moet 'checken', kijk ik dus met priemgetallen die <= 7. Waarom ik dit heb gedaan weet ik niet meer, maar het werkte blijkbaar wel, en scheelde een hoop tijd!

Verder zou ik het fijn vinden als je mijn code doorneemt voordat je jouw verbeteringen geeft (aangezien ik die verbeteringen al heb aangegeven).
Zie mijn eerste regel in die post : "Ik had destijds ook al een verbetering op dat stuk code gemaakt:"
Deze code van mij is dus van het moment dat het item werd geplaatst, meer niet.

Dat met jouw methode (heb je dat zelf uitgevonden trouwens?) is gebaseerd op een karakter van priemgetallen.
Jep, kwam er volgens mij tijdens proberen achter.

[kH_]

Als ik het getal 49 moet 'checken', kijk ik dus met priemgetallen die <= 7. Waarom ik dit heb gedaan weet ik niet meer, maar het werkte blijkbaar wel, en scheelde een hoop tijd!

Omdat 7 de vierkantswortel van 49 is, dus de maximale delingsfactor en aangezien je alle factoren daarvoor al gehad hebt, ben je klaar ;)


Zie mijn eerste regel in die post : "Ik had destijds ook al een verbetering op dat stuk code gemaakt:"
Deze code van mij is dus van het moment dat het item werd geplaatst, meer niet.
Owk :)

[Tha Narie]

Omdat 7 de vierkantswortel van 49 is, dus de maximale delingsfactor en aangezien je alle factoren daarvoor al gehad hebt, ben je klaar ;)
Dat was hem inderdaad, maar dat had je in de 1e post ook al uitgelegd zag ik!

Maar is mijn methode dan toch stukje sneller dan de jouwe?
- alleen check op primes
- uit de for-loop gaan als er een deler is gevonden
- zichzelf aanroepen is in het begin sneller, maar wordt aan het einde volgens mij iets trager dan een oEF

Ik zie trouwens nog een grote fout bij jou!
for (var j=2; j <= Math.round(Math.sqrt(i)); j++)
Daar bereken je elke loop de afgeronde wortel van een getal dat niet verandert!
Dat moet je dus voor de for doen (zoals ik).
(Zelfde als array.length in de conditie van een for zetten bij een grote array)

[kH_]

Whaha, je hebt gelijk :)

******, ik verwijder die post van mij.

[Tha Narie]

Why, stond toch nog goede uitleg tussen! :)

[kH_]

nee, of het is goed, of het is fout. En het was duidelijk fout (ik ben erg perfectionistisch, maar dat komt niet naar voren door die post :))

[Roenes]

Maar als jij je post verwijderd dan slaat de discussie nergens meer op. En daar komt bij: iedereen maakt fouten maar daar leer je van! :)

Dus zou je toch je post terug kunnen zetten? :rolleyes:

[kH_]

Uhm, ik heb het echt verwijderd hoor, ik houd echt geen offline versie van al mijn posts bij :)

En ach....er komt wel weer een nieuwe optimalisatie. Die van Tha Narie is toch op dit moment de beste.