Komplizierte 32-Bit-Rechnung möglichst effizient

Hallo,

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

> 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.

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.

Thorsten schrieb:
> Ich möchte folgendes berechnen:

1

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

Du meinst wohl das?

1

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

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

1

;Temp Block A

2

.def  _TMP0    = R8

3

.def  _TMP1    = R9

4

.def  _TMP2    = R10

5

.def  _TMP3    = R11

6

7

;High Block A

8

.def  _HA0    = R16

9

.def  _HA1    = R17

10

.def  _HA2    = R18

11

.def  _HA3    = R19

12

13

;High Block B

14

.def  _HB0    = R20

15

.def  _HB1    = R21

16

.def  _HB2    = R22

17

.def  _HB3    = R23

18

19

MathMul32x32_32U:

20

clr  R2

21

mul  _HA0,_HB0

22

movw  _TMP0,R0

23

mul  _HA0,_HB2

24

movw  _TMP2,R0

25

mul  _HA0,_HB1

26

add  _TMP1,R0

27

adc  _TMP2,R1

28

adc  _TMP3,R2

29

mul  _HA1,_HB0

30

add  _TMP1,R0

31

adc  _TMP2,R1

32

adc  _TMP3,R2

33

mul  _HA1,_HB1

34

add  _TMP2,R0

35

adc  _TMP3,R1

36

mul  _HA2,_HB0

37

add  _TMP2,R0

38

adc  _TMP3,R1

39

mul  _HA0,_HB3

40

add  _TMP3,R0

41

mul  _HA1,_HB2

42

add  _TMP3,R0

43

mul  _HA2,_HB1

44

add  _TMP3,R0

45

mul  _HA3,_HB0

46

add  _TMP3,R0

47

movw  _HA0,_TMP0

48

movw  _HA2,_TMP2

49

ret

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

Können sich alle 3 Variablen jederzeit Ändern?

viel Erfolg
hauspapa

@ 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

@ Thorsten (Gast)

1

int16_t x;

2

uint16_t p;

3

uint8_t a;

4

5

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!

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...?

Ohne Überlauf geht das:

1

#include <stdint.h>

2

#include <stdfix.h>

3

4

uint16_t fun_f (int16_t x, uint16_t p, uint8_t a)

5

{

6

    unsigned fract fx = urbits (x);

7

    unsigned fract fp = urbits (p);

8

    uint16_t xp = bitsur (fx * fp); // (x * p) >> 16

9

10

    uint16_t pax8 = a == 0

11

        ? xp

12

        : ((__uint24) xp * (uint8_t) -a) >> 8;

13

14

    return x - pax8;

15

}

avr-gcc 4.9 mit -O2 macht daraus:

1

fun_f:

2

  movw r30,r24

3

  movw r18,r24

4

  movw r26,r22

5

  call __muluhq3

6

  movw r18,r24

7

  neg r20

8

  tst r20

9

  breq .L2

10

  mul r20,r18

11

  movw r24,r0

12

  mul r20,r19

13

  clr r26

14

  add r25,r0

15

  adc r26,r1

16

  clr __zero_reg__

17

  mov r18,r25

18

  mov r19,r26

19

  clr r20

20

.L2:

21

  movw r24,r30

22

  sub r24,r18

23

  sbc r25,r19

24

  ret

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