Hi,
Zitat von
Hawkeye219:
Das war ja gar nicht so einfach zu verstehen, aber ich glaube jetzt hab ichs.
Ich habe mir dann auch mal überlegt, was das bedeuten würde, wenn ich zwei 64-Bit-Zahlen damit in 32 Bit zerlegen wurde, um das Produkt zu berechnen. Ich bin von 64 Bit unsigned ausgegangen, also ohne Vorzeichen. [edit]Die Einzelnen 32-bittigen "Ziffern" sind aber eh vorzeichenlos.[/edit]
Der Schritt
v=(q-p)(s-r)
sieht mir problematisch aus.
pq und rs sind ja die einzelnen "Stellen", also 32-Bit-Teile er 64-Bit-Zahlen. Sie sind unsigned Integers und können ALLE Werte von 0 bis 2^32-1 sein.
Da gibt es nun z. B. für q-p folgende Fälle:
q > p --> das Ergebnis ist positiv. Wenn p gar 0 ist und q = 2^32-1, ist es 2^32-1.
q = p --> 0
q < p --> das Ergebnis ist negativ. Im Extremfall ist q = 0 und p=2^32-1.
Das Ergebnis muss also Zahlen von +2^32-1 bis -2^32-1 speichern können und daher ist es mindestens 33 Bit groß, weil Vorzeichen wichtig ist. Das Vorzeichen wird ja auch extra im Text betont.
Das gleiche gilt auch für die andere Differenz.
Diese 33-Bit-Zahlen werden jetzt miteinander multipliziert. Das kann der Prozessor aber nicht, er kann nur 32-Bit-Zahlen multiplizieren. Also müsste man die Zahlen erweitern und z. B. einen Algorithmus verwenden, um Zahlen 64-Bittig miteinander zu multiplizieren. Genau das war aber der gesuchte Fall. (Das Ergebnis der 33-Bit-Multiplikation kann übrigens im schlimmsten Fall nur mit 66 Bits oder mehr dargestellt werden...)
Auch andere Gedanken, die ich mir dazu gemacht habe, wie man dieses "Problem" umgehen könnte (und da hatte ich schon einige Ideen) lassen es mir letztlich als kompliziert erscheinen. Da nehme ich doch lieber meine Schulmethode.
Ich habe mich mal in meinem Testprogrammcode durchgewühlt und dort mit Taschenrechner
die Anzahl der Multiplikationen gezählt, die dort mit meinem Algo oben durchgeführt werden. In den 3,5 Minuten schafft mein PC 322 Millionen Multiplikationen. Ich denke mal das reicht mir für meine Zwecke aus, denn die Fälle, in denen ich 128 Bits verwenden möchte, sind ja nicht Fälle wo ich viele Berechnungen nacheinander vornehmen möchte, sondern ich habe vor, große Zahlen zu verwenden.
Mfg
FAlter