AVR Assembler Ganzzahl durch Kommazahl

[Peter Stuckl (Gast)]

Hallo,

programmiere gerade einen Attiny2313 in Assembler.

Habe auch schon fast alles hinbekommen was ich mir vorgestellt habe.

Nur jetzt stehe ich aufm Schlauch.

Möchte eine Ganzzahl in 2 Registern durch eine fixe Kommazahl teilen.

Ganzzahlen: 1 bis 4000

Feste Kommazahl: 0,8789

Also z.B. 1800/0,8789=2048

Beim Ergebnis benötige ich keine Nachkommastellen.

Ich hoffe mir kann jemand einen Denkanstoß geben.

Vielen Dank schonmal

[Falk B. (falk)]

Das Zauberwort lautet Festkommaarithmetik.

MfG
Falk

[Andreas R. (rebirama)]

ich programmier selbst kein asm, aber in C würde ich mit
225 multiplizieren(ungefähr 0.8798*256) und anschließend durch 256 
Teilen (>>8)

[spess53 (Gast)]

Hi

Multiplikation mit 1/0,8789. Multiplikationsroutinen findest du bei 
AppNotes von Atmel.

MfG Spess

[Andreas R. (rebirama)]

oh, ich seh grade du hast nen tiny, der hat gar keinen mul befehl...

[Klaus W. (mfgkw)]

x/0.8789 ist übrigens gleichbedeutend mit x*1.137786

[Kluchscheißernder N. (kluchscheisser)]

Peter Stuckl schrieb:
> Hallo,
>
> programmiere gerade einen Attiny2313 in Assembler.
>
> Habe auch schon fast alles hinbekommen was ich mir vorgestellt habe.
>
> Nur jetzt stehe ich aufm Schlauch.
>
> Möchte eine Ganzzahl in 2 Registern durch eine fixe Kommazahl teilen.

Dividieren ist etwas aufwendig. Ich würde es vermeiden, indem ich mit 
dem Reziprokwert der fixen Zahl multipliziere.

>
> Ganzzahlen: 1 bis 4000
>
> Feste Kommazahl: 0,8789
>
> Also z.B. 1800/0,8789=2048

Da bietet sich an, mit 291 zu multiplizieren und das untere Byte 
wegzuwerfen, um durch 256 zu teilen.

Also 1800 mal 291 (ergibt drei Bytes)
Nur die beiden oberen Bytes beachten (ersetzt eine Division durch 256)

Denn: Der Reziprokwert von 0,8789 ist 1,1377858.
Dies wird mit 256 multipliziert (Bruch erweitert) und ergibt 291,27...
Der Fehler beträgt knapp 3/256, also gut 0,1%.
Die Erweiterung mit 256 wird dann durch Weglassen des unteren Bytes 
kompensiert. Wenn es sein muss, kann man zuvor noch 128 addieren um das 
Ergebnis zu runden.

Das wäre dann: 1800 x 291 (= 523800) / 256 = 2046

>
> Beim Ergebnis benötige ich keine Nachkommastellen.

Die wären bei Bedarf aber da.

>
> Ich hoffe mir kann jemand einen Denkanstoß geben.

Die Multiplikation mit 291 erreichst Du übrigens durch 9 mal Shiften 
(über 3 Bytes) und 3 Additionen (je 3 Bytes). ;-)

>
> Vielen Dank schonmal

[Flo (Gast)]

Such dir nen Bruch der möglichst nahe an deiner Zahl liegt.
Dann multiplizierst du ganzzahlig deine Zahl mit dem Zähler (auf 
Überlaufe achten -> Zahlenbereich), und dann dividerst du durch den 
Nenner.

Ideal wäre ein Bruch, der im Nenner eine 2er-Potenz hat, dann kann man 
das Dividieren durch Schieben ersetzen.

[Falk B. (falk)]

http://www.mikrocontroller.net/articles/Festkommaarithmetik#Division_durch_Konstanten

[Peter Stuckl (Gast)]

Viel dank für die schnellen und zahlreichen Antworten.

1800*289/254= 2048

Das kommt dem ganzen noch am nächsten denke ich.

Was mich aber stört sind die 3 Bytes (1800*289).

Aber das bekomme ich wohl hin.

[Falk B. (falk)]

@  Peter Stuckl (Gast)

>1800*289/254= 2048

Das hat aber KEINER erzählt.

Eher

1 / 0,8789 = 1,1377859 = 291 / 256

