Einzeiler zur Berechnung von beliebig vielen Primzahlen

Heute ist Stammtischzeit:
Jeden Donnerstag 20:30 Uhr hier im Chat.
Wer Lust hat, kann sich gerne beteiligen. ;)
  • Hallo zusammen,

    bei der Recherche zu etwas ganz Anderem bin ich auf folgenden Einzeiler

    Code
    procedure main();every write(!(p := 1, a := [2])| 1(|(p +:= 2), not(p % !a = 0), put(a, p)), "\t[", *a, "]") \1000;end

    der Programmiersprache Icon gestoßen, der die ersten 1000 Primzahlen in Bruchteilen einer Sekunde berechnet und ausgibt.

    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

  • Einzeiler zur Berechnung von beliebig vielen Primzahlen? Schau mal ob du hier fündig wirst!

  • Hallo Framp,

    zum Glück gibt es didaktisch wesentlich bessere Beispiele für lesbaren Programmcode. Eigentlich überzeugen die meisten Quellcodes in Icon durch hohe Strukturiertheit und Lesbarbeit.

    Dieser Einzeiler besticht aber durch seine Geschwindigkeit, der - in einer anderen Programmiersprache umgesetzt, um zum gleichen Ergenbnis zu führen - deutlich umfangreicher ist.

    Ich gebe Dir aber recht: Wer so programmiert, hat einen an der Schüssel. Man braucht sicherlich länger, diese Code zu verstehen, als verständlichen Code selber zu programmieren.

    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

  • Klar, in jeder Sprache kann man kryptischen Code erzeugen. Gibt ja sogar Wettbewerbe dazu.

    Da Du mich bzgl Icon jetzt angekifft hast habe mir mal icon installiert und q&d versucht den Code zu verstehen. Dabei habe ich den Code wie folgt umformatiert und kommentiert. Waere nett wenn Du mir da meine paar offenen Fragen beantworten würdest (mit ??? im Code gekennzeichnet) :-).


    Das Pythonäquivalent sieht übrigends wie folgt aus.

    Code
    p=1
    a=[2]
    c=1
    print "%s [%s]" % (a[0], len(a))
    while c < 1000:
        p+=2
        if not any(p % item == 0 for item in a):
            a.append(p)
            print "%s [%s]" % (p, len(a))
            c+=1
  • Hmm ....


    wie schnell war Dein Pgm noch gleich ;) ...
    Und der Quellcode passt notfalls auch in eine Zeile :) ...


    aber vor allem: er ist verständlich :) ... (für mich zumindest :lol: )
    Und jetzt mach mir mal die Freude und lass das Ganze mit 10 Mio laufen:


    ... lass die Bildschirmausgabe weg:

    Code
    dirk@saturn:~$ time ./prime
    Total: 664579
    
    
    real	0m0.318s
    user	0m0.300s
    sys	0m0.004s
    dirk@saturn:~$


    und versuch mich zu beeindrucken :) ...

    cu,
    -ds-

  • Hallo Framp,

    meine Deutung des Einzeilers - ich sage bewusst "Deutung", da mir solch kryptischer Code echt fremd ist:
    every leitet eine Schleife ein wie in allen anden Sprachen

    Code
    for i:= 1 to 1000 do


    ist in Icon

    Code
    every i := 1 to 1000 do

    Bei Icon gibt es die Möglichkeit, in einer every-Schleife sog. Generatoren einzupacken, die jeglichen Inhalt mithilfe des Generator-Operators !-ausspucken. Das heißt, dass sich Startwert und Endwert aus anderen Informationsquellen erschließen (müssen), so wie in dem Einzeiler auch.

    Der Beschränkungsoperator \ lässt dann nur die dahinter stehende Anzahl an Ergebnissen zu. Das heißt, every liefert 1000 Ergebnisse, dann ist every abgeschlossen.

    Der Alternativ-Operator | ist eines der bedeutendsten Merkmale der Programmiersprache Icon. Man kann den umgangssprachlich so beschreiben:
    Ich möchte gern, dass irgendein Ausdruck abgearbeitet wird | Huch, hat nicht funktioniert, dann mach was anderes Sinnvolles oder Fehlermeldung oder Abbruch

    (p := 1, a := [2]) setzt die zu untersuchende Zahl auf 1 und setzt die erste Primzahl 2 in die Primzahlliste a. Da vor der Klammer auch der Generator-Operator ! steht, wird hier die Liste a mit einer - der ersten - Primzahl 2 als erstes Ergebnis der 1000 geforderten zurückgegeben. Mehr gibt's dann nicht.

    Beim zweiten Durchlauf (every lässt grüßen) passiert hier gar nichts und die Alternative hinter dem Alternativ-Operator | wird durchgeführt.

    Hier passiert dann so einiges.

    Übrigens bedeutet 1() keine Endlosschleife sondern bezeichnet eine Funktion namens 1, die den ersten Ausdruck hinter der Klammer "(" als Ergebnis liefert - aber alle anderen Ausdrücke, die durch Komma getrennt vorliegen, werden auswertet.

    Beispiel-Code (vollkommen enthirnt - zeigt aber das Prinzip):

    Code
    $define deutsch 1
    $define englisch 2
    
    
    procedure main()
       write("Das deutsche Wort ", deutsch("Haus", "house"), " bedeutet in englisch ", englisch("Haus", "house"))
    end

    Es gibt hier definitiv keine Funktion deutsch() oder englisch() aber eben 1() und 2().


    Zurück zum Alternativ-Zweig:

    Code
    |(p +:= 2),
    not(p % !a = 0),
    put(a, p)),
    "\t[", *a, "]"


    Code
    |(p +:= 2)


    Die Variable p wird um 2 erhöht, ist also 3, 5, 7, 9, ... bis denn 1000 Primzahlen als Ergebnis geliefert worden sind

    Code
    not(p % !a = 0)


    Ermittelt den Rest bei der Division von p und a. Lässt es sich ohne Rest teilen, isses keine Primzahl, not negiert das Ergebnis. In Icon bedeutet das, dass dieser Ausdruck gescheitert ist und bei diesem Druchlauf nichts geschrieben wird, der Prüfling p als Kandidat einer Primzahl verworfen wird. Zur Erinnerung: Wir befinden uns in einer write()-Funktion - jedes Ergebnis wird ausgegeben.
    Wenn die beiden Zahlen bei der Division einen Rest ergeben => p ist eine Primzahl
    sonst: keine Primzahl
    Thread-andere-einzeiler-zur-berechnung-von-beliebig-vielen-primzahlen?pid=159145#pid15914
    Jetzt steht vor dem a der Generator-Operator, d.h, der Prüfling p wird durch alle bisher ermittelten Primzahlen, abgelegt in a, dividiert. Die erste Division ohne Divisionsrest sorgt für den vorzeitigen Abbruch der Prüfung von p.

    Wenn p = 3 ist, ist 3 % 2 = 1 , 3 ist also eine Primzahl.
    Analog bei p = 5, p = 7.

    Bei p = 9: 9 % 2 = 1 aber 9 % 3 = 0 => 9 ist keine Primzahl

    In der "Funktion" 1() passiert aber noch mehr:

    Code
    put(a, p)),


    Setzt die Primzahl p in die Primzahlliste a

    Analog bei p = 5, p = 7. Das heißt, die Primzahlliste wird schrittweise größer a := [2, 3], a := [2, 3, 5], a := [2, 3, 5, 7]

    Bei p = 9: 9 % 2 = 1 aber 9 % 3 = 0 => 9 ist keine PrimzahlThread-andere-einzeiler-zur-berechnung-von-beliebig-vielen-primzahlen?pid=159145#pid15914

    Code
    "\t[", *a, "]"


    setzt den Cursor auf die nächste Position (wenn nicht anders definiert auf die nächste durch 8 teilbare Position)
    schreibt [Thread-andere-einzeiler-zur-berechnung-von-beliebig-vielen-primzahlen?pid=159145#pid15914
    Der Größenoperator * ermittelt die Größe der danach stehenden Variablen. Bei Listen ist es die Anzahl der darin enthaltenen Werte. *zeichenkette ist die Anzahl der darin enthaltenen Zeichen etc.

    Sehr viel Deutung für

    Code
    procedure main();every write(!(p := 1, a := [2])| 1(|(p +:= 2), not(p % !a = 0), put(a, p)), "\t[", *a, "]") \1000;end

    Somit ist Deine Deutung bis auf die Bedeutung von 1() korrekt. :thumbs1:
    Thread-andere-einzeiler-zur-berechnung-von-beliebig-vielen-primzahlen?pid=159145#pid15914
    In Icon spricht man übrigens nicht von Arrays sondern von Listen - meint aber natürlich das Gleiche.

    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

    2 Mal editiert, zuletzt von Andreas (13. Oktober 2017 um 23:58)

  • Vielen Dank für die ausführliche 'Deutung'.

    Der | Operator scheint ein ziemliches Alleinstellungsmerkmal zu sein für Icon. Mal sehen ob ich mal etwas Zeit finde mich etwas in Icon einzulesen. Bin leider gerade anderweitig busy.

  • Hallo Framp, hallo Dreamshader,

    am Rande angemerkt: Eure Software verwendet Zahlen bis zu einem Grenzwert, bis zu der Primzahlen ermittelt werden. Mein Programm ermittelt eine bestimmte Anzahl an Primzahlen. Das macht den Vergleich der Rechengeschwindigkeiten etwas schwierig.

    Fangen wir mal an:
    168 [letzte Primzahl 997]
    Mit Ausgabe:


    Ohne Ausgabe


    1000 [letzte Primzahl 7919]
    Mit Ausgabe:
    real 0m0.073s
    user 0m0.065s
    sys 0m0.001s

    Ohne Ausgabe
    real 0m0.057s
    user 0m0.051s
    sys 0m0.009s


    10000:
    104729 [10000]

    Mit Ausgabe
    real 0m4.573s
    user 0m4.403s
    sys 0m0.104s


    Ohne Ausgabe
    real 0m4.300s
    user 0m4.292s
    sys 0m0.005s

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

  • Hallo Dreamshader,


    und versuch mich zu beeindrucken :) ...

    gerne doch - aber es lassen sich nur gleiche Algorithmen miteinander vergleichen. Ich werde heute Abend Deinen Algorithmus in Icon übertragen und mal schauen, was dabei an Zeiten herauskommt.

    Momentan hänge ich in der Schweiz herum und warte darauf, dass hier irgendwas weitergeht ... [Däumchendreh-Modus an]


    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.


  • ...
    gerne doch - aber es lassen sich nur gleiche Algorithmen miteinander vergleichen. ...
    ...

    Hi Andreas,
    da ich nicht schuld sein will, wenn Du aus lauter Verzweiflung hinter den nächsten ICE springst: die Ergebnisse waren von meinem Ubuntu-Laptop ( Dualcore bei ca. 1.6 GHz ) :) ...
    Das Ergebnis auf meinem Raspi - altes Modell B mit 512 MB RAM, ohne Übertaktung - sieht so aus:

    10 Mio:

    Code
    pi@raspberrypi ~ $ time ./prime
    Total: 664579
    
    
    real 0m3.056s
    user 0m2.910s
    sys 0m0.000s
    pi@raspberrypi ~ $

    bzw. bei 1000:


    bei 1000 ohne Ausgabe:

    Code
    pi@raspberrypi ~ $ time ./prime
    Total: 168
    
    
    real 0m0.014s
    user 0m0.000s
    sys 0m0.000s
    pi@raspberrypi ~ $

    //EDIT: vielleicht noch ein hint: das Ganze basiert auf dem Sieb des Eratosthenes - Divisionen sind durch Bitoperatoren ersetzt, da die (auf Assemblerebene) schneller sind ...

    cheers,
    -ds-

  • Hi Dreamshader,

    [/Däumchendreh-Modus aus]

    Deinen Algorithmus habe ich mir jetzt angeschaut - aber ehrlich gesagt, Zeilen wie diese

    Code
    if ( p[a>>3] & (1<<(a&7))) continue;
    for (b=a+a; b<MAX_PRIMES; b+=a)
    p[b>>3]=p[b>>3]|(1<<(b&7));
                 tot++;

    fallen für mich auch unbter "Security by obscurity"

    Den Sieb des Eratosthenes - im ganz klassischen Sinn - programmiere ich so:

    Code
    $define MAX 10000000
    
    procedure main()	p := list(MAX)	every i := 2 to sqrt(MAX) do if /p[i] then every j := i*i to MAX by i do p[j] := 0	every i := 2 to MAX do if /p[i] then write(i)end

    Mit dem Icon-Interpreter durchgeführt erhalte ich folgende Zeiten:

    Mit Ausgabe
    real 0m17.543s
    user 0m4.955s
    sys 0m2.497s

    Ohne Ausgabe:
    andreas@andreas-N73SV:~$ time SiebEra

    real 0m2.958s
    user 0m2.927s
    sys 0m0.029s

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

    Einmal editiert, zuletzt von Andreas (14. Oktober 2017 um 01:43)

Jetzt mitmachen!

Du hast noch kein Benutzerkonto auf unserer Seite? Registriere dich kostenlos und nimm an unserer Community teil!