Wer kann die schnellsten Primzahlen?

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!

Ponto

EnERgYzEr schrieb:

Ich glaube kaum, dass jemand einen so ausgefuchsten Algo hat, dass er über 2^32
Zahlen in einer nicht mehr messbaren 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.

Du meinst, dass die Obergrenze von 2^63-1 auf 2^32 gesenkt wird?

Ponto

volkard schrieb:

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.

Das verstehe ich nicht so ganz? Ein trivialer Algorithmus zum Testen von 9223371994482243049 (2^63 -1 = 9223372036854775807) braucht auf meinem P4 2.4 GHz 38 Sekunden. Ich verrate wohl nichts, wenn ich sage, dass der Algorithmus im Grunde so aussieht:

for (unsigned i = 3; i * i < test; i += 2) {
  if (test % i == 0) {
     break;
  }
}

energyzer

Ponto schrieb:

EnERgYzEr schrieb:

Ich glaube kaum, dass jemand einen so ausgefuchsten Algo hat, dass er über 2^32
Zahlen in einer nicht mehr messbaren 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.

Du meinst, dass die Obergrenze von 2^63-1 auf 2^32 gesenkt wird?

Nein, dass würde den ganzen Spaß nehmen Die Anzahl der Zahlen die ausge-
rechnet werden sollen, könnten wir auf ein max. von 2^32 setzen.

Zarniwoop

Bei mir(WinXp, Dev-C++) zeigt

typedef unsigned long long ulong;
cout << sizeof(ulong);

lediglich 8 byte an. Bei 8*4 = 32 reicht das nicht aus, um Zahlen wie 2^63 zu speichern. Wie kann ich das ändern/mache ich etwas falsch?

Zarniwoop

rapso

Zarniwoop schrieb:

Bei mir(WinXp, Dev-C++) zeigt
typedef unsigned long long ulong;
cout << sizeof(ulong);
lediglich 8 byte an. Bei 8*4 = 32 reicht das nicht aus, um Zahlen wie 2^63 zu speichern. Wie kann ich das ändern/mache ich etwas falsch?

Zarniwoop

wie kommst du auf 4? byte hat 8 bit, also 8*8=64

rapso->greets();

Zarniwoop

Ah sc***** - stimmt!

Man bin ich doof!

Zarniwoop

FireFlow

Ponto schrieb:

volkard schrieb:

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.

Das verstehe ich nicht so ganz? Ein trivialer Algorithmus zum Testen von 9223371994482243049 (2^63 -1 = 9223372036854775807) braucht auf meinem P4 2.4 GHz 38 Sekunden. Ich verrate wohl nichts, wenn ich sage, dass der Algorithmus im Grunde so aussieht:
for (unsigned i = 3; i * i < test; i += 2) {
  if (test % i == 0) {
     break;
  }
}

Ich braue 0,01ms