Macht einen Fehler von 0,93%, Hmmm.

>Das kommt dem ganzen noch am nächsten denke ich.

Ich würde auf 1165 / 1024 gehen, macht 0,08% Fehler für gerade mal zwei 
Bit mehr.

MFG
Falk

[Ralli (Gast)]

Da ich kleine kompakte Umrechnungen öfter brauche, habe ich mal
mein Verfahren als Code-Schnipsel angefügt.
Die Multiplikationsroutine kann man immer brauchen,
das Ergebnis ist nicht exakt, aber optimal genau.

; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

.def Tmp0  = R16
.def Tmp1  = R17     
.def Tmp2  = R18     
.def Tmp3  = R19     
.def Tmp4  = R20     
.def Tmp5  = R21     
.def Tmp6  = R22     
.def Tmp7  = R23     
.def Tmp8  = R24     
.def Tmp9  = R25 

; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 

; K = 1 / 0,8789
;
; Konstante muss < 1 sein, also:
;
; A / 0,8789 = A * 1,137786
: = A * 2 * 0,568893    
; = A * 2 * (0,568893 * 65536) / 65536
; = A * 2 * 37283 / 65536


  ldi Tmp0,  low(1800)
  ldi Tmp1, high(1800)  ; A

  lsl Tmp0
  rol Tmp1    ; A = 2 * A

  push Tmp2
  push Tmp3    ; Register sichern

  ldi Tmp2,  low(37283)
  ldi Tmp3, high(37283)
  rcall mult_01_23  ; A = A * 2 * 37283

  mov Tmp0, Tmp2
  mov Tmp1, Tmp3  ; A = A * 2 * 37283 / 65536 = A / 0,8789
  
  pop Tmp3
  pop Tmp2    ; Register wiederherstellen


; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 

mult_01_23:      ; IN: Tmp1-0 = A, Tmp3-2 = B
  push  Tmp4    ; OUT: Tmp3-2-1-0 = A x B
  push  Tmp5
  push  Tmp6
  push  Tmp7
  push  Tmp8
  push  Tmp9
  clr  Tmp4
  clr  Tmp5
  clr  Tmp6
  clr  Tmp7
  clr  Tmp8
  clr  Tmp9

mult0:
  lsr  Tmp1
  ror  Tmp0
  brcc  mult1
  add  Tmp6, Tmp2
  adc  Tmp7, Tmp3
  adc  Tmp8, Tmp4
  adc  Tmp9, Tmp5
mult1:
  lsl  Tmp2
  rol  Tmp3
  rol  Tmp4
  rol  Tmp5

  tst  Tmp0
  brne  mult0
  tst  Tmp1
  brne  mult0

  mov  Tmp3, Tmp9
  mov  Tmp2, Tmp8
  mov  Tmp1, Tmp7
  mov  Tmp0, Tmp6

  pop  Tmp9
  pop  Tmp8
  pop  Tmp7
  pop  Tmp6
  pop  Tmp5
  pop  Tmp4
  ret

; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

[Peter Stuckl (Gast)]

Guten Morgen

@Ralli

das läuft optimal mit dein Vorschlag!

Hätte nie gedacht, dass man das so hinbekommt!

[spess53 (Gast)]

Hi

>; K = 1 / 0,8789
>;
>; Konstante muss < 1 sein, also:
>;
>; A / 0,8789 = A * 1,137786
>: = A  2  0,568893
>; = A  2  (0,568893 * 65536) / 65536
>; = A  2  37283 / 65536

Die Berechnung kann der Assembler2 auch allein:

ldi r18,Low(Q15(FRAC(1/0.8789))+1)
ldi r19,High(Q15(FRAC(1/0.8789))+1)+$80

MfG Spess

[eProfi (Gast)]

0,8789r*65536=74565,93469109113  hex 1.2345  binär 1.0010001101000101

das genaue Ergebnis für 4000 ist
4000/0,8789=4551,1434747

d.h. Du kopierst die Zahl in ein Summierregister (alles 
16bit-Operationen)
shiftest die Zahl um 3 nach rechts und addierst ins Summierregister
shiftest die Zahl um weitere 4 nach rechts und addierst ins Register
shiftest die Zahl um weitere 1 nach rechts und addierst ins Register
shiftest die Zahl um weitere 2 nach rechts und addierst ins Register
shiftest die Zahl um weitere 4 nach rechts und addierst ins Register *)
fertig - Ergebnis steht im Summierregister

das sind 2*(1+4+5+2+3)=30 Befehle

*) diese Zeile bringt nur etwas, wenn wie unten beschrieben vorher nach 
links geschoben wurde
dann sind es 2*(1+4+5+2+3+5)=40 Befehle

Wenn's etwas schneller, dafür ungenauer sein darf
(/0,8767123287 entspricht *1,140625):
d.h. Du kopierst die Zahl in ein Summierregister (alles 
16bit-Operationen)
shiftest die Zahl um 3 nach rechts und addierst ins Summierregister
shiftest die Zahl um 3 nach rechts und addierst ins Summierregister
4000 wird so zu 4000+500+62=4562
so sind es 2*(1+4+4)=18 Befehle


Wenns genauer sein soll: Der Wert 4000 passt in 12 Bit, also zuerst um 
1-4 Bits nach links schieben, dann wie oben beschrieben rechnen und 
Ergebnis wieder um 1-4 Bits nach rechts schieben.

Das kann man noch optimieren:
Zahl ins Register kopieren
Zahl um 3 nach links schieben und ins Register addieren
Originalzahl um 4 nach rechts schieben und ins Register addieren
weiter wie oben
zum Schluss Ergebnis wieder um 3 nach rechts

Das Runden bringt auch mehr Genauigkeit:
Einfach das "Nachkommabit" auf das Ergebnis addieren.
also beim letzten Beispiel nur noch das Carry addieren (adc #0), da sich 
das Nachkommabit nach dem letzten shr  im Carry  befindet.

Falls noch Fragen, bitte fragen!
Mich würde interessieren, wie Du es gelöst hast.

[Kluchscheißernder N. (kluchscheisser)]

Kann es sein, dass Du "nach links shiften" meinst? Denn nach rechts ist 
ja Division durch 2, da bleibt am Ende nix übrig. ;-(

[eProfi (Gast)]

Nein, ich meine schon nach rechts schieben. Zum Schluss soll ja nichts 
mehr übrigbleiben.
Nochmal zur Verdeutlichung ein Beispiel:
1.   0    0    1   0   0   0  1  1  0 1 0 0 0 1 0 1
4000 2000 1000 500 250 125 62 31 15 7 3 1
4000+          500+           31+15+  3              =4549

Und das Beispiel mit erhöhter Genauigkeit durch "shl 3":
1.    0     0    1    0    0    0   1   1   0  1  0  0 0 1 0 1
32000 16000 8000 4000 2000 1000 500 250 125 62 31 15 7 3 1
32000+           4000+              250+125+   31+       1=36407
36407/8=4550,875   Runden ergibt 4551, da das Nachkommabit 1 ist.


Wieso hättest Du auf Linksschieben getippt?

[Kluchscheißernder N. (kluchscheisser)]

eProfi schrieb:
> Nein, ich meine schon nach rechts schieben. Zum Schluss soll ja nichts
> mehr übrigbleiben.
> Nochmal zur Verdeutlichung ein Beispiel:
> 1.   0    0    1   0   0   0  1  1  0 1 0 0 0 1 0 1
> 4000 2000 1000 500 250 125 62 31 15 7 3 1
> 4000+          500+           31+15+  3              =4549
>
> Und das Beispiel mit erhöhter Genauigkeit durch "shl 3":
> 1.    0     0    1    0    0    0   1   1   0  1  0  0 0 1 0 1
> 32000 16000 8000 4000 2000 1000 500 250 125 62 31 15 7 3 1
> 32000+           4000+              250+125+   31+       1=36407
> 36407/8=4550,875   Runden ergibt 4551, da das Nachkommabit 1 ist.
>
>
> Wieso hättest Du auf Linksschieben getippt?

Sorry, ich bin von meinem Vorschlag mit der Multiplikation mit 291 und 
Pseudo-Division durch 256 (unteres Byte wegwerfen) ausgegangen:
Beitrag "Re: AVR Assembler Ganzzahl durch Kommazahl"
Dies wäre mit Linksschieben und Addieren recht einfach zu erledigen. 291 
ist ja 0b100100011. Das sind 9 Bit mit insgesamt 4 Einsern, also 9 
Links-Shifts mit 3 Additionen (da wo die Einser stehen).

Aber was soll's, es sind genügend verschiedene Vorschläge gemacht 
worden, ich erwarte daher nicht, dass mein Vorschlag umgesetzt wird. ;-)