Die Dusche ist eine der wichtigsten Errungenschaften der heutigen Zivilisation, zumindest was das Nachdenken angeht. Man ist mit dem mechanischen Ablauf des sich Säuberns beschäftigt, eine Tätigkeit, der man sich mehrere Jahrzehnte hingegeben hat und die einem ganz bestimmt keinen Funken geistiger Anstrengung mehr abverlangt. Man denk nicht mehr nach, ob der linke oder der rechte Arm jetzt dran ist, habe ich schon den Hals gewaschen oder sind jetzt schon die Füße dran? Man macht es einfach, ohne nachzudenken, absolut mechanisch. Der Kopf ist absolut frei, frei für wichtige Gedanken, frei für die besten Gedanken bzw. Ideen überhaupt!
So erging es mir heute ebenfalls. Plötzlich dachte ich darüber nach wieso ich eigentlich bei der Prim-Eigenschaften Berechnung immer von der zu überprüfenden Zahl abwärts laufen lasse? Also versuche die zu überprüfende Zahl mit jeder Zahl bis eins modulo zu nehmen. Das ergibt doch keinen Sinn! Bis zur Hälfte der zu überprüfenden Zahl wird das modulo Ergebnis immer ungleich null sein. Somit habe ich die vorhandene for-Schleife so abgeändert, daß sie die zu überprüfende Zahl nur noch mit den Zahlen ab der Hälfte abwärts modulo genommen werden.
for (i = ((z - (z % 2)) / 2); i > 1; i--)
Nach der Änderung der Schleife kam der Algorithmus auf das millionste Ergebnis bereits nach 42 Minuten und 18 Sekunden. Mehr als doppelt so schnell wie vorher!
Beim weiteren Sinnieren im Verlaufe des Nachmittags kam mir die Frage wie hoch denn die Wahrscheinlichkeit wäre, daß die zu überprüfende Zahl modulo einer hohen Zahl gleich null wäre gegenüber einer modulo Operation mit einer kleinen Zahl. Also zum Beispiel wie wahrscheinlich es wäre, daß 27 % 13 gleich 0 wäre gegenüber 27 % 3 gleich 0 wäre. Somit kehrte ich die Schleife einfach um. Gleichzeitig erlaubte ich der Funktion zurückzukehren, wenn die zu überprüfende Zahl eins wäre. Da jede Primzahl nur durch sich selbst und durch eins teilbar ist, kann ich die Schleife ruhig von 3 zählen lassen.
for (i = 3; i < ((z - (z % 2)) / 2); i++)
Schon schrumpfte die Rechenzeit auf unglaubliche 9 Minuten und 55 Sekunden. Quasi ein Bruchteil des ursprünglichen Wertes!
Später des Abends fragte ich mich wozu die modulo Operation mit geraden und ungeraden Zahlen durchgeführt wird. Die modulo Operation einer ungeraden Zahl mit einer geraden kann doch nie null ergeben. Somit folgte wieder eine Änderung der for-Schleife.
for (i = 3; i < ((z - (z % 2)) / 2); i += 2)
Wie man erkennen kann, zählt die Schleife immer um zwei hoch. Somit werden nur noch ungerade Zahlen berücksichtigt. Auch nach dieser Änderung sank die Rechenzeit. Dieses Mal waren es nur noch 5 Minuten und 19 Sekunden.
Nun frage ich mich nach dem Erfolg des Verringerns der Laufzeit von 106 auf 5 Minuten an einem Tag, ob ich nicht öfter am Tag oder eher den ganzen Tag lang duschen sollte. Und ob mein Notebook strömendes Wasser überhaupt verträgt und/oder ob es generell Unterwassernotebooks gibt. Würde ich eine extra Halterung für das Notebook in der Dusche benötigen? Vielleicht doch lieber Tisch und Stuhl in der Dusche installieren? Na, ich weiß ja nicht…
BTW: Bugfix in der ersten for-Schleife in der Berechnung der Summe. Die letzte Stelle im Array ist immer eins weniger als die Array Grösse selbst. Was für ein lustiger Fehler…
for (i = (arr_size - 1); i >= 0; i--)
Außerdem stelle ich grad fest, dass entweder mein Code recht seltsam ist (und daran besteht kein Zweifel) oder die Speicherverwaltung verhält sich unter Linux im Gegensatz zum OpenBSD ein wenig anders als erwartet. Segmentation fault. Wie schade.