Wer kann die schnellsten Primzahlen?

[SideWinder]

Walli schrieb:

Lyrix schrieb:

Oder irre ich mich?

Ja. Man kann etwas in asm schneller machen als der Compiler, aber auch gewaltig langsamer. Man muss schon gut asm können um besser als der Compiler zu sein. Ausserdem verbaut man sich mit asm viele geile Optimierungen, die man auf Hochsprachenebene machen kann, da diese damit eben nicht so ersichtlich und locker zu implementieren sind. Ausserdem ist hier ganz sicher der Algorithmus entscheidend...

Der Trick dahinter ist ja erst nach dem Compiler weiterzuoptimieren.

MfG SideWinder

[Walli]

SideWinder schrieb:

Der Trick dahinter ist ja erst nach dem Compiler weiterzuoptimieren.

Bringt auch eher wenig, würde ich behaupten. Das Quentchen, was man da raus holt, büßt man an Übersichtlichkeit ein und sieht dann am Ende vielleicht eine Super-Optimierung nicht, weil der Code mit inline-asm verseucht ist.

[energyzer]

Naja der Prim Algo wird ja vermutlich nicht all zu lang - insofern kann man
ihn doch vollständig in C++ implementieren, optimieren und compilieren.
Danach (und ich denke so meint es auch SideWinder) kann man dann das De-
kompilat weiter optimieren, so dass man sowohl in C++ als auch in ASM alles
ausgereizt hat.

[Walli]

Ich glaube zwar nicht, dass man mit solchen Optimierungen hier einen Blumentopf gewinnen kann, aber ich lasse mich gerne vom Gegenteil überzeugen . Der bessere Algorithmus wirds machen.

[energyzer]

Ich denke auch eher, dass die Mathematik siegen wird

[otze]

mit der mathematik komm ich leider nimmer viel weiter, ich schaff es zwar, die möglichkeiten im vorfeld schon massiv einzuschränken, aber bei einem suchlauf einer zahl n muss ich immernoch bis zu n/3-1 abfragen machen

[FireFlow]

Nochmal die Frage: Muss es für jede Primzahl immer klappen, oder muss es nur für eine bestimmte (nicht im Vorfeld bekannte) Testreihe funktionieren?

[energyzer]

Ich würde es besser finden, wenn es immer funktioniert. Bei bestimmten Ver-
fahren muss man dann halt nachprüfen...

[otze]

es muss für alle primzahlen klappen können, oder wie schon gesagt wurde: "der code wird öffentlich gemacht, damit andere fälle finden können, in denen es nicht funktioniert"

[Lyrix]

Nene ich kann in Assample rnur Standards (und da muss ich zugeben, dass ich da sehr viele Mankos hab, da mich diese Programmiersprache überhaupt nicht anspricht, .... Doch leider muss ich es ja in der Schule amchen ).
Das mit der Zeit erwähnte mal unsere Lehrerin, dass man mit einem optimalen Code wesentlich weniger Rechenzeit haben kann als in C oder C++.

Wie gesagt, ich weiss es nicht, und ich kann auch nur vom 'Hören' etwas dazu sagen, wollte aber dennoch mal darauf hinweisen, weil es hätte ja etwas dran sein koennen

[FireFlow]

otze schrieb:

es muss für alle primzahlen klappen können, oder wie schon gesagt wurde: "der code wird öffentlich gemacht, damit andere fälle finden können, in denen es nicht funktioniert"

Ich hab grade mal zum Testen ein Programm auf dem Miller-Rabin-Verfahren geschrieben welches noch nicht optimiert ist. Es überprüft jede Zahl auf eine Primzahl von 0 bis 0xffffffff und läuft grade im Hintergrund. Ich schreibe das ganze Testweise in eine Datei, wobei ich vermute dass die Ausgabe hierbei nochmal viel Zeit kostet (hab gerade 20MB).
Das Programm hat keinen direkten Fehler da es zufällige Zeugen sucht dass die Zahl keine Primzahl ist. Hab mir das nicht alles selber ausgedacht ich werd morgen (äh heute) mal den Code posten.

/edit 30mb *lol*
/edit hmm ich sollte im voraus nachdenken nach meiner rechnung würde es einige tage benötigen

mfg fireflow

[volkard]

FireFlow schrieb:

Das Programm hat keinen direkten Fehler da es zufällige Zeugen sucht dass die Zahl keine Primzahl ist.

gleiche eingaben müssen gleiche ausgaben erzeugen. benutzt du einen zufall, der von uhrzeit oder dergleichen abhängt, wird die einsendung nicht angenommen.
es muß gewährleistet sein, daß wenn einer eine eingabe findet, bei der dein programm einen fehler zeigt, es jedesmal bei dieser eingabe einen fehler zeigt.

Hab mir das nicht alles selber ausgedacht ich werd morgen (äh heute) mal den Code posten.

ich würde sagen, daß es nicht sehr gut ist, so lange vor dem einsendeschluss mit fertigem code zu kommen. könnte eine schlimme spaßbremse sein.

