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.

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.

i found a really nice howto for a chroot jail to lock users into their home directories. the funny thing is that the user does not know that he is in a jail. it looks like a usual unix environment. you have also the possibility to allow scp, sftp and/or rsync. 

=> cyberciti.biz

I took half an hour and hacked a little script the easy and st00pid way:


#!/bin/bash
#
# Name: del-except-3
# Author: pes
# Date: 08.04.2010
# Description
# Deletes all files in ${searchpath} except the last 3
#

debug=1
searchpath=$1

if [ ! -d ${searchpath} ]; then
    echo "${searchpath} does not exist"
    exit 1
fi

cd ${searchpath}

last3=`ls -tr | tail -3`

set -- ${last3}

last3_1=$1
last3_2=$2
last3_3=$3

if [ ${debug} -ne 0 ]; then
    echo "last 3 files in ${searchpath}"
    echo " 1: $last3_1"
    echo " 2: $last3_2"
    echo " 3: $last3_3"
fi

for i in `ls -1`; do
    if [ "${i}" != "${last3_1}" ]; then
        if [ "${i}" != "${last3_2}" ]; then
            if [ "${i}" != "${last3_3}" ]; then
                echo "rm ${searchpath}/${i}"
                rm ${i}
            fi
        fi
    fi
done

is there a smart combination of shell commands? someting that does not look that stupid?

wir entwickeln java applikationen, d.h. unsere winxp rechner haben dem entsprechend 3gig ram und verwenden eclipse. bei den vorhergehenden tests sah alles in ordnung aus, keine schwierigkeiten mit der entwicklungsumgebung.

nach dem rollout haben diverse user festgestellt, dass wenn man eclipse starten möchte (egal welche version), das startup-fensterchen kommt und prompt wieder verschwindet o.O oder wenn man glück hat, kommt ein recht grosses popup, in dem sämtliche startup-parameter drin stehen mit der fehlermeldung “java vm could not be started” oder ähnlichem. da denkt sich jeder: “wtf?” wenn man den Xmx parameter in der eclipse.ini auf 840mb stellt, kommt es hoch. jedoch alles über diesem wert…

nach der befragung von onkel google hat sich herausgestellt, dass ein paar andere virenscanner ein recht ähnliches problem aufweisen. unter anderem panda und kaspersky (link). wenn man “protection against unknown threats” abstellt bzw. die virenscanner komplett deinstalliert, ist das problem gelöst. da frage ich mich doch wie zum teufel kann man einen virenscanner auf den markt bringen und vertreiben, der das dynamische allozieren zusätzlichen speichers begrenzt? wtf?

plötzlich sehe ich eine frau recht erschrochen von links nach rechts den zebrastreifen überqueren. sie lächelt leicht schockiert, hält sich ihre hand vor die brust. wirft nochmal kurz einen blick zum fahrzeug auf der linken fahrbahn, das ebenfalls dort steht, schlendert weiter.

leicht irritiert fällt mein blick auf den mercedes fahrer, also das fahrzeug, auf das die frau ihren blick geworfen hat. schulterzuckend denke ich mir: “kei ahnig, hat vielleicht stark gebremst und die frau erschrocken”. nachdem die frau die strasse überquert hat, dachte ich mir, dass der mercedes fahrer wieder seines weges geht. doch interessanterweise hat er sein fahrzeug auf den bürgersteig gelenkt und ist dort neben 90 grad zur strassenseite geparkten fahrzeugen stehen geblieben.

noch irritierter fällt mein blick auf den hintermann des mercedes fahrers. laut fahrzeug-form konnte man noch erkennen, dass es ein recht neues modell des suzuki swift war. “war”, weil die motorhaube einer ziehharmonika glich. extrem sauer hat der hintermann gas gegeben und hat sein fahrzeug zwischen den stehenden mercedes fahrer und die parkenden autos gelenkt. doch nein, er hat nicht gebremst. keineswegs. ungebremst hat der psycho einen fünfer golf so stark gerammt, daß zusätzlich das daneben stehende fahrzeug beschädigt wurde.

alter falter… naja, unfall. passiert schon mal. kann man nix machen. aber gas geben und dabei zwei weitere fahrzeuge beschädigen? wtf?!?