Wer kann die schnellsten Primzahlen?

[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.

[Gregor@Home]

Wieviele Zahlen werden denn so in der Liste stehen? Man muss sich ja irgendwie überlegen können, ob man sich ein Sieb oder soetwas anlegen sollte, oder ob man jede Zahl einzeln prüfen muss.

[Meep Meep]

volkard schrieb:

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.

naja ob er sowas beim einlesen macht oder nach dem einlesen sollte eigendlich doch egal sein oder ? der dateinamen wird als parameter uebergeben. ist also egal, wann er das macht.

Meep Meep

[energyzer]

Der Wettbewerb gefällt mir

Und das mit dem vorgegebenen Generator ist denke ich mal der beste Vorschlag,
um den Zeitfaktor der Datenbeschaffung zu vereinheitlichen.

[volkard]

Meep Meep schrieb:

naja ob er sowas beim einlesen macht oder nach dem einlesen sollte eigendlich doch egal sein oder ? der dateinamen wird als parameter uebergeben. ist also egal, wann er das macht.

wird die zeit für's einlesen mitgerechnet, kommt doch wieder das argument, man könne eine sprache mit einer sehr langsamen stream-implemetierung haben.

[Gast]

volkard schrieb:

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.

Ich habe eigentlich keine Zeit (siehe oben), aber wenn sich der Aufwand als gering rausstellen sollte, könnte ich ein solches Programm einsenden. Evtl. auch außer Konkurrenz nur zum Vergleichen, damit ihr nicht versuchen müsst, meine Berechnungen zu widerlegen. Würd mich schon mal interessieren, wie sich ein iterativer Algorithmus bei so kleinen Zahlen noch schlägt. Mal schaun, ich leg mich jetzt mal nicht fest. Vielleicht sagt einer aus der Java-Fraktion, er macht sicher mit, dann könnt ihr den Wertebereich ja gleich mal auf die Hälfte eingrenzen.
Vielleicht übersetz ich das Teil auch nach C#, dann kann ich nen ulong verwenden.

[volkard]

Gregor@Home schrieb:

Wieviele Zahlen werden denn so in der Liste stehen? Man muss sich ja irgendwie überlegen können, ob man sich ein Sieb oder soetwas anlegen sollte, oder ob man jede Zahl einzeln prüfen muss.

möglichst viele.
aber andererseits soll das testen nicht ewig dauern. so ne minute oder auch 10 als laufzeit würde ich vorschlagen. ich weiß nicht, wie viele zahlen man in der zeit testen kann. wenn wir pech haben, braucht der schnellste schon ne minute für eine zahl. *g*
ich hätte gerne, daß die auswertung noch auf dem forentreff geschehen kann, damit man den sieger, der hofentlich da ist, gebührend bewundern kann.

[FireFlow]

Ich werd mal rumprobieren weiß aber noch nicht ob was taugliches rauskommt.

@volkard: Kannst du mal einen Beispielcode posten mit Implementierung der main-Funktion und sagen wie schnell dein momentaner Algo ist? Nur damit man sich mal an etwas orientieren kann (was sicher eh keiner erreicht^^)

[volkard]

FireFlow schrieb:

@volkard: Kannst du mal einen Beispielcode posten mit Implementierung der main-Funktion und sagen wie schnell dein momentaner Algo ist?

noch nicht. habe noch keinen guten generator.

kennt sich einer mit generatoren aus und kann mir einben empfehlen?

Nur damit man sich mal an etwas orientieren kann (was sicher eh keiner erreicht^^)

meiner, an dem ich so lange suche, ist noch nicht fertig. ich könnte höchstes meine referenzimplementierung messen, an der ich immer teste. aber die wirste eh schlagen, die hat absichlich keine tricks, damit sie echt sicher richtig rechnet.

[Meep Meep]

volkard schrieb:

ich könnte höchstes meine referenzimplementierung messen, an der ich immer teste.

das waer ne feine sache und ne datei, wo die zahlen drinnen sind zum irgendwo runterladen. dann haetten wir was zum vergleichen

Meep Meep