Komplizierte 32-Bit-Rechnung möglichst effizient

[Thorsten (Gast)]

Hallo,

gegeben sind folgende Variablen:

int16_t x;
uint16_t p;
uint8_t a;

Ich möchte folgendes berechnen:

x -= x * (256 - a) * p >> 24;

Aufgrund der Breite der Variablen kann man das so natürlich nicht machen 
(Überläufe). Daher dachte ich mir folgendes, um möglichst wenig 
Genauigkeit zu verschenken:

int32_t y = 256;
y -= a;
y *= p;
y >>= 8;
y *= x;
y >>= 16;
x -= y;

Die Frage ist nun: Geht das schneller/kleiner/besser?? Das Ganze 
passiert 1200 mal je Sekunde (neben allerlei anderer Geschichten).

[Uwe S. (de0508)]

Hallo,

welchen µC verwendest Du, dann kann man auch schauen, ob er Mul und Div 
in Hardware macht ?

[Thorsten (Gast)]

Das Wichtigste vergessen ^^

Ist ein ATMega, also mul kann er. Ich will Assembler nur im Notfall. 
Also, mein Ziel ist erstmal, den C-Code zu optimieren.

[Helmut S. (helmuts)]

> also mul kann er.

Aber nur 8bit*8bit. Also praktisch doch nicht.

Ideal wäre ein Prozessor der eine 32bit*32bit Multiplikation kann.
Dann geht das in einer Zeile so wie du es zuerst geschrieben hast.

[Thorsten (Gast)]

Naja, sagen wir mal so: Die Hardware ist das, was ich am wenigsten 
ändern kann. Die ist fix.

[Helmut S. (helmuts)]

Wenn das jetzt 2000 Takte dauert und der AVR mit 16MHz läuft, dann hast 
du doch immer noch über 80% der Rechenleistung für andere Aufgaben.

[Johann L. (gjlayde)]

Thorsten schrieb:
> Ich möchte folgendes berechnen:

> x -= x * (256 - a) * p >> 24;

Du meinst wohl das?

x -= (x * (256 - a) * p) >> 24;

[Uwe S. (de0508)]

Hallo,

hier ist noch eine 32Bit = 32Bitx32Bit Multiplikation mit 39 Takte + 4 
(Ret).

Erg = A * B

Mit
# Erg := _HA3:0
# Temp:= _TMP3:0
# A := _HA3:0
# B := _HB3:0

;Temp Block A
.def  _TMP0    = R8
.def  _TMP1    = R9
.def  _TMP2    = R10
.def  _TMP3    = R11

;High Block A
.def  _HA0    = R16
.def  _HA1    = R17
.def  _HA2    = R18
.def  _HA3    = R19

;High Block B
.def  _HB0    = R20
.def  _HB1    = R21
.def  _HB2    = R22
.def  _HB3    = R23

MathMul32x32_32U:
clr  R2
mul  _HA0,_HB0
movw  _TMP0,R0
mul  _HA0,_HB2
movw  _TMP2,R0
mul  _HA0,_HB1
add  _TMP1,R0
adc  _TMP2,R1
adc  _TMP3,R2
mul  _HA1,_HB0
add  _TMP1,R0
adc  _TMP2,R1
adc  _TMP3,R2
mul  _HA1,_HB1
add  _TMP2,R0
adc  _TMP3,R1
mul  _HA2,_HB0
add  _TMP2,R0
adc  _TMP3,R1
mul  _HA0,_HB3
add  _TMP3,R0
mul  _HA1,_HB2
add  _TMP3,R0
mul  _HA2,_HB1
add  _TMP3,R0
mul  _HA3,_HB0
add  _TMP3,R0
movw  _HA0,_TMP0
movw  _HA2,_TMP2
ret

[Thorsten (Gast)]

Das war so geschrieben, um das Prinzip zu verdeutlichen. "Pseudocode".

[Thorsten (Gast)]

Hmm, aber die einzelne 32-Bit-Multiplikation sollte der GCC doch drauf 
haben. Ich gehe nicht davon aus, dass diese in einer ineffizienten Art 
und Weise implementiert ist. Ich meine, das ist doch eine Grundfunktion, 
die überall benutzt wird.

[(prx) A. K. (prx)]

Hast du bei der Rechnung ein konkretes Performance-Problem, oder 
befürchtest du nur, dass du eines kriegen könntest?

