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)
Hi all, ich schlage folgendes vor: struct sdLong{ unsigned long Hi_Long; unsigned long Low_Long; }; struct sdDInt{ unsigned short Hi_Long1; unsigned short Low_Long1; unsigned short Hi_Long2; unsigned short Low_Long2; }; union uDoubleLong{ struct sdLong dLong; struct sdDInt dDInt; }; struct sDInt{ unsigned short Hi_Int; unsigned short Low_Int; }; union uLong{ unsigned long Long; struct sDInt Int; }; void Dlong_Mult(unsigned long f1, unsigned long f2){ union uDoubleLong Result; union uLong zw_res1,zw_res2,zw_res3,zw_res4; union uLong res; unsigned long a,b,c,d; // Aufbau von result // Longs: Hi_Long || Low_Long // Int: Hi_Long1 | Low_Long1 || Hi_Long2 | Low_Long2 // Aufbau von uLong // Long // Hi_Int | Low_Int // f1 = a + 2^16*b // f2 = c + 2^16*d a = f1 & 0xffff; b = (f1 & 0xffff0000) >> 16; c = f2 & 0xffff; d = (f2 & 0xffff0000) >> 16; // result = f1 * f2 = ac + 2^16*(ad + bc) + 2^32*bd // damit ergeben sich 4 getrennt multiplikationen // und sich 3 getrennt additionen zw_res1.Long = a*c; // 1. Mult: a*c zw_res2.Long = a*d; // 2. Mult: a*d zw_res3.Long = b*c; // 3. Mult: a*c zw_res4.Long = b*d; // 4. Mult: a*d // // nun erfolgt die addition der ergebnisse Result.dDInt.Low_Long2 = zw_res1.Int.Low_Int; // ergebnis übernehmen res.Long = (long) zw_res1.Int.Hi_Int + // 1 Addition (long) zw_res2.Int.Low_Int + (long) zw_res3.Int.Low_Int; Result.dDInt.Hi_Long2 = res.Int.Low_Int; // ergebnis übernehmen Result.dDInt.Low_Long1 = res.Int.Hi_Int; res.Long = (long) zw_res2.Int.Hi_Int + // 2. Addition (long) zw_res3.Int.Hi_Int + (long) zw_res4.Int.Low_Int + (long) Result.dDInt.Low_Long1; // überlauf aus 1 Addition beachten Result.dLong.Hi_Long = res.Long; res.Long = (long) zw_res4.Int.Hi_Int + // 3. Addition (long) Result.dDInt.Hi_Long1; // überlauf aus 2 Addition beachten Result.dDInt.Hi_Long1 = res.Int.Hi_Int; // ergebnis übernehmen // 64 bit ergebnis ist in Result gespeichert } In dieser Form (oder ähnlich) muss es gehen. Die Zerlegung in 4 Multiplikationen und 3 Additionen ist wegen der Überlauf-Probleme notwendig. Bye Klaus
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.