Wer kann die schnellsten Primzahlen?

[otze]

hmmm ich mach mal mit

[dali]

Also doch nicht zwischen 0 und 2^31-1 wenn 64 Bit zulässt?

[_GERNER_]

VOLKART WAS KRIEGT DER GEWINNER ÜBERHAUPT???

[Gast]

Schreibe ein Programm, das von der Standardeingabe eine Liste von Zahlen einliest

IMHO keine gute Idee. Da geht erst schon mal die halbe Zeit für das Parsen drauf und der ganze Programmablauf hängt dann sehr stark davon ab, wie gut der Zeichenstrom in eine Zahl geparsed werden kann, ob vielleicht Java vorher einen Unicode-String macht, wie gut die Stream-Implementierungen überhaupt sind... damit verlagerst du das Gewicht ganz böse auf das ganze I/O.

Erlaubte Tricks: alle.

Ok, dann kriegst du von mir ein Programm, was eine Zahl nur mit einer Fehlerquote von (1/2)^60 als Primzahl identifizieren kann. Ist das auch erlaubt?
Wenn du Glück hast, irrt sich dann mein Programm einmal und du darfst es disqualifizieren. Aber da würde ich vorher schon den ganzen Wertebereich durchprobieren. Ein bisschen genauer sollten die Kriterien schon noch sein. Es gibt mathematisch bewiesene Primzahlen und Primzahlen "industrieller Qualität", wie man so schön sagt. Ein Irrtum in diesem kleinen Wertebereich ist derart unwahrscheinlich, dass ich mit so einem iterativen Algorithmus wahrscheinlich alle exakten schlagen kann.

Aber ich habe eh keine Zeit, mich zu beteiligen. Die Prüfungen stehen vor der Tür.

[volkard]

Meep Meep schrieb:

ist die Standardeingabe die eingabekonsole ?

nicht zwingend die konsole (mit maus und tastatur). kann auch umgeleitet sein. wird sogar zum messen umgeleitet sein.

also das, was man in c++ cin nennt und wovon man in c mit scanf liest. das, was man fein umleiten kann, wie in

generator.exe | deinProgramm.exe > ausgabe.txt

[volkard]

GERNER schrieb:

VOLKART WAS KRIEGT DER GEWINNER ÜBERHAUPT???

wer bei dieser konkurrent gewinnt, ist doch schon belohnt genug, oder?

[Jester]

Optimizer schrieb:

IMHO keine gute Idee. Da geht erst schon mal die halbe Zeit für das Parsen drauf und der ganze Programmablauf hängt dann sehr stark davon ab, wie gut der Zeichenstrom in eine Zahl geparsed werden kann, ob vielleicht Java vorher einen Unicode-String macht, wie gut die Stream-Implementierungen überhaupt sind... damit verlagerst du das Gewicht ganz böse auf das ganze I/O.

Quark. Das Primtesten ist viel aufwändiger als das Einlesen, also wird bei ausreichender Menge an Zahlen die es zu testen gilt das testen die meiste Zeit in Anspruch nehmen.

[otze]

also der eingabestring hat die form zahl \n zahl \n ...zahl \n 0 ?

oder kommen die zahlen nacheinander beim programm an?

[Meep Meep]

und was waere wenn du die zahlen binaer in eine datei legst, die wir dann auslesen muessen ? dann waere das geparse weg.

Meep Meep

[Gast]

Jester schrieb:

Optimizer schrieb:

IMHO keine gute Idee. Da geht erst schon mal die halbe Zeit für das Parsen drauf und der ganze Programmablauf hängt dann sehr stark davon ab, wie gut der Zeichenstrom in eine Zahl geparsed werden kann, ob vielleicht Java vorher einen Unicode-String macht, wie gut die Stream-Implementierungen überhaupt sind... damit verlagerst du das Gewicht ganz böse auf das ganze I/O.

Quark. Das Primtesten ist viel aufwändiger als das Einlesen, also wird bei ausreichender Menge an Zahlen die es zu testen gilt das testen die meiste Zeit in Anspruch nehmen.

Die Menge der Zahlen beeinflusst nicht den Anteil des Parsens an dem gesamten Programmablauf. Ich gebe zwar zu, es nicht gemessen zu haben, aber endlos lange wird ne 2^64 - 1 Zahl nicht zum auswerten brauchen, parsen kann ich Sprachen wie in Java aber vergleichsweise teuer werden.

[volkard]

Optimizer schrieb:

Schreibe ein Programm, das von der Standardeingabe eine Liste von Zahlen einliest

IMHO keine gute Idee. Da geht erst schon mal die halbe Zeit für das Parsen drauf und der ganze Programmablauf hängt dann sehr stark davon ab, wie gut der Zeichenstrom in eine Zahl geparsed werden kann, ob vielleicht Java vorher einen Unicode-String macht, wie gut die Stream-Implementierungen überhaupt sind... damit verlagerst du das Gewicht ganz böse auf das ganze I/O.

hmm. kann sein, daß das ganze unternehmen schiefgeht.
aber wie können wir sonst andere sprachen mitmachen lassen?

