Wer kann die schnellsten Primzahlen?

[primzahl.4]

hab-bald-ferien 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.

öhm, was ist x dann? double, long long, float, int? unsigned?

double und float kann man ja schonmal ausschließen!

[Jester]

Wie ich volkard kenne würde ich auf ein

typedef unsigned long long u64;
u64 x = ...;

tippen.

[volkard]

SeppSchrot schrieb:

Ich mache nicht mit, weil ich weiß, dass DU schon seit langer Zeit dabei bist, einen Primzahlenalgo auf Geschwindigkeit zu optimieren.

deswegen wäre es gemein, würde ich mitmachen. in der tat.
also mache ich nicht mit.

trauste dich nun?

[Meep Meep]

hola

also 64 bit zahlen bei der eingabe ?
ist die Standardeingabe die eingabekonsole ?

Meep Meep

ps: wieviele zahlen werden da dem programm uebergeben ?

[volkard]

hab-bald-ferien schrieb:

öhm, was ist x dann? double, long long, float, int? unsigned?

ich weiß nicht, wie er in der sprache heißt, die du nehmen magst.
er sollte ganzzahlen bis 2^64-1 halten können.

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.

[volkard]

Meep Meep schrieb:

ps: wieviele zahlen werden da dem programm uebergeben ?

so viele, daß störfaktoren wie der programmstart irrelevant werden. sagen wir mal ungefähr eine minute laufzeit.

[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