Einzelnen Beitrag anzeigen

Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#4

Re: Guter Algorithmus zum multiplizieren großer Zahlen gesuc

  Alt 15. Nov 2008, 09:52
Also ich würde sagen, du kannst die Zahlen einfach ausmultiplizieren

Soll heißen, wenn du die in 2 64bit Zahlen splittest (verschnkt übrigens ein bit, da du 2 Vorzeichenbits hast)

Und dann kannnst du rechnen: A*B = a1*b1*2^128 + a1*b2*2^64 + a2*b1*2^64 + a2*b2

Jetzt musst du nur noch eine Funktion schreiben, die 2 64bit Zahlen multipliziert und das Ergebnis als 128bit Zahl zurückgibt (die 2^64 kannste ja shiften...)

(Mit 32bit wirds natürlich entsprechend länger ...)

Btw.: Auf fast allen modernen CPUs gibt es doch bereits vorgefertigte 128bit Arithmetik, oder nicht?
  Mit Zitat antworten Zitat