naja, noch ist viel zeit, was zu ändern. vielleicht besser, man gibt eine implementierung von rand() an und läßt das prog einige primzahlen zählen und liest nur den seed ein?

Erlaubte Tricks: alle.

Ok, dann kriegst du von mir ein Programm, was eine Zahl nur mit einer Fehlerquote von (1/2)^60 als Primzahl identifizieren kann. Ist das auch erlaubt? ;)[/quote]
es kann nicht verhindert werden, fürchte ich. naja, der quellcode muß ja dabei sein, vielleicht erkennt man fehler oder lücken, die man dann gezielt jagen kann.

[volkard]

Jester schrieb:

Quark. Das Primtesten ist viel aufwändiger als das Einlesen, also wird bei ausreichender Menge an Zahlen die es zu testen gilt das testen die meiste Zeit in Anspruch nehmen.

egal. die java-fraktion soll nicht nachher sagen können "aua, ihr habt uns benachteiligt wegen der streams, deshalb haben wir nicht mitgemacht".

machen wir also einen standardisierten zahlengenerator. ärgerlich wäre es natürlich, wenn dann keiner mit ner anderen sprache mitmacht.

[Jester]

Was heißt standardisierter Generator? Und wenn der dann in irgendeiner Sprache langsamer generiert als in einer anderen isses auch wieder fies, oder?

Die Eingaben müssen schon irgendwie von außen kommen.

[SideWinder]

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.

MfG SideWinder

[Gast]

volkard schrieb:

naja, noch ist viel zeit, was zu ändern. vielleicht besser, man gibt eine implementierung von rand() an und läßt das prog einige primzahlen zählen und liest nur den seed ein?

Das hört sich gut an. Den Seed einzulesen wäre eine einmalige Sache.

es kann nicht verhindert werden, fürchte ich. naja, der quellcode muß ja dabei sein, vielleicht erkennt man fehler oder lücken, die man dann gezielt jagen kann.

Nichts hindert mich daran, den Wertebereich durchzutesten.
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.

Jester schrieb:

Was heißt standardisierter Generator? Und wenn der dann in irgendeiner Sprache langsamer generiert als in einer anderen isses auch wieder fies, oder?

Die Eingaben müssen schon irgendwie von außen kommen.

IMHO aber weniger fies als die wirklich beträchtlichen Unterschiede bei der I/O. Ich glaub sogar nicht mal, dass ein Generator in bestimmten Sprachen grob langsamer sein kann. Das sind doch nur ein paar simple Berechnungen und Bitoperationen.

[Gregor@Home]

volkard schrieb:

falls jemand ne sprache vorweist, die nen unsigned 64-bit-typ nicht kennt, aber nen signed 64-bit-typ hat, können wir auch leicht als obergrenze auf 2^63-1 gehen. das ändert nicht viel.

Java hat nur einen vorzeichenbehafteten 64-Bit-Datentyp (ich bin mir allerdings gar nicht sicher, ob das so ein großes Problem ist). Aber frag erst mal, ob überhaupt jemand von der Javafraktion mitmachen möchte. Ich habe leider auf absehbare Zeit wohl keine Zeit für soetwas, werde also vermutlich nicht mitmachen.

[volkard]

Jester schrieb:

Was heißt standardisierter Generator? Und wenn der dann in irgendeiner Sprache langsamer generiert als in einer anderen isses auch wieder fies, oder?

ich denke an was wie

#include <iostream>
using namespace std;

typedef long long i64;

int main()
{
    i64 x1,a1,m1;
    cin>>x1>>a1>>m1;
    i64 x2,a2,m2;
    cin>>x2>>a2>>m2;
    i64 x3,a3,m3;
    cin>>x3>>a3>>m3;
    int anzahl;
    cin>>anzahl;
    int ergebnis=0;
    for(int i=0;i<anzahl;++i){
        i64 x=x1*x2+x3:
        if(isPrime(x))
            ++ergebnis;
        x1=(x1+a1)%m1;
        x2=(x2+a2)%m2;
        x3=(x3+a3)%m3;
    }
	return 0;
}

da läßt sich nix optimieren, wenn ich richtig sehe. dreimal % wird gerechnet. also drei divisionen. die sind in jeder sprache gleichlahm, die zeit geht nur im prozessor drauf.
und der generator ist auch einfach genug, daß man ihn in jeder sprache bauen kann, in der man auch ne primzahlenfunktion bauen kann.

edit: und er ist deutlich schneller als das primzahlengeschehen. darum fällt er gar nicht ins gewicht.

[volkard]

Gregor@Home schrieb:

Java hat nur einen vorzeichenbehafteten 64-Bit-Datentyp (ich bin mir allerdings gar nicht sicher, ob das so ein großes Problem ist).

ok. dann sorgen wir dafür, daß die größte zahl irgendwo unter 2^63-1 ist.

Aber frag erst mal, ob überhaupt jemand von der Javafraktion mitmachen möchte.

mag jemand aus der java-fraktion mitmachen?

[volkard]

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.

[volkard]

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.