[Thorsten (Gast)]

Nein, meine Intuition sagt mir, dass der Code zu umständlich ist und ich 
eine Vereinfachung übersehen habe.

[S. K. (hauspapa)]

Können sich alle 3 Variablen jederzeit Ändern?

viel Erfolg
hauspapa

[Falk B. (falk)]

@ Thorsten (Gast)

>Nein, meine Intuition sagt mir, dass der Code zu umständlich ist und ich
>eine Vereinfachung übersehen habe.

https://www.mikrocontroller.net/articles/AVR-GCC-Codeoptimierung#Prinzipien_der_Optimierung

[Falk B. (falk)]

@ Thorsten (Gast)

int16_t x;
uint16_t p;
uint8_t a;

x -= x * (256 - a) * p >> 24;

256-a ist 8 bit breit, * x sind 24 Bit, mal p sind eigentlich schon 40 
Bit! Aber hier willst du sicher KEINE 64 Bit Multiplikation.
Also muss man p schon vorher um mind. 8 Bit nach recht schieben oder 
gleich nur mit 8 Bit definieren, wenn es keine zusätzliche Einschränkung 
der Zahlenbereiche der Variablen gibt.

Aber der GCC muss fast alles als 32 Bit rechnen, wo eine handoptimiere 
ASM-Variante deutlich sparen kann. Aber dennoch gilt mein Link oben zum 
Thema Optimierung! Wenn es auch so ausreichend schnell ist, so what!

[Johann L. (gjlayde)]

Thorsten schrieb:
> Das war so geschrieben, um das Prinzip zu verdeutlichen. "Pseudocode".

Gibt dann auch nur "Pseudoantworten".

Das ist bestimmt ne verkappte Fixedpoint-Berechnung, und über die 
Wertebereiche der (Zwischenergebnisse ist vermutlich mehr bekannt als 
dass diese in 40 Bits reinpassen.

hmmm Welche Würmer kann man sich sonst noch aus der Nase ziehen 
lassen...?

[Thorsten (Gast)]

Falk Brunner schrieb:
> 256-a ist 8 bit breit, * x sind 24 Bit, mal p sind eigentlich schon 40
> Bit! Aber hier willst du sicher KEINE 64 Bit Multiplikation.

Bitte lesen!! Pseudocode, um zu verdeutlichen, was eigentlich gemacht 
werden soll. Natürlich bin ich mir der Überläufe bewusst, das steht aber 
eigentlich alles schon im ersten Posting.

Von Fixpoint und auch Floating Point ist hier nie die Rede gewesen. Es 
sind alles ganze Zahlen.

[Johann L. (gjlayde)]

Ohne Überlauf geht das:

#include <stdint.h>
#include <stdfix.h>

uint16_t fun_f (int16_t x, uint16_t p, uint8_t a)
{
    unsigned fract fx = urbits (x);
    unsigned fract fp = urbits (p);
    uint16_t xp = bitsur (fx * fp); // (x * p) >> 16

    uint16_t pax8 = a == 0
        ? xp
        : ((__uint24) xp * (uint8_t) -a) >> 8;

    return x - pax8;
}

avr-gcc 4.9 mit -O2 macht daraus:

fun_f:
  movw r30,r24
  movw r18,r24
  movw r26,r22
  call __muluhq3
  movw r18,r24
  neg r20
  tst r20
  breq .L2
  mul r20,r18
  movw r24,r0
  mul r20,r19
  clr r26
  add r25,r0
  adc r26,r1
  clr __zero_reg__
  mov r18,r25
  mov r19,r26
  clr r20
.L2:
  movw r24,r30
  sub r24,r18
  sbc r25,r19
  ret

__muluhq3 ist eine 16x16=16 Multiplikation ohne Überlauf und mit Rundung 
zum nächsten (max. Fehler = 1/2 LSB).

[Thorsten (Gast)]

Danke, das sieht ganz gut aus. Dieser Trick mit der Fixpoint-Geschichte 
bringt minimal Codevorteile. Der Trick mit der Fallunterscheidung macht 
viel aus.

Es funktioniert, weil auch x nicht negativ wird (trotz signed). Ob es 
letztendlich auch korrekt laufen würde, wenn das der Fall wäre, weiß ich 
jetzt aber nicht (fun_f liefert ja schließlich auch unsigned zurück).