3. Wer kann die schnellsten Primzahlen?

Wer kann die schnellsten Primzahlen?

  • V

    SideWinder schrieb:

    Warum stehen die Eingaben nicht einfach in einer Datei und die liest man vor der Prüfung in den Speicher? Soviel RAM muss der TestPC dann eben haben.

    dann macht einer beim einlesen heimliche vorausberechnungen. sagt zum beispiel, daß er in asm einliest, weil das schneller ist und versteckt einen heiimlichen vortest in der einlese-routine, die schonmal alle test-zahlen wegwirft, die zum beispiel gerade sind.

    0
  • V

    Optimizer schrieb:

    Wenn du diese Vorgehensweise erlaubst, nehm ich den Source von isProbablePrime und optimier ihn für ein long. Du könntest natürlich auch einfach verlangen, dass die Auswertung des Programms bewiesen richtig sein muss.

    naja. andere machen auch programmierfehler. und die müssen auch entdeckt werden. da die codes der ersten drei plärtze veröffentlich werden, werden die leute auf plätzen nach dir schon alles dransetzten, deinen code zu widerlegen, wenn er ne lücke hat. schraubste die certainty zu weit hoch, fürchte ich, du bist zu lahm. läßt du sie aber zu weit unten, ist der fehler zu leicht zu finden. um die fehlerjagt überhaupt erst sinnvoll zu machen, muß noch verlangt werden, daß die ausgabe des programms nur von der eingabe abhängt. nicht von uhrzeit oder so. damit einer, der einen fehler findet, ihn reproduzieren kann und die medallie des moglers aberkannt werden kann und die anderen nachrücken.

    0
  • ?

    Wieviele Zahlen werden denn so in der Liste stehen? Man muss sich ja irgendwie überlegen können, ob man sich ein Sieb oder soetwas anlegen sollte, oder ob man jede Zahl einzeln prüfen muss.

    0
  • M

    volkard schrieb:

    SideWinder schrieb:

    Warum stehen die Eingaben nicht einfach in einer Datei und die liest man vor der Prüfung in den Speicher? Soviel RAM muss der TestPC dann eben haben.

    dann macht einer beim einlesen heimliche vorausberechnungen. sagt zum beispiel, daß er in asm einliest, weil das schneller ist und versteckt einen heiimlichen vortest in der einlese-routine, die schonmal alle test-zahlen wegwirft, die zum beispiel gerade sind.

    naja ob er sowas beim einlesen macht oder nach dem einlesen sollte eigendlich doch egal sein oder ? der dateinamen wird als parameter uebergeben. ist also egal, wann er das macht.

    Meep Meep

    0
  • E

    Der Wettbewerb gefällt mir 👍

    Und das mit dem vorgegebenen Generator ist denke ich mal der beste Vorschlag,
    um den Zeitfaktor der Datenbeschaffung zu vereinheitlichen.

    0
  • V

    Meep Meep schrieb:

    naja ob er sowas beim einlesen macht oder nach dem einlesen sollte eigendlich doch egal sein oder ? der dateinamen wird als parameter uebergeben. ist also egal, wann er das macht.

    wird die zeit für's einlesen mitgerechnet, kommt doch wieder das argument, man könne eine sprache mit einer sehr langsamen stream-implemetierung haben.

    0
  • ?

    volkard schrieb:

    Optimizer schrieb:

    Wenn du diese Vorgehensweise erlaubst, nehm ich den Source von isProbablePrime und optimier ihn für ein long. Du könntest natürlich auch einfach verlangen, dass die Auswertung des Programms bewiesen richtig sein muss.

    naja. andere machen auch programmierfehler. und die müssen auch entdeckt werden. da die codes der ersten drei plärtze veröffentlich werden, werden die leute auf plätzen nach dir schon alles dransetzten, deinen code zu widerlegen, wenn er ne lücke hat. schraubste die certainty zu weit hoch, fürchte ich, du bist zu lahm. läßt du sie aber zu weit unten, ist der fehler zu leicht zu finden. um die fehlerjagt überhaupt erst sinnvoll zu machen, muß noch verlangt werden, daß die ausgabe des programms nur von der eingabe abhängt. nicht von uhrzeit oder so. damit einer, der einen fehler findet, ihn reproduzieren kann und die medallie des moglers aberkannt werden kann und die anderen nachrücken.

    Ich habe eigentlich keine Zeit (siehe oben), aber wenn sich der Aufwand als gering rausstellen sollte, könnte ich ein solches Programm einsenden. Evtl. auch außer Konkurrenz nur zum Vergleichen, damit ihr nicht versuchen müsst, meine Berechnungen zu widerlegen. 😉 Würd mich schon mal interessieren, wie sich ein iterativer Algorithmus bei so kleinen Zahlen noch schlägt. Mal schaun, ich leg mich jetzt mal nicht fest. Vielleicht sagt einer aus der Java-Fraktion, er macht sicher mit, dann könnt ihr den Wertebereich ja gleich mal auf die Hälfte eingrenzen. 😃
    Vielleicht übersetz ich das Teil auch nach C#, dann kann ich nen ulong verwenden.

    0
  • V

    Gregor@Home schrieb:

    Wieviele Zahlen werden denn so in der Liste stehen? Man muss sich ja irgendwie überlegen können, ob man sich ein Sieb oder soetwas anlegen sollte, oder ob man jede Zahl einzeln prüfen muss.

    möglichst viele.
    aber andererseits soll das testen nicht ewig dauern. so ne minute oder auch 10 als laufzeit würde ich vorschlagen. ich weiß nicht, wie viele zahlen man in der zeit testen kann. wenn wir pech haben, braucht der schnellste schon ne minute für eine zahl. *g*
    ich hätte gerne, daß die auswertung noch auf dem forentreff geschehen kann, damit man den sieger, der hofentlich da ist, gebührend bewundern kann.

    0
  • F

    Ich werd mal rumprobieren weiß aber noch nicht ob was taugliches rauskommt.

    @volkard: Kannst du mal einen Beispielcode posten mit Implementierung der main-Funktion und sagen wie schnell dein momentaner Algo ist? Nur damit man sich mal an etwas orientieren kann (was sicher eh keiner erreicht^^)

    0
  • V

    FireFlow schrieb:

    @volkard: Kannst du mal einen Beispielcode posten mit Implementierung der main-Funktion und sagen wie schnell dein momentaner Algo ist?

    noch nicht. habe noch keinen guten generator.

    kennt sich einer mit generatoren aus und kann mir einben empfehlen?

    Nur damit man sich mal an etwas orientieren kann (was sicher eh keiner erreicht^^)

    meiner, an dem ich so lange suche, ist noch nicht fertig. ich könnte höchstes meine referenzimplementierung messen, an der ich immer teste. aber die wirste eh schlagen, die hat absichlich keine tricks, damit sie echt sicher richtig rechnet.

    0
  • M

    volkard schrieb:

    ich könnte höchstes meine referenzimplementierung messen, an der ich immer teste.

    das waer ne feine sache und ne datei, wo die zahlen drinnen sind zum irgendwo runterladen. dann haetten wir was zum vergleichen

    Meep Meep

    0
  • S

    Ich mach mit, da ich heute aber keine Zeit mehr habe, bleibt meine aktuelle Version folgende:

    #include <iostream>