na, andererseits, wenn du wirklich ein Miller-Rabin-Verfahren veröffentlichst, wird das schon seinen grund haben. entweder haste festgestellt, daß es doch nicht so flott ist, oder biste davon überzeugt, daß es nicht schneller geht für zahlen ab 2^50 und wills nach oben allen die gleiche chance geben und den kampfschauplatz nach unten zu den kleinen zahlen hin verlegen, wo eh alles viel spaßiger ist.

[FireFlow]

Dann benutz ich eben immer den gleichen Seed was solls^^ Ich wünsche dann viel Spass beim Fehler suchen.

Ich bin davon überzeugt dass ich nicht als mein Code einschicken will was auf einem Verfahren beruht weöches schon oft genug auskommetiert ist. Außerdem ist es eben nicht 100% sicher ob das Ergebniss stimmt.

[energyzer]

Du bist dir auch sicher, dass dein Code mit Zahlen bis 2^63 zurecht kommt? Weil
das finde ich das größte Hindernis - besonders beim Miller-Rabin Verfahren.
Versuche mich da der Problematik gerade auf Binär-Ebene zu nähern und hab schon
einiges an Abkürzungen gefunden. Mag sein, dass es da ganz einfache Lösungen
gibt, aber ich will das jetzt erstmal selbst lösen. So machts schließlich am
meisten Spaß

[FireFlow]

Starting: 1120604557
Ending:   1120604649
Rang:     [0, 16777215[
Found:    1077871 Prims

Villeicht stimmts auch gar net^^

[Shade Of Mine]

Sorry falls ich die Frage/Antwort überlesen haben sollte:

Wieviele Zahlen bekomme ich denn als Eingabe. Sprich: wo liegt die Obergrenze? Allzuviele, sprich 2^32 werden es ja wohl nicht sein, weil dann das testen zu lange dauert, oder?

Mehr als 2^32 würde meinen Algo tot machen, also lieber weniger nehmen

[rapso]

Shade Of Mine schrieb:

Sorry falls ich die Frage/Antwort überlesen haben sollte:

Wieviele Zahlen bekomme ich denn als Eingabe. Sprich: wo liegt die Obergrenze? Allzuviele, sprich 2^32 werden es ja wohl nicht sein, weil dann das testen zu lange dauert, oder?

Mehr als 2^32 würde meinen Algo tot machen, also lieber weniger nehmen

falls du die range meinst, die lag bei 2^63-1 afaik.

rpaso->greets();

[volkard]

Shade Of Mine schrieb:

Wieviele Zahlen bekomme ich denn als Eingabe. Sprich: wo liegt die Obergrenze? Allzuviele, sprich 2^32 werden es ja wohl nicht sein, weil dann das testen zu lange dauert, oder?

als eingabe kriegste so 3 oder 10 zahlen. die definieren aber nur die zufallszahlengenerator und irgendwie (vermutlich von dir nicht auslesbar) die anzahl der zu testenden zahlen.

falls du nur fürchtest, daß dein cache überläuft, ich kann mir nicht vorstellen, daß es 2^32 zahlen werden. aber ich weiß ja nicht, wie ausgefuchst schnell eure verfahren werden. wenn ihr 2^32 zahlen in 10 minuten testen könnt, kann es passieren, daß die sequenz auch 2^32 lang wird.

Mehr als 2^32 würde meinen Algo tot machen, also lieber weniger nehmen

falls es nur ein cache ist, den kannste zur not immer nach 2^32 einträgen flushen.
ach, riskier es, würde ich sagen. wenn ich richtig sehe, werden die zahlen über 2^50 so affig lange rechnen, daß wir froh sein können, in 10 min eine davon zu schaffen.

[Shade Of Mine]

volkard schrieb:

falls es nur ein cache ist, den kannste zur not immer nach 2^32 einträgen flushen.

Ist aber kein cache.

Mein ganzer Algo baut eigentlich darauf auf, dass ich X zahlen zum testen bekomme wobei X in einem bestimmten Bereich, vorzugsweise <2^32 liegt. Alles darüber wird da nämlich teuerer. Und teurer heisst, dass ich mich dumm und dämlich zahle wenn dann nur 2^10 oder so zahlen kommen...

Ich werde also auf max 2^32 zahlen gehen.

Aber mein Beitrag ist sowieso egal - da ich zu wenig über Primzahlen weiss kann ich eh nicht mit den Profis mithalten (aber spaß habe ich trotzdem daran, und das ist ja das wichtigste).

@rapso:
range ist klar, es ging mir um die Anzahl der Zahlen die ich Testen muss und sagen können muss ob es eine Primzahl ist. Volkard hat mich eh verstanden

[energyzer]

Ich glaube kaum, dass jemand einen so ausgefuchsten Algo hat, dass er über 2^32
Zahlen in einer nicht mehr messbaren kleinen Zeit schafft Also können wir das
IMHO ruhig als max. Grenze annehmen - Einwände? Andererseits würde ich es gut
finden, wenn die Algos die Überschreitung von 2^32 Zahlen überleben - auch wenn
sie dann langsam werden.

// Edit: Es geht mir um die Anzahl der Zahlen und nicht um deren Größe!