64 bit Multiplication emulieren

Ich möchte eine funktion mit 32 bit schreiben die 64bit * 64bit = 64bit (unsigned) multipkliziert, ohne dass 64bit-variablen nötig sind. Der Übertrag zum schluss kann entfallen .......

void mult64 (uint32_t ah, uint32_t al, uint32_t bh, uint32_t bl)
{
... ??
}

beide werte stehen als high und low word zur verfügung.
vom algorithmus her müsste es so laufen:

(ergebnis_h, ergebnis_l) = ah*bh + ah*bl + al*bh + al*bl

aaaaber!!! bei diesen multiplikationen und additionen dürfen keine überläufe entstehen. erst der überlauf im gesamtergebnis darf abgeschnitten werden.

und wie gesagt ein uint64_t habe ich nicht.

habt ihr eine Idee?
Danke!!!!!

volkard

neuer c-coder schrieb:

vom algorithmus her müsste es so laufen:

(ergebnis_h, ergebnis_l) = ah*bh + ah*bl + al*bh + al*bl

Nö. Du meinst sicherlich

(ergebnis_h, ergebnis_l) = ah*bh<<64 + ah*bl<<32 + al*bh<<32 + al*bl
//oh, ah*bh<<64 fällt weg.

aaaaber!!! bei diesen multiplikationen und additionen dürfen keine überläufe entstehen. erst der überlauf im gesamtergebnis darf abgeschnitten werden.

Du brauchst einen Typen, der ohne Fehler * kann.
Also uint16_t*uint16_1=uint32_t!
Dann kannste fein ziffernweise vorgehen.

Oder Du klaust Dir ein fast_pow und machst ein slow_mul draus, indem Du den Startwert zu 0 statt 1 machst und * durch + ersetzt.

Sehr cool ist auch, inline-assembler, dein Prozessor kann nämlich vermutlich uint32_t*uint32_t=uint64_t.

SeppJ

Einfachste Erkenntnis:
2^16 * 2^16 = 2^32
Damit hast du vier 16 Bit Stellen deren Produkt nie größer als 32 Bit wird und kannst somit rechnen wie in der Grundschule.

Für fortgeschrittene (oder auch weniger fortschrittliche, dafür einfacher zu implementierende) Ideen:
http://en.wikipedia.org/wiki/Multiplication_algorithm
Besonders interessant dürften dabei die Peasant multiplication und shift and add sein.
Oder auch
http://www.google.com/search?hl=en&q=multiply+64+bit+using+32+bit&oq=multiply+64+bit

edit: volkard war mal wieder schneller. Wusste ich doch schon beim Titel, dass er das Thema auch spannend finden würde

volkard schrieb:

Sehr cool ist auch, inline-assembler, dein Prozessor kann nämlich vermutlich uint32_t*uint32_t=uint64_t.

Und er kann das sicher auch für vorzeichenbehaftete Integer und es besteht wohl kaum Gefahr, dass die Implementierung einen Fehler hat. Dies ist nämlich durchaus möglich, wenn man alles selber schreibt (insbesondere mit Vorzeichen).