Einzelnen Beitrag anzeigen

Benutzerbild von jfheins
jfheins

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

Re: Guter Algorithmus zum multiplizieren großer Zahlen gesuc

  Alt 15. Nov 2008, 18:02
Ich kenne mich jetzt nicht mit Assembler aus, aber ... du addierst doch nicht etwa, oder?

Außerdem kann ich mir nicht vorstellen, dass das effizient ist - das sieht mir einfach zu lang aus

Um nochmal auf meinen Vorschlag zurückzukommen:

128bit - A*B = a1*b2*2^64 + a2*b1*2^64 + a2*b2

Kannst du weiter runterbrechen - d.h. eine Multiplikation von 2 64bit Werten sieht dann so aus:

x*y = x1*y1*2^64 + x1*y2*2^32 + x2*y1*2^32 + x2*y2

Wobei x1 das high-order dword ist und x2 das low-order dword. [s]Außerdem kannst du wieder den ersten Term vernachlässigen (würde wieder zu einem Überlauf führen)[s] Vergiss das ^^

Du musst dann eben Funktionen für 64bit und 32bit Multiplikation sowie zur Multiplikation mit 2er Potenzen zur Verfügung stellen

Du könntest daraus auch etwas rekursives machen nach dem Motto "Teile und Herrsche"
  Mit Zitat antworten Zitat