Wer kann die schnellsten Primzahlen?
-
Ich habe die Zahlen bis 2^32 nun in 22 Sekunden geprüft. Das eben war eine fehlerhafte Messung in der ich noch ein paar Debugsachen drin hatte.
-
Walli schrieb:
Ich habe die Zahlen bis 2^32 nun in 22 Sekunden geprüft. Das eben war eine fehlerhafte Messung in der ich noch ein paar Debugsachen drin hatte.
Wow. Wieviele findest du denn bis 2^32?
-
wie erreichst du 22s? schätzt du die zahlen nur?
-
volkard schrieb:
#include <iostream> #include <cstdlib> #include <cmath> using namespace std; typedef long long i64; int bigrand(){ return rand()|(rand()<<8)|(rand()<<16); } i64 megarand(){ return (i64(bigrand())<<31)|bigrand(); } int main() { for(i64 max=10;max>0;max*=10){ int c=0; for(int i=0;i<1000000;++i){ i64 x=megarand(); x>>=rand()%50; if(x<max) ++c; } cout<<"<"<<max<<": "<<double(c)/10000<<'%'<<endl; } return 0; }<10: 0%
<100: 0.0056%
<1000: 0.1167%
<10000: 1.2614%
<100000: 7.3182%
<1000000: 14.3283%
<10000000: 21.2051%
<100000000: 28.0856%
<1000000000: 35.0752%
<10000000000: 41.9018%
<100000000000: 48.7581%
<1000000000000: 55.7992%
<10000000000000: 62.7778%
<100000000000000: 69.5799%
<1000000000000000: 76.6079%
<10000000000000000: 83.5278%
<100000000000000000: 90.332%
<1000000000000000000: 96.9142%also alle größenbereiche so ungefäht gleich oft.
die ganz kleinen, also unter 10000 benachteiligt, damit man nicht sofort zu tabellen greifen muss.wäre das ok?
Sieht auf den ersten Blick zumindest sehr gut aus.
-
otze schrieb:
wie erreichst du 22s? schätzt du die zahlen nur?
Vielleicht hat er im Gegensatz zu dir aber auch bloß ein Dual-System mit zwei Intel Pentium 3,2 GHz und fängt auf einem Rechner von oben nach unten und auf dem anderen von unten nach oben an
MfG SideWinder
-
hab ein sieb hochgeladen, falls jemand ne referenzimplementierung braucht.
windows: http://www.volkard.de/download/primeGenerator.exe
linux: http://www.volkard.de/download/primeGeneratoraufruf: primeGenerator 100
und ausgabe ist
"2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 "
statt 100 darf man auch größere zahlen nehmen.die geschwindigkeit ist vermutlich höher als eure lösung, aber es ist ja auch ein sieb des eratosthenes. kann also nur aufeianderfolgende prim zahlen schnell finden. ihr macht ja ne funktion, die die zahlen durcheiander kriegt und jede zahl einzeln testen muss, weil sie gar nicht hintereinander sind.
-
Da fällt mir ein: Caching in irgendeiner Weise erlaubt? Was natürlich dann auch ein Durchschnittsergebnis aus ~50 Messugnen benötigt um aussagekräftig zu werden. Sonst kann man Glück und Pech haben.
MfG SideWinder
-
Also ich messe mit so ner Timerklasse die irgendwer mal gepostet hatte. Wie genau die ist, k.A. Deckt sich jedenfalls halbwegs mit der Stoppuhr.
#ifndef TIMER_HPP #define TIMER_HPP #include <ctime> #include <iostream> class Timer { unsigned n; clock_t start; public: Timer(unsigned number = 0) : n(number), start(clock()) {} ~Timer() { std::cout << "timer " << n << ": " << static_cast<float>(clock() - start) / CLOCKS_PER_SEC << " sec." << std::endl; } }; #endifAber ich glaube ich muss mein Ergebnis mit den 2^32 nochmal zurückziehen. Irgendwie sind das zu wenige Primzahlen, die der findet...
-
FireFlow schrieb:
Was muss alles in dem Archiv drin sein? 64Kb sind wenig^^
naja, gepackt ist das schon einiges. viel größer kann's aber nicht sein, da sonst die leute mit monster-tabellen ankommen.
Reicht der Source und nen Comment zu den Compile-Einstellungen?
reicht völlig. das ist mir sogar am liebsten.
Welcher Compiler wird beim Test genutzt?
keine ahnung. mal sehen, was wir beim forentreff zur verfügung haben. es haben bisher immer ein genügend leute rechner mitgehabt. nsbesondere moderne rechner. das testen auf meiner alten hardware ergibt eh keine guten ergebnisse. ich hoffe, daß jemand linux und windows auf einem rechner hat. ich denke mal, vom gcc für linux und vom msvc für windows können wir ausgehen. aber wie gesagt, ich weiß nichtmal, ob überhaupt auf dem treffen getestet werden kann.
weil ich nix über die hardware sagen kann, kann man auch mehrere einsendungen abgeben. vielleicht will SideWinder ja 512MB ram dazu benutzen, eine riesige std::map als cache anzulegen. und wenn der rechner nur 256MB hat, kackt das programm ab. deswegen sollte er zur sicherheit dann auch eine version ohne cache einreichen.
[quote]Ich mein fertige Binarys testen kanns net sein da kann man bescheissen ;)/quote]
wie bescheißen?das problem ist, daß einer vielleicht was in lisp oder forth oder algol66 einreicht und wir keinen compiler dafür beschaffen können.
-
otze schrieb:
überleg ich auch grad. besten algo für einmalige 4byte werte raussuchen, und dann mal schauen...
falls du nur eine primzahlenliste brauchst, die speicher man wohl optimal als char-array von primzahlendifferenzen. und rutsch dann zu programmbeginn einmal durch und summiert und kopiert es in ein int-array.
-
wie bescheißen?
Von den Compileroptionen angefangen (Optimiert auf Pentium, etc.) über die Eingabe bei der man bereits alle geraden Zahlen kickt (bzw. wenn die Eingabe überhaupt dem User überlassen wird gilt sowieso wer am schnellsten von stdin lesen kann). Außerdem kann ich Algorithmen anfertigen die eine gewisse Prozentchance haben richtige zahlen auszuspucken. Dann optimiere ich nur noch um einerseits noch schnell genug und andererseits noch genügend Chance zu haben. Damit die Chance noch höher wird schicke ich dreimal die selbe Binary ab und behaupte ein anderer Algo käme zur Verwendung und ihr testet alle bis es bei einem rein zufällig funktioniert.
MfG SideWinder
-
SideWinder schrieb:
Da fällt mir ein: Caching in irgendeiner Weise erlaubt?
ja. es zu verbieten wäre zu willkürlich.
aber es trifft ja eh nur die sehr kleinen zahlen, wo man chache-treffer erwarten kann.
-
volkard schrieb:
otze schrieb:
überleg ich auch grad. besten algo für einmalige 4byte werte raussuchen, und dann mal schauen...
falls du nur eine primzahlenliste brauchst, die speicher man wohl optimal als char-array von primzahlendifferenzen. und rutsch dann zu programmbeginn einmal durch und summiert und kopiert es in ein int-array.
gute idee
aber sind die primzahlen nicht hinterher schon sehr weit voneinander entfernt?
-
otze schrieb:
gute idee
aber sind die primzahlen nicht hinterher schon sehr weit voneinander entfernt?wenn ich mich recht erinnere, sind dir durchschnittlichen lücken bei primzahlen der größen x ungefäht ln(x) groß.
aber du brauchst ja die größten lücken. genaueres auf http://primes.utm.edu/notes/gaps.htmlaber ich fürchte, es ist piepegal, ob du 30k primzahlen speicherst oder berechnest. weiß es aber nicht.
-
http://www.forum-3dcenter.org/vbulletin/showthread.php?t=95859
rapso->greets();
-
juhu, ich hab meinen algo dazu gebracht, nichtmehr >10mins zu brauchen:
range 1-10.000.000
primzahlen:664579
zeit:9s*stolz*
-
warum eigentlich hauptsächlich die relativ kleinen zahlen testen?
die anzahl der primzahlen zwischen 0 und 2^32 ist verschindend gering im gegensatz zu den primzahlen zwischen 2^32 und 2^64. wenn jetzt ein großteil der zu testenden zahlen im kleinen bereich liegt wird man ja fast dazu gezwungen tabellen anzulegen und zu versuchen die in 64kb zu packen
zwischen 0 und 2^32 liegen ca. 200000000 primzahlen
zwischen 2^32 und 2^64 liegen ca. 400000000000000000 primzahlen
nur mal so zum vergleich. (anzahl primzahlen zwischen 0 und x: x/ln(x))
-
klein ist relativ, wenn der hier vorgestellte zufallsgenerator hauptsächlich zahlen ausserhalb des 32 bit bereichs erzeugt(um genau zu sein 65%)
-
otze schrieb:
klein ist relativ, wenn der hier vorgestellte zufallsgenerator hauptsächlich zahlen ausserhalb des 32 bit bereichs erzeugt(um genau zu sein 65%)
naja das bedeutet, er erzeugt 35% innerhalb des 32 bit bereiches, normalverteilt wären es weit unter 0,1%. eine tabelle wird sich auf jedenfall lohnen, imo.
-
---vergesst es... dummer fehler---
@otze: Hast du dafür einen Cache genutzt oder nicht? ^^