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.