www.mikrocontroller.net

Forum: PC-Programmierung Multi. größerer Zahlen


Autor: Hannes1984 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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;
}

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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;
> }

Autor: Hannes1984 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: Stinkywinky (Gast)
Datum:

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

Autor: Klaus Kehrer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.