Wer kann die schnellsten Primzahlen?
-
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? ^^
-
EnERgYzEr schrieb:
@otze: Hast du dafür einen Cache genutzt oder nicht? ^^
damit hab ich den cache berechnet(wenn du damit nen cache in form einer datei mit vorberechneten werten meinst)
//edit hab aber auch nen absoluten primitiv algo benutzt^^
//edit2 nur halt hinterher männlich aufgemotzt^^
-
Wollen wir denn jetzt erstmal volkards letzten Generator als Vorlage nehmen?
Zusätzlich bräuchten wir eine Anzahl an Nummern, die wir testen sollen, um
schon mal eine ungefähre Vergleichbarkeit zu schaffen.Dann kann der Spaß beginnen
@otze: War so gedacht, ob du nur einmalig die Primzahlen in dem Bereich gezählt
hast oder für jede im Bereich den isPrime Test gemacht hast. Aus deiner Antwort
entnehme ich Fall Nr. 1
-
man könnte ab jetzt ja auch erstmal so im geheimen werkeln, und dann erst wenige tage vor beginn mit werten protzen...
//edit jede zahl im bereich wurde auf primzahl getestet
-
borg schrieb:
warum eigentlich hauptsächlich die relativ kleinen zahlen testen?
weil das auch die anforderung für eine isPrime() wäre, die man in die c++-standardbibliothek aufnehmen könnte.
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
eigentlich nicht. unter 100000 waren ja nur 7%. also kannste schonmal nur maximal 7% zeit sparen mit cachen oder tabellen.
zu erwarten ist aber, daß die großen zahlen so viel überproportional mehr zeit fressen als die mini-zahlen, daß am ende eigentlich kaum gewinn da ist.andererseits wird bei praktisch gleichen implementierungen für große zahlen sich vielleicht doch ein trick für kleine zahlen auswirken. ich denke gar nicht an tabellen oder cachen. das ist mir zu popelig und irrelevant. ich bin aber sicher, daß man für zahlen unter 2^32 eine schnellere implemetierung machen kann als für zahlen über 2^32.
bool isPrime(i64 n){ if(n<2 hoch 32) return isPrimeSmall(n); else isPrimeBig(n); }ich bin auch sicher, daß man sich im ram eine tabelle mit 30k primzahlen sowas von schnell bauen kann (ein mikrosekündchen oder so), daß jeder versuch, es in den code zu packen, pure zweitverschwendung ist.
würde ich mitmachen, dann mit einem algo, der gar nix cachet und keine tabellen benutzt. ich darf doch außer konkurrenz mitmachen?
das häufen der kleinen zahlen ist einfach, damit man den siegercode dann sich kopieren kann auf die eigene platte und immer nehmen kann, wenn man mal primzahlen braucht. manche sorten hashtables sollen ja primzahlen als größe haben. plant der user 1200000 einträge, ruft er HashTable ht(1200000) auf und ich reserviere mir erstmal mehr platz, damit sie nur zu 80% voll wird, also 1200000/80%==1500000 und suche dann möglichst schnell die nächste primzahl. gäbe es eine isPrime(), die in allen größenbereichen einigermaßen tauglich ist, würde ich mir ein loch in den bauch freuen und einfach die benutzen. gäbe es nur eine für zahlen unter 1000 und eine, die für echt große zahlen taugt aber nicht für kleine, würde ich traurig sein.
vielleicht können wir am samstag ja im zuge der vorträge auch die ganzen angewandten tricks vorstellen und Jester erklärt uns die mathematik dahinter.
aber werkeln könnt ihr auf jeden fall schon. unabhängin vom generator wird es so sein, daß ihr ne funktion für saugroße zahlen braucht und vielleicht fallen euch auch feinere funktionen für kleinere zahlen ein.
-
Also die Schätzfunktionen scheinen für kleine Zahlen grottenlangsam zu sein. Unter 100-binär-stelligen Zahlen braucht man damit gar nicht anfangen.
(bei einer Wahrscheinlichkeit von 0.5^40, dass eine erkannte Primzahl doch keine ist)
-
Optimizer schrieb:
Also die Schätzfunktionen scheinen für kleine Zahlen grottenlangsam zu sein. Unter 100-binär-stelligen Zahlen braucht man damit gar nicht anfangen.
(bei einer Wahrscheinlichkeit von 0.5^40, dass eine erkannte Primzahl doch keine ist)das beruhigt mich.
0.5^40 ist gerade so am rande, was man wagen könnte.
dann kann's ja anfangen mit dem spaß. *freu*
-
Also wie ist das jetzt genau?
Muß das Programm *immer* die korrekte Antwort liefern, oder genügt es die Antwort mit hoher Wahrscheinlichkeit zu liefern (sprich: beim testen liegt man immer richtig).
-
Jester schrieb:
Also wie ist das jetzt genau?
Muß das Programm *immer* die korrekte Antwort liefern, oder genügt es die Antwort mit hoher Wahrscheinlichkeit zu liefern (sprich: beim testen liegt man immer richtig).
klar ist, daß jemand, der einen probalisistischen test macht und gewinnt, seinen gewinn aberkannt kriegt, und die nächsten nachrücken, wenn einer seine lücke findet.
aber ich sehe keine chance, beweise zu fordern. Optimizer könnte ja kommen und sagen, daß er drei wochen lang seinen rechner hat laufen lassen und mit einem testprogramm nachgewiesen hat, daß sein probalistischer test den gesamten bereich abdeckt.
als zwischenweg könnte man fordern, daß gegebenenfalls das testprogramm auch gezeigt werden muß, damit wir wenigstens innerhalb von drei wochen feststellen können, ob das wahr ist?
-
Okay, das wollte ich wissen. Es genügt also nicht mit hoher Wahrscheinlichkeit das richtige zu produzieren, sondern man muß immer das richtige produzieren. Ob man das jetzt beweisen will oder nicht... ist ja ein ganz anderes Thema.
-
Jester schrieb:
Okay, das wollte ich wissen. Es genügt also nicht mit hoher Wahrscheinlichkeit das richtige zu produzieren, sondern man muß immer das richtige produzieren. Ob man das jetzt beweisen will oder nicht... ist ja ein ganz anderes Thema.
naja, ganz so isses leider nicht.
angenommen, du findest ein verfahren, das nur 10 lücken bis 2^60 hat. klar ist, daß du den sieg aberkannt kriegst, sobald einer die lücke findet. und ich werde den lückenfinder bauen und als bildschirmschoner installieren.
nur ist 2^60 so groß, daß selbst bei 4MHz und einem Test pro Takt noch 268435456 sekunden vergehen, was 204 jahre sind, um alles zu testen.
gilt weiter moores gesetz, sind es in 15 jahren aber nur noch 74 tage und weil du ja 10 lücken hattest, nur 7,4 tage und das kriegen wir dann schon geknackt. also ein mogel-sieg dürfte nur ein sieg auf zeit sein.und das ganzt ohne mathematische überlegungen, wo genau die lücken stecken könnten. könnte mir einen erheblichen faktor vorstellen, wenn man den fehler eines genau gegebenen verfahrens sucht.
was du eigentlich wissen willst, ist ob riemanns vermutung als wahr angenommen werden darf. ja, darfste, wenn es nach mir geht.
-
Wie gross ist jetzt der Zahlenbereich? [0, 2^63]?
-
Ponto schrieb:
Wie gross ist jetzt der Zahlenbereich? [0, 2^63]?
[0,2^63-1], damits in den signed 64-bitter von java passt.
-
In welchen C++-Datentyp passen den soviele Zahlen rein?
Zarniwoop
-
long long
-
achso.
-
Auf vielen Maschinen reicht auch ein long.