Goldbachsche Vermutung – 2

Posted in c0de on February 13th, 2012 by serge

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.

Goldbachsche Vermutung

Posted in c0de on February 12th, 2012 by serge

Ich bin mir sicher, daß ich bei weitem nicht der erste bin, der seinen Spaß damit hat. Die Vermutung ist so simpel wie kompliziert: jede gerade Zahl ist die Summe zweier Primzahlen. Klingt recht einfach, bewaffnet mit einem Blatt Papier und einem Bleistift geht man die geraden Zahlen von vorne durch, addiert so lange zwei Primzahlen, bis man auf die ganze Zahl kommt. Für z.B. 4 wäre es 1+3, für 6 wäre es 1+5 oder 3+3 usw. Sieht wirklich recht einfach aus und wenn man Spaß an Zahlen hat, versucht man das bis zur Zahl x.

Rechnerisch wäre die Vermutung bis Zahl x bewiesen, doch wie hoch würde die bewiesene Zahl sein auf unserem Blatt Papier? Ein Tausend? Vier Tausend? Womöglich sogar zehn Tausend? Denken wir doch mal ein bißchen größer, was ist mit zwei Milliarden? Macht das unser Kopf und vor allem unsere Geduld überhaupt mit? Immerhin müßte man peu á peu eine Milliarde gerader Zahlen bewiesen haben, um sicher zu stellen, daß alle bisherigen geraden Zahlen der Goldbachschen Vermutung entsprechen. Das heißt man müßte es mathematisch lösen.

Wie wir wissen hat Mathematik recht wenig mit Rechnen zu tun. Mit Rechnen kann man keine allgemein gültigen mathematischen Beweise vollführen. Damit sind bestätigende und nicht bestätigende Beweise für alle Zahlen gemeint. Die Vermutung mathematisch nachzuweisen ist sicherlich eine Herausforderung, vor allem für mich, einen mathematisch eher unbedarften Menschen. Rechnerisch jedoch… Dafür hat man ja eigentlich Rechner, so habe ich mir gedacht.

Was müßte das Programm machen? Eigentlich ja nur alle Zahlen von null aufwärts durchlaufen, ob sie gerade bzw. ungerade sind prüfen. Bei ungeraden Zahlen auf Prim-Eigenschaften prüfen, Primzahlen in ein Prim-Array schieben, bei geraden Zahlen die Summe prüfen. Somit sah der erste Entwurf wie folgt aus:

Wie man sehen kann, geht das Programm in eine Schleife hinein, unterscheidet zwischen geraden und ungeraden Zahlen, untersucht ungerade Zahlen, berechnet gerade Zahlen und fängt wieder von vorne an.

/*
 * prim_srv.c
 */

#include <sys/errno.h>

#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include "prim_srv.h"
#include "errexit.c"
#include "debug.c"
#include "prim.c"
#include "summ.c"

extern int errno;

int main (int argc, char *argv[])
{
    int i = 0;
    int j = 0;

    int* prim_no;
    int* prim_no_tmp;
    int prim_no_size = 0;

    prim_no        = (int*) malloc ((prim_no_size + 1) * sizeof(int));
    prim_no_tmp    = (int*) malloc ((prim_no_size + 1) * sizeof(int));
    prim_no[0]     = 0;
    prim_no_tmp[0] = 0;

    while (1)
    {
        i++;

        if ((i % 2) == 0)
        {
            if (i > 0 && summ (i, prim_no, prim_no_size) == 0)
            {
                printf ("prim_srv - %i - keine summe vorhanden!\n", i);
                break;
            }
        }
        else
        {
            if (prim(i) == 1)
            {
                if ((prim_no_tmp = (int *) malloc ((prim_no_size + 1) * sizeof(int))) == NULL)
                    errexit ("prim_srv - error malloc of prim_no_tmp");

                for (j = 0; j < prim_no_size; j++) prim_no_tmp[j] = prim_no[j];
                prim_no_tmp[prim_no_size++] = i;

                free (prim_no);
                prim_no = NULL;

                if ((prim_no = (int*) malloc ((prim_no_size) * sizeof(int))) == NULL)
                    errexit ("prim_srv - error malloc of prim_no");

                for (j = 0; j < prim_no_size; j++) prim_no[j] = prim_no_tmp[j];

                free (prim_no_tmp);
                prim_no_tmp = NULL;
            }
        }
    }
}

Damit nicht alles in einer riesigen Datei hockt, habe ich kurzerhand die Prim-Eigenschafts- und die Summen-Berechnung in zwei extra Dateien ausgelagert, prim.c und summ.c.

