Wer kann die schnellsten Primzahlen?

volkard

Vielleicht sollten wir mal einen Programmierwettbewerb machen, wo alle Sprachen und so mitmachen können.

---snip----

Schreibe ein Programm, das von der Standardeingabe eine Liste von Zahlen einliest und auf die Standardausgabe zu jeder Zahl ausgibt, ob sie eine Primzahl ist (0 für falsch, 1 für wahr). Für Sprachen, die EOF schlecht erkennen, wird sichergestellt, daß die letzte Zahl in der Eingabe die 0 ist und die 0 nicht vorher auftritt.

Beispieleingabe:
10
13
1
19
20
0
Ausgabe:
0
1
0
1
0
0

edit: stattdessen wird es einen standardisierten generator geben. siehe weiter hinten im thread.

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.

Bewertungskriterium: Geschwindigkeit.
Erlaubte Sprachen: alle.
Erlaubte Hilfsmittel: alle.
Erlaubte Tricks: alle.

Einschränkungen:
- Die Größe einer Einsendung darf gepackt 64k nicht überschreiten.
- Gleiche Eingaben müssen gleiche Ausgaben erzeugen.

Eingesandt werden muss der Quellcode, um im Falle eines Gewinnes veröffentlicht zu werden. Zusätzlich darf eine ausführbare Datei für Windows oder Linux eingesandt werden. Als Packformate werden angenommen:
.tar.gz
.tar.bz2
.zip
.rar

Jeder Einsender darf mehrere Einsenungen einsenden. Es zählt seine beste.

Der Einsendeschluss ist Freitag, 22.7.05 umd 12:00h.

Ausgewertet wird auf dem Forumstreffen.

---snip----

Wer würde denn da mitmachen?

du gewinnst doch sowieso. oder darfst du dabei selbst nicht mitmachen?

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

Jester

Ich finds ne gute Idee!

Wieviele Zahlen kommen denn als Eingabe?

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?

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?

VOLKART WAS KRIEGT DER GEWINNER ÜBERHAUPT???

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

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.