www.mikrocontroller.net

Forum: Compiler & IDEs wie "erzwinge" ich eine 16bit*16bit = 32bit Multiplikation?


Autor: Jörg H. (idc-dragon)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich caste mir mit AVR gcc gerade den Wolf, aber es will nicht klappen:
Ich brauche eine Multiplikation von zwei uint16_t, das Ergebnis davon 
hat 32 bit Breite. Von diesem will ich ferner nur die obere Hälfte 
weiterverwenden, die untere ist sozusagen der Nachkommateil.

Etwa in der Art:
uint16_t a;
uint16_t b;
uint16_t c;
...
c = (a*b) >> 16;

Der Compiler sieht das so wohl als Multiplikation mit 16 Bit 
Ergebnisbreite an. Außerdem erkennt er, das anschließend die 16 gültigen 
Ergebnisbits rausgeschoben werden, und optimiert die Multiplikation weg. 
Hieraus entsteht also gar kein Code.

Wenn ich in einem hilflosen Versuch z.B. einen Operanden auf 32 bit 
caste,
c = ((uint32_t)a*b) >> 16;
dann wird gleich die Bibliotheksfunktion __mulsi3 instantiiert und 
aufgerufen, das ist volle Breitseite 32*32 bit.
Habe ich eine Chance, das hier effizienterer Code erzeugt wird?

Autor: Jörg H. (idc-dragon)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Auf 32Bit Prozessoren geht das mitunter, in etwas anderer Form. Man 
kommt mit 32 Bit Variablen (=Maschinenworten) an. Wenn man weiß das nur 
die untere Hälfte belegt ist und 16*16Bit ausreicht kann man die 
Operanden im Multiplikationsterm auf 16 Bit casten. Der Compiler fügt 
dann eine kleinere Multiplikation ein, aber liefert 32 bit Ergebnis:
uint32_t a;
uint32_t b;
uint32_t c;
...
c = (uint16_t)a * (uint16_t)b;
Daher meine Hoffnung, daß ich meinen Fall auf dem 8bitter dem Compiler 
das irgendwie verständlich casten kann.

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vielleicht so:
a=(a1*2^8+a2);
b=(b1*2^8+b2);
also
c=(a*b)/2^16=(a1*b1*2^6+(a1b2+b1a2)*2^8+a2b2)/2^16=
a1b1+(a1b2/2^8+b1a2/2^8)

c=(a>>8)*(b>>8)+((a>>8)*(b&255))>>8+((b>>8)*(a&255))>>8;

gute Nacht
Detlef

Autor: Jörg H. (idc-dragon)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nanu, der Thread ist etwas entstellt, wo sind denn die Postings von 
Andreas Kaiser (a-k) hin?

Zu der gcc-Optimierung: Sowas kann man nur bauen, wenn es einen Weg für 
den Compiler gibt das zu erkennen. Wie sagt man ihm also korrekt, das er 
16*16->32 multiplizieren soll? Mich wundert offengestanden schon, das es 
keine ensprechende Bibliotheksfunktion geben soll. Ich habe eine 
Auflistung derselben gesucht, aber nicht gefunden.

"Zu Fuß" multiplizieren wie von Detlef angeregt könnte schon eine Lösung 
sein. Muß mal nachgucken wie das ging, ist ja wie schriftlich 
multiplizieren, ist schon eine Weile her...

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jörg Hohensohn wrote:

> Nanu, der Thread ist etwas entstellt, wo sind denn die Postings von
> Andreas Kaiser (a-k) hin?

Kein Interesse, mich auf dem Niveau von JfK rumzuärgern.

Autor: Jörg H. (idc-dragon)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Andreas Kaiser wrote:

> Kein Interesse, mich auf dem Niveau von JfK rumzuärgern.

Ja, schade. Durch Löschen der "guten" Anteile sieht es aber auch nicht 
besser aus.

Ich hab kurz in Richtung Detlef weiterprobiert. Der Term stimmte so noch 
nicht ganz. Es sind 4 Teilmultiplikationen, 8*8->16. Die Ergebnisse 
davon muß man wegen möglicher Überläufer schon 32bittig addieren, darf 
erst zum Schluß die unteren 16 Bit wegschneiden.
uint16_t mul16x16h(uint16_t a, uint16_t b)
{
    uint32_t c;
    c = (a>>8)*(b>>8)<<16 + (a>>8)*(b&255)<<8 + (a&255)*(b>>8)<<8 + (a&255)*(b&255);
    return c >> 16;
}
Ich krieg es dem Compliler aber auch hier noch nicht beigebogen, sich 
auch so zu verhalten, casts der Multplikationsanteile auf uint32_t 
halfen nicht.

Ich hoffe immer noch auf eine "fertige" 16*16->32 Multiplikation aus der 
Library...

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>Die Ergebnisse davon muß man wegen möglicher Überläufer schon 32bittig 
>>addieren,

naja, wie immer kann man Genauigkeit gegen Aufwand handeln: 
(a&255)*(b&255) kann maximal 255^2 groß werden, das beeinflußt also 
höchstens Bit Nummer 16 deines 32 Bit Ergebnis, der gemischte Term kann 
maximal 2*255^2 werden, geht also maximal in Bit 16/17 ein. Wenn Dir 
also das LSB Deines geschobenen c egal ist kannst Du die Berechnung 
(a&255)*(b&255) weglassen, wenn Dir die beiden unteren Bit egal sind 
reicht es (a>>8)*(b>>8) zu berechnen.

Cheers
Detlef

Autor: Jörg H. (idc-dragon)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es gibt tatsächlich keine Bibliotheksfunktion, gerade habe ich die Doku 
gefunden (libgcc war das Zauberwort):
http://gcc.gnu.org/onlinedocs/gccint/Integer-libra...
Die liefern alle die gleiche Breite zurück, die reingesteckt wurde.

Detlef, du hast recht, das mit der Genauigkeit ist schon erstaunlich. 
16*16 Bit für meine Festkommaarithmetik liefert mir letztlich nur 2 Bit 
mehr Ergebnis als 8*8 Bit, hmm.

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.