c++.de :: Schnelle Rechenoperationen mit großen zahlen

volkard Moderator 22:16:08 27.05.2012 Titel:

SpR schrieb:

könnte jemand mal den Namen oder nen Link zu den Algorithmen geben, welcher schneller als Karatsuba sind, heißt nicht das ich sie verstehe würde mir aber gerne einmal das Prinzip ansehen.

Wikipedia "Karastuba" verlinkt auf die schnelleren.
Und sagt, daß bei Deinen 4096 Bits die schnelleren noch gar nicht so greifen.

Unregistrierter

Okay vielen Dank schöne Pfingsten noch.
MfG SpR

nachtfeuer Moderator 14:46:19 30.05.2012 Titel:

Ich würde empfehlen, erstmal zu gucken, und zu verstehen, wie die Karatsuba-Multiplikation arbeitet, denn sie läßt sich überraschend angenehm und leicht in Assembler umsetzen.

Darüber hinaus ist es sehr hilfreich, Binärmultiplikation aufzuschreiben und zu verstehen. Also 1*1 ist ja noch einfach. Aber wieviel ist 11 * 11 (binär)? oder
wieviel wäre dann 1111111111111111 * 1111111111111111?

volkard Moderator 14:49:24 30.05.2012 Titel:

nachtfeuer schrieb:

Darüber hinaus ist es sehr hilfreich, Binärmultiplikation aufzuschreiben und zu verstehen.

Binär? Wollten wir nicht übungshalber das 256-er-System nehmen und dann das 4294967296-er benutzen?

nachtfeuer Moderator 22:44:06 30.05.2012 Titel:

volkard schrieb:

Binär? Wollten wir nicht übungshalber das 256-er-System nehmen und dann das 4294967296-er benutzen?

4294967296-er? Ist das nicht etwas veraltet? - Bei 32Bit Compi mit SSE ginge zumindest ein 2^128-er Zahlensystem.
Aber Avx...256er Zahlensystem als Einstiegsdroge und dann weiter machen mit 2^256er.

Man fragt sich gelegentlich, was eigentlich so ein funktionaler Sprachinterpreter wie z. B. der ghci Haskellinterpreter intern so treibt, wenn man mit so Begriffen wie 2*(2^256)^3 + 4 * (2^256)^2 + 2* (2^256) usw. herumrechnet oder z.B. (2^256)^64 -1.

(aber 256er? da hat wohl einer mit 8 Bit Compies angefangen was?)

Christoph Moderator 00:04:22 31.05.2012 Titel:

nachtfeuer schrieb:

Man fragt sich gelegentlich, was eigentlich so ein funktionaler Sprachinterpreter wie z. B. der ghci Haskellinterpreter intern so treibt, wenn man mit so Begriffen wie 2*(2^256)^3 + 4 * (2^256)^2 + 2* (2^256) usw. herumrechnet oder z.B. (2^256)^64 -1.

Im Zweifelsfall steckt oft libgmp dahinter, weil man es selber nur schwer schneller hinbekommt. Bei ghc ist das so.

nachtfeuer Moderator 11:01:51 31.05.2012 Titel:

Mir fällt noch ein, es gab Anfang letzten Jahres einen ganz ähnlichen Thread,
( http://www.c-plusplus.de/forum/280689 )
und ein Problem des TOs war glaub ich, neben der fehlenden Erfahrung mit ein bißchen Herumprobieren, dass die Bitmultiplikation/Addition nicht gleich verstanden wurde, dabei ist das Prinzip eigentlich sehr einfach, wenn man es mal auf Papier gemacht hat. Wenn man die Binärmultiplikation/Addition verstanden hat, und das entgegenkommen der Prozessorbefehle, versteht sich auch der Asm-Code gleich viel besser.

Wenn man von großen Zahlen wie (2^256)^64 lediglich eins abziehen will, und das ist nicht ganz trivial, kann man die Zahl von hinten nach vorn nach der nächstbesten binären 1 absuchen. Bei Zahlen wie 2^x steht die 1 natürlich ganz vorne bzw. ganz links. Bei der Zahl (2^256)^64 - 1 steht dagegen die erste 1 ganz hinten bzw. ganz rechts.

Man sucht also von rechts die nächstbeste 1, macht aus dieser (theoretisch) eine Null und aus dem Rest ( den folgenden Nullen) per

Assembler:
not reg

eine 1.
Direkt auf der Registerebene (der Abschnitt mit der 1) macht man (praktisch) einfach ein

Assembler:
dec reg

(dec reg ginge natürlich auch bei den restlichen, hinteren (nuller) Abschnitten, da ja 00 - 1 FF sein muß)
(und ginge so ganz ohne Carryflag (aber mit CX also Cindy, der kleinen Zähltochter vom Graf Zahl...) )