Wer kann die schnellsten Primzahlen?
-
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.
-
-
Also ich würde Assambler ausschliessen, weil Assambler denke ich weit aus Zeitersparender mit dem ''Rechnen'' ist, was ich zumindest bis jetzt gehört habe.
Oder irre ich mich?
-
Lyrix schrieb:
Also ich würde Assambler ausschliessen, weil Assambler denke ich weit aus Zeitersparender mit dem ''Rechnen'' ist, was ich zumindest bis jetzt gehört habe.
Oder irre ich mich?Wenn du das denkst, dann kannst du ja eine Lösung mit Assembler implementieren. Ich denke, dass dir das nahezu nichts bringen wird.
-
Lyrix schrieb:
Oder irre ich mich?
Ja. Man kann etwas in asm schneller machen als der Compiler, aber auch gewaltig langsamer. Man muss schon gut asm können um besser als der Compiler zu sein. Ausserdem verbaut man sich mit asm viele geile Optimierungen, die man auf Hochsprachenebene machen kann, da diese damit eben nicht so ersichtlich und locker zu implementieren sind. Ausserdem ist hier ganz sicher der Algorithmus entscheidend...
-
Walli schrieb:
Lyrix schrieb:
Oder irre ich mich?
Ja. Man kann etwas in asm schneller machen als der Compiler, aber auch gewaltig langsamer. Man muss schon gut asm können um besser als der Compiler zu sein. Ausserdem verbaut man sich mit asm viele geile Optimierungen, die man auf Hochsprachenebene machen kann, da diese damit eben nicht so ersichtlich und locker zu implementieren sind. Ausserdem ist hier ganz sicher der Algorithmus entscheidend...
Der Trick dahinter ist ja erst nach dem Compiler weiterzuoptimieren.
MfG SideWinder
-
SideWinder schrieb:
Der Trick dahinter ist ja erst nach dem Compiler weiterzuoptimieren.
Bringt auch eher wenig, würde ich behaupten. Das Quentchen, was man da raus holt, büßt man an Übersichtlichkeit ein und sieht dann am Ende vielleicht eine Super-Optimierung nicht, weil der Code mit inline-asm verseucht ist.
-
Naja der Prim Algo wird ja vermutlich nicht all zu lang - insofern kann man
ihn doch vollständig in C++ implementieren, optimieren und compilieren.
Danach (und ich denke so meint es auch SideWinder) kann man dann das De-
kompilat weiter optimieren, so dass man sowohl in C++ als auch in ASM alles
ausgereizt hat.
-
Ich glaube zwar nicht, dass man mit solchen Optimierungen hier einen Blumentopf gewinnen kann, aber ich lasse mich gerne vom Gegenteil überzeugen
. Der bessere Algorithmus wirds machen.
-
Ich denke auch eher, dass die Mathematik siegen wird
-
mit der mathematik komm ich leider nimmer viel weiter, ich schaff es zwar, die möglichkeiten im vorfeld schon massiv einzuschränken, aber bei einem suchlauf einer zahl n muss ich immernoch bis zu n/3-1 abfragen machen