/*
 * berechnet primzahlen
 *
 * z: zu untersuchende zahl
 */

int prim (int z)
{
    int i = 0;
    for (i = (z - 1); i > 1; i--)
    {
        if ((z % i) == 0)
        {
            return 0;
        }
    }
    return 1;
}

Die Untersuchung einer ungeraden Zahl auf ihre Prim-Eigenschaften gestaltet sich recht einfach: man nehme die Zahl, gehe alle Zahlen von der gegebenen Zahl abwärts bis eins und versuche die zu überprüfende ungerade Zahl mit der abwärts laufenden Zahl modulo zu nehmen. Falls der ermittelte Restwert der modulo Operation null ergibt, ist die untersuchte ungerade Zahl keine Primzahl.

Wie man unschwer erkennen kann, ist dieser Algorithmus zwar recht einfach, jedoch auch ziemlich rechenaufwändig. Da sollte man beizeiten das Mathematikbuch herausholen und tatsächlich darüber nachdenken wie man den Algorithmus intelligenter gestalten kann.

/*
 * berechnet Summe
 *
 * z:        zu untersuchende zahl
 * arr:      array mit primzahlen
 * arr_size: groesse des arrays
 */
int summ (int z, int arr[], int arr_size)
{
    int i = 0;
    int j = 0;
    int has_summ = 0;
    int i_j_summ = 0;

    for (i = arr_size; i >= 0; i--)
    {
        i_j_summ = 0;
        for (j = 0; j < arr_size; j++)
        {
            i_j_summ = arr[i] + arr[j]; 

            if (i_j_summ > z) break;
            has_summ = (i_j_summ == z) ? 1 : 0;

            if (has_summ == 1) break;
        }
        if (has_summ == 1) return has_summ;
    }
    return has_summ;
}

Bei der Untersuchung der Summe bei den geraden Zahlen habe ich mir noch weniger Mühe gegeben. Man nehme das Primzahlen Array gehe das äußere von hinten nach vorne, das innere von vorne nach hinten durch und addiere die Primzahlen der äußeren Schleife mit den Primzahlen der inneren Schleife so lange, bis man auf die gesuchte gerade Zahl kommt.

Tja, was nun? Das Programm ist klein, hübsch und läuft vor sich hin. Für 1000000 Zahlen hat mein sechs Jahre alten Notebook ganze 103 Minuten und 28 Sekunden gebraucht. In Ordnung, es hat ja nur einen Prozessor, somit teilen sich das Betriebssystem und die Berechnung die Rechenzeit. Um bis in eine tiefe Milliardenzahl vorzudringen, muß das Programm schneller werden! Es ist jedoch so schrecklich einfach konstruiert, daß da eigentlich kein Potential mehr drin steckt. Ja, bis auf die Berechnung der Prim Eigenschaften und die Berechnung der Summen. Darüber habe ich mich jedoch bereits vorher muckiert… Ach … und das Herumkopieren des dynamisch allozierten Arrays schaut beim Erweitern des Primzahlen Arrays auch recht seltsam aus. Das geht bestimmt intelligenter…

Ein neuer Ansatz muß her. Wer sagt denn, daß das Programm nur auf einer Maschine rechnen soll? Wie wäre es, wenn das Programm als Server dient und nur die Zahlen an den Client zwecks Prüfung bzw. Berechnung schickt? Oder noch besser: die Zahlen an viele Clients verteilt? Doch wie läßt sich das bewerkstelligen, ohne daß man nach jeder Anfrage an den Client ewig auf eine Antwort wartet, um anschließend die nächste Zahl prüfen bzw. berechnen zu lassen? Oder wie soll das Programm mit vielen Clients gleichzeitig umgehen? Sollte man den klassischen Client/Server Kommunikationsweg oder den RPC Weg wählen? Wie soll das Übergeben des Arrays mit Primzahlen an die Berechnung bei der klassischen Kommunikation funktionieren? Wird es überhaupt noch mit RPC gehen? Muß man die vielen Clients durch Generierung mehrerer Prozesse bedienen? Und wie sieht es mit der Rückgabe der Ergebnisse von den Prozessen an den Server? Wäre da die Interprozesskommunioation der beste Weg oder eher simples wegschreiben der Rückgabe auf die Festplatte? Und was ist mit dem Speichern der Ergebnisse in Arrays, wenn mehrere Clients die Ergebnisse im gleichen Augenblick zurück liefern? Sollte man Semaphore einsetzen, um das zu schreiben zu steuern?

Kommt Zeit, kommt Rat.

impressum