Multi. größerer Zahlen

[Hannes1984 (Gast)]

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;
}

[Karl H. (kbuchegg)]

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;
> }

[Hannes1984 (Gast)]

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.

[Karl H. (kbuchegg)]

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)

[Stinkywinky (Gast)]

> x = a * d + c * b;
gibt 0x11BD6BA00 (Überlauf)

[Klaus Kehrer (Gast)]

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