Hallo, ich bin gerade dabei, eine Multiplikation 32*32 Bit zu
Implementieren. habe auch eine sehr edle Variante gefunden nur leider
kommt nicht ganz das Ergebnis raus. Es basiert auf folgendem Prinzip
(a+2^16*b)*(c+2^16*d) = (a*c+(a*d + b*c)*2^16+b*d*2^32)
Also Man teilt die beiden Faktoren in jeweils Hi und Lo Part auf.
Nur wenn ich 9212D700 * CC20C500 übergebe
7478B617 5F730000--> kommt raus
7479B617 5F730000-->so solls sein
vielleicht hat ja jemand von euch eine Ahnung, woran das liegen kann.
static void long_multiply (unsigned long v1, unsigned long v2)
{
unsigned long a, b, c, d;
unsigned long x, y, HI,LO;
a = (v1 >> 16) & 0xffff;
b = v1 & 0xffff;
c = (v2 >> 16) & 0xffff;
d = v2 & 0xffff;
LO = b * d;
x = a * d + c * b;
y = ((LO >> 16) & 0xffff) + x;
LO = (LO & 0xffff) | ((y & 0xffff) << 16);
HI = (y >> 16) & 0xffff;
HI += a * c;
}
Hannes1984 wrote:
> Hallo, ich bin gerade dabei, eine Multiplikation 32*32 Bit zu> Implementieren. habe auch eine sehr edle Variante gefunden nur leider> kommt nicht ganz das Ergebnis raus. Es basiert auf folgendem Prinzip>> (a+2^16*b)*(c+2^16*d) = (a*c+(a*d + b*c)*2^16+b*d*2^32)>> Also Man teilt die beiden Faktoren in jeweils Hi und Lo Part auf.> Nur wenn ich 9212D700 * CC20C500 übergebe>> 7478B617 5F730000--> kommt raus> 7479B617 5F730000-->so solls sein>> vielleicht hat ja jemand von euch eine Ahnung, woran das liegen kann.>> static void long_multiply (unsigned long v1, unsigned long v2)> {> unsigned long a, b, c, d;> unsigned long x, y, HI,LO;>> a = (v1 >> 16) & 0xffff;> b = v1 & 0xffff;> c = (v2 >> 16) & 0xffff;> d = v2 & 0xffff;>> LO = b * d;> x = a * d + c * b;> y = ((LO >> 16) & 0xffff) + x;>
Überprüf mal ob dieses Zwischenergebnis größer
als 16 Bit wird. Ich denke das kann passieren
> LO = (LO & 0xffff) | ((y & 0xffff) << 16);> HI = (y >> 16) & 0xffff;
Wenn ja, dann verlierst du hier ein Bit übertrag.
HI = (y >>16);
>> HI += a * c;> }
Hi danke für die Antwort,
> LO = (LO & 0xffff) | ((y & 0xffff) << 16);> HI = (y >> 16) & 0xffff;
LOW = 5F730000
HI = 1BD7
Ich vermute der Fehler liegt hier, weil 2, 32 Bit zahlen addiert erzeugt
eigentlich wieder einen Überlauf, wenn ja, wie könnte man das Problem
beheben.
> x = a * d + c * b;> y = ((LO >> 16) & 0xffff) + x;
Ich wollte nämlich nicht auf die Schulmethode zurück greifen weil die
Viel zu langsam ist, wenn ich von "hand" die Bits verschiebe gegenüber
dem Verfahren hier, so kann der Compiler selber noch besser Optimieren.
Hannes1984 wrote:
> Hi danke für die Antwort,>>> LO = (LO & 0xffff) | ((y & 0xffff) << 16);>> HI = (y >> 16) & 0xffff;>> LOW = 5F730000> HI = 1BD7>> Ich vermute der Fehler liegt hier,
Nicht vermuten. Fakten schaffen.
Im Debugger durchgehen und alle Zwischenergebnisse
kontrollieren (und mit einem Taschenrechner nachrechnen)
Eine eigene Frage?
Dieser Thread ist über 19 Jahre alt.
Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.