using namesapce std;

int main ()
{
    u64 num = NumberFactory.createRandom();
    u64 problems = 0;

    for(u64 i = 2; i < num; ++i)
        if(num % i == 0)
            ++problems;

    if(problems == 0)
        cout << num << " ist eine Primzahl." << endl;
    else
        cout << num << " ist keine Primzahl." << endl;

    return 0;
}

    Ich werde es eventuell noch etwas optimieren ;). Vorher aber noch ein paar Fragen:

    - Haben die Zahlen auch eine gewisse Mindestgröße?
    - Gilt es alle Primzahlen bis zur Maximalgröße vorauszurechnen und die Eregbnisse in einem Baum abzuspeichern?
    - Nein? Auch nicht wenn ich den Baum in der Eingaberoutine als ASM verstecke?
    - Ist Assembler grundsätzlich erlaubt? Welchen genauen Sinn hat der Wettbewerb in diesem Fall?

    Mir fallen sicher noch 100 weitere Dinge ein. Aber du bist ja auch erst beim Generator.

    MfG SideWinder

    0
  • V

    Meep Meep schrieb:

    das waer ne feine sache und ne datei, wo die zahlen drinnen sind zum irgendwo runterladen. dann haetten wir was zum vergleichen

    korrektheit kannste erstemal einfacher vergleichen.
    http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006880

    und falls ein fehler dann passiert ist, mußte den noch finden...

    ich kann ein programm bereitstellen, das primzahlen auswirft, bis die platte voll ist.

    0
  • V

    SideWinder schrieb:

    - Haben die Zahlen auch eine gewisse Mindestgröße?

    ja. 0.

    - Gilt es alle Primzahlen bis zur Maximalgröße vorauszurechnen und die Eregbnisse in einem Baum abzuspeichern?

    ja. aber soviel ram haben wir eh nicht. und die einsendung darf gepackt nicht größer als 64k sein. da passen auch nicht alle rein.

    - Ist Assembler grundsätzlich erlaubt? Welchen genauen Sinn hat der Wettbewerb in diesem Fall?

    java ist ja auch erlaubt.
    ich nehme nicht an, daß asm wirklich viel bringt. durch die divisionen müssen alle durch. da ist der prozessor lahm, gal welche sprache. und wenn du einen baum-trick machst, würdest du den baum in asm schreiben? ich erwarte von dir, daß du gerade wegen der hochsprache tricks einbauen kannst, die man in asm nie hinkriegen würde.

    0
  • O

    alle antworten entnehme ich aus dem,w as bisher gesagt wurde:

    - Haben die Zahlen auch eine gewisse Mindestgröße?

    nein, aber sie werden sich vorwiegend in einem "niedriegren" bereich aufhalten

    - Gilt es alle Primzahlen bis zur Maximalgröße vorauszurechnen und die Eregbnisse in einem Baum abzuspeichern?

    alle tricks sind erlaubt

    - Ist Assembler grundsätzlich erlaubt? Welchen genauen Sinn hat der Wettbewerb in diesem Fall?

    alle sprachen sind erlaubt

    0
  • S

    ja. 0.

    Das heißt wenn ich meinen optimalen Algo gefunden habe fülle ich noch bis 64KB mit if(i == blubb) return blubb; auf?

    MfG SideWinder

    0
  • ?

    volkard schrieb:

    Die Eingabezahlen werden nicht gleichverteilt sein, sondern kleine Zahlen kommen deutlich häufiger vor. Die Eingabezahlen werden mit x=r()*r()+r() erzeugt, wobei r() gleichverteilte Zahlen zwischen 0 und 2^31-1 zurückliefert.

    BTW: Bevor da einer anfängt, eine Sonderbehandlung für Zahlen <2^30 oder so zu programmieren... Vielleicht solltest du ein bischen genauer sagen, was du unter "kleine Zahlen kommen deutlich häufiger vor" verstehst. IMHO kommt es auch bei dieser Art der Generation von Zufallszahlen nahezu nicht vor, dass eine Zahl <2^50 oder so erzeugt wird. ...nur so am Rande. Bei deinen Beispielzahlen könnte man leicht in eine falsche Richtung denken.

    0
  • V

    SideWinder schrieb:

    Das heißt wenn ich meinen optimalen Algo gefunden habe fülle ich noch bis 64KB mit if(i == blubb) return blubb; auf?

    wenn du dich nicht dafür schämst, ja.

    0
  • F

    Was muss alles in dem Archiv drin sein? 64Kb sind wenig^^ Reicht der Source und nen Comment zu den Compile-Einstellungen? Welcher Compiler wird beim Test genutzt?

    Ich mein fertige Binarys testen kanns net sein da kann man bescheissen 😉

    0
  • O

    volkard schrieb:

    - Gilt es alle Primzahlen bis zur Maximalgröße vorauszurechnen und die Eregbnisse in einem Baum abzuspeichern?

    ja. aber soviel ram haben wir eh nicht. und die einsendung darf gepackt nicht größer als 64k sein. da passen auch nicht alle rein.

    oha, hab das grad erst gesehen...wieviel ram haben wir, und wieviele ram braucht man ca um alle primzahlen bis dahin darzustellen?^^

    0
Anmelden zum Antworten