Zitat:
Original von Damien
Wenn bei der Überprüfung, ob x prim ist, nur bis Wurzel(x) gesucht wird, geht das ganze wesentlich schneller vonstatten. Noch schneller geht's, wenn bei jedem Schritt der Betrag des angenommenen Teilers um 2 erhöht wird anstatt um 1.
|
Mir kam da vor ein paar Tagen noch eine ungewöhnlichere Optimierung in den Sinn. Was, wenn man auch die 3er-Zahlen nicht betrachten müsste? Übrig blieben die Zahlen 5, 7, 11, 13, 17, 19, ... Man sieht schnell, dass die Differenz zweier Folgeglieder zwischen +4 und +2 alterniert. Das ist aber schön, denkt man sich da, denn 2 = (4 XOR 6) und 4 = (2 XOR 6). Man kann also mit derselben Operation aus einer 4 eine 2 und umgekehrt machen. Noch schöner: XOR ist eine Elementaroperation, die direkt auf Registerebene ausführbar ist, die Kosten sind also sehr gering. Die Einsparung (jeder 6. Schleifendurchlauf) dagegen recht hoch
Hier mal eine Beispielfunktion in C, die mit dieser Optimierung Primzahlen berechnet. Ich war leider zu faul zum kommentieren, ich hoffe ihr versteht sie trotzdem *g* (Ach ja, sie ist natürlich auf 32bit-Architekturen optimiert, für 64bitter kann man als Datentyp stattdessen uint64_t nehmen)
Code:
uint32_t *prim(uint32_t max) {
uint32_t n=1;
uint32_t p,i;
uint32_t *buf;
double pred_n;
char offset=4;
pred_n=1.425*(max/log((double)max))+1;
buf=(uint32_t*)malloc((long)pred_n*4);
if (max>0) buf[n++]=1;
if (max>1) buf[n++]=2;
if (max>2) {
buf[n++]=3;
for (i=5; i<=max; i+=offset) {
offset^=6; /* hier wird der Offset zwischen 2 und 4 alterniert */
p=3;
do {
if ((i/buf[p])<buf[p]) {
buf[n++]=i;
break;
}
} while (i%buf[p++]);
}
}
realloc(buf,n*4);
*buf=n-1;
return buf;
} Zurückgegeben wird ein Zeiger auf ein Feld, im ersten Element steht die Anzahl der gefundenen Primzahlen. Wegen topic: Den code, um dann nur die Paare auszugeben (bzw überhaupt was auszugeben), spare ich mir jetzt (merker, vergleichen ob differenz = 2, wenn ja ausgeben), das ist IMO nebensächlich *g*
Greets, Ziri