Teilen durch 3 in Assembler

Wenns nicht so genau sein muss, versuch einfach 1/3 durch Summe aus
Brüchen mit Zweierpotenzen darzustellen, z.B.:

1/3 = 1/4 + 1/8 - 1/16 + 1/32 - 1/64 + ...

das wären 0.328 wenn ich mich nicht verrechnet hab, also schon recht
nahe an den 0.333. Die Brüche machst Du in Assembler durch Rechtsshift.

Du kannst binär dividieren genau gleich wie du's in der Grundschule
gelernt hast:

z.B.: 90 / 3
01011010 : 11 =
01 <= 11 ==> ergebnis = 0
 10 <= 11 ==> ergebnis = 00
 101 >= 11 ==> ergebnis = 001
  101 >= 11 ==> ergebnis = 0011
   100 >= 11 ==> ergebnis = 00111
    011 >= 11 ==> ergebnis = 001111
      00 <= 11 ==> ergebnis = 0011110
       0 Rest
Also ergebnis = 11110 = 0x1E oder 30

Ob's dafür nen schönen Algo. gibt weiß nicht...

@all,
vielen Dank für die zahlreichen Ideen.

@Thorsten, @Sebastian
Diese Lösungen funktionieren auch mit anderen Zahlen als 3 und
beschreiben das konventionelle dividieren. Ich habe es im Moment so
implementiert.

@Rupert
Das ist ein mir bislang unbekannter Ansatz. Ich werde mal ausrechnen
wie groß der Aufwand und die Genauigkeit für's Teilen durch 3 ist.

@Tobias
Danke für die Beispielrechnung. Aber ohne Divisionsbefehl funktioniert
das glaube ich nicht. Oder ich müßte wieder ganz normal
Subtrahieren/Addieren wie beim Beispiel von Thorsten und Sebastian.

Nochmals Danke für eure Ideen

Jürgen

Wie wärs hiermit:
http://www.atmel.com/dyn/resources/prod_documents/AVR200.zip

In vielen Fällen läuft das etwas fixer ab und geht voll nach dem
Verfahren von Tobias.

MfG
Andi

Multiplizieren mit 1/3 bzw. 85/256 bzw. mit 85 Multiplizieren und dann
von dem 16 bit Ergebnis nur das obere Byte nehmen.
Mfg
Michael

Hallo zusammen,

@Tobias
Da war ich wohl zu vorschnell mit der Behauptung, daß dein Vorschlag
eine Division benötigt. Ich hab's gemerkt, als ich es mit den
Atmel-Algorithmen von Andi verglichen habe. Ist mir echt peinlich, ich
hoffe du nimmst es mir nicht übel.

@Andi
Vielen Dank für den Hinweis auf die Atmel Website. Die Datei hatte ich
irgendwie übersehen.

@Michael
Das ist auch ein interessanter Ansatz wenn nur ein
Multiplikationsbefehl und kein Divisionsbefehl zur Verfügung steht.

Also vielen Dank nochmal für eure Hinweise.

Jürgen

kein Problem. Den Ansatz mit 1/3 multiplizieren habe ich mir gerade
überlegt und dabei gibts nur ein Problem: 1/3 lässt sich wie im
dezimalen im binären nicht eindeutig (also periodisch) anschreiben.
1/3 binär wäre 0,01010101... usw. Also wieder nur mit begrenzter
Genauigkeit darstellbar.

Wenn wir jetzt wieder 90 mit 1/3 multilpizieren sieht das so aus:

01011010 * 0,01010101
Jetzt Komma verschieben (Grundschule...), 8 stellen
001011010 * 1010101
--------------------
001011010
  001011010
    001011010
      001011010
--------------------- addieren
001110111100010
Komma wieder hinzu
0011101,11100010 ==> 29,xxx also fast 30.

>> Wenn wir jetzt wieder 90 mit 1/3 multilpizieren....

Dann "runde" 90 vorher indem du 90 + (3 -1) drauf addierst.
Wenn du zb. 89 / 3 rechnen willst, mit einer Ganzzahldivision, dann
solltest du auch (89 + 2) / 3 rechnen um ein korrektes Resultat zu
erhalten.

Gruß Hagen

Oder einfach nichtr mit 85 sondern mit 86 multiplizieren um nicht
29,irgendwas, sondern 30,irgendwas zu nekommen.

90 * 85 / 256 = 29,88   falsch
90 * 86 / 256 = 30,23   richtig
255 * 85 / 256 = 84,67  falsch
255 * 86 / 256 = 85,66  richtig
3 * 85 / 256 = 0,996    falsch
3 * 86 / 256 = 1,01     richtig

Wie man sieht, kommt man mit 86 an der Ganzzahl vor dem Komma genau
hin.
Für Zahlen mit 8 Bit ist das in Ordnung.
Erst bei Zahlen mit 16 Bit wird es irgend wann um 1 zuviel und mit 85
um 1 zu wenig.
Dann lieber doch gleich eine richtige Div-Routine verwenden sofern man
mit 16 Bit-Zahlen rechnen will.

MfG
Andi

bei 8 Bit mache ich es so:

.include  "8515DEF.INC" ;oder was auch immer

.CSEG
.ORG  0

Reset:
    ldi    yl,low(RAMEND)
    out    SPL,yl
    ldi    yh,high(RAMEND)
    out    SPL+1,yh
;******

;a=25
    ldi    r24,25
;b=3
    ldi    zl,3
;c=a/b
    rcall  Div8u
;ergebnis ist in zl

;****** 8/8 unsigned division ******
Div8u:  mov    r25,zl
    mov    zl,r24
    sub    r22,r22
    ldi    r23,0x09
d8u1:  rol    zl
    dec    r23
    brne  d8u2
    ret
d8u2:  rol    r22
    sub    r22,r25
    brcc  d8u3
    add    r22,r25
    clc
    rjmp  d8u1
d8u3:  sec
    rjmp  d8u1

Vergesst den letzten Beitrag von mir!
So oder so hat man z. B. bei 251 als Ergebnis 84 wie bei 252.
Auch, wenn man mit 85 multipliziert und vorher den Eingangswert um 2
erhöht.
Es bringt wirklich nur eine Div-Funktion was in der Form einer Schleife
und immer 3 subtrahieren bis Unterlauf oder die "echte" Div-Funtion
aus der App-Note die man, wenn es nur /3 sein soll darauf optimieren
könnte.

MfG
Andi

@jornbyte: Das ist ja das aus dem AVR200.asm (App-Note).
Man kann es aber noch etwas optimieren um 8 Takte zu sparen.
Sind zwar "nur" 8% von den angegeben 97 aber immerhin.

Hier das umgestellte aus der App-Note:

div8u:  sub     drem8u,drem8u ;clear remainder and carry
        ldi     dcnt8u,9      ;init loop counter
d8u_1:  rol     dd8u          ;shift left dividend
        dec     dcnt8u        ;decrement counter
        breq    d8u_2         ;if done
        rol     drem8u        ;shift dividend into remainder
        sub     drem8u,dv8u   ;remainder = remainder - divisor
        brcc    d8u_3         ;if result negative
        add     drem8u,dv8u   ;restore remainder
        clc                   ;clear carry to be shifted into result
        rjmp    d8u_1         ;else
d8u_3:  sec                   ;set carry to be shifted into result
        rjmp    d8u_1
d8u_2:  ret                   ;return

Es ist lediglich das "RET" nach unten gestellt und das breq statt
brne benötigt nicht 2 sondern nur 1 Takt * 8 = 8 Takte gespart.

MfG
Andi