effiziente Division durch 10

[Tom M. (tomm)]

Hallo zusammen


Ich brüte gerade über effizienten Algorithmen für die Division durch 10. 
Für Divisoren des Typs uint8_t funzt dieser Ansatz:

q = ((dividend + 1) * 51) >> 9

Dabei muss die Multiplikation zu einem uint16_t aufgewertet werden. Da 
passt alles, es können keine Überläufe statt finden.

Dieser Ansatz ist eine Näherung : 51/512 ist eben nicht genau 1/10. Für 
welchen Wertebereich wird dieser Algo funzen? Wie ermittle ich das 
rechnerisch? Ich scheitere an der Binär-Dezimal Problematik... (Durch 
Ausprobieren sehe ich, dass es das erste Mal beim Dividenden 260 
hapert.)

Wenn ich mir weitere Zweierpotenzen und Multiplikatoren anschaue, orte 
ich eine Verbesserung bei 2^12=4096: Multiplikation mit 409 (oder besser 
410?), dann 12 Bits schieben (>>12). Für welchen Wertebereich der 
Dividenden wird dieser Ansatz zuverlässig sein, angenommen ich stelle 
ausreichend breite Register/Variablen zu Verfügung? Ich kann das in 
Nullkommanix ausproggen und sehe's dann, mich interessiert aber der 
händische Ansatz.


Wer hat Lösungsansätze? Danke. :)

[hans (Gast)]

ich denke so wäre es recht einfach:

q = dividend / 10;

gruß
hans

[Tom M. (tomm)]

Will ich aber ned - meine ALU kennt keine Division. Den oben genannten 
Algo hab ich als Funktion in ASM implementiert und frage mich gerade, 
was die Grenzen der Bitschieberei sind... %)

[Detlev T. (detlevt)]

Kommt ja auch darauf an, was du als "effizient" bezeichnest. Für uint8_t 
könnte man ja z.B. auch an eine Tabelle denken.

[MaWin (Gast)]

> mich interessiert aber der händische Ansatz.

Da das Schieben die Nachkommastellen abschneidet,
interessiert dich die Stelle, an der die Nachkommastellen
>0.99999999999999 werden (falls der Multiplikator kleiner
war als der notwendige Wert) oder (falls der Multiplikator
grösser war und du 1 addiert hast) wo diese 1 aufgebraucht
ist.

Also Kehrwert von Fehler pro Ganzzahl.

[doofi (Gast)]

Stichwort: Multiplikation mit dem ternären Kehrwert.
Suchen darfst selber.

[Rufus Τ. F. (rufus)]

Dem Threadstarter geht es um Ganzzahldivision. Da ist ein ternärer 
Kehrwert nicht wirklich hilfeich.

[Oktoberfestbesucher (Gast)]

Hallo Threadstarter,
falls du die Division durch 10 brauchst um eine Binärzahl in eine 
Dezimalzahl zu wandeln, dann schau dir mal diesen Thread an:
Beitrag "C programmieren wie die grossen Jungs"

mfG.

[doofi (Gast)]

Rufus t. Firefly schrieb:
> Dem Threadstarter geht es um Ganzzahldivision. Da ist ein ternärer
> Kehrwert nicht wirklich hilfeich.

Ein wenig kurz gedacht.

Eine Multiplikation mit 0.1 sollte doch einer Division durch 10
äquivalent sein?

Um die Zahl der Rechenschritte zu minimierten, die ternäre Darstellung.

Ist aber wohl zu kompliziert für Dich :-)

[Yalu X. (yalu) (Moderator)]

Was ist denn der ternäre Kehrwert? Google liefert bei "ternärer
Kehrwert" genau einen Treffer, nämlich diesen Thread hier. Gibt man
"ternary reciprocal" ein, landet man auf irgendwelchen Chemiker-Seiten.

[Detlev T. (detlevt)]

Folgende Idee für 8 Bit:

Mathematisch gilt doch sicher

$$\frac{x}{10} = x * \frac{26}{256} - x * \frac{4}{2560}$$

Multipliziert man einen 8-Bit Wert mit 26 erhält man den ersten Term im 
MSB, einen Rest im LSB. Das Ergebnis im MSB ist also der korrekte Wert, 
solange Rest mal 10 größer ist als x mal 4. Das kann man testen, indem 
man den Rest mit 10 multipliziert, durch 4 teilt (shift) und mit x 
vergleicht. Nur wenn der Wert kleiner als x ist, muss man das Ergebnis 
noch um 1 dekrementieren.

Ist der Rest mindestens 103, kann man sich den zweiten Schritt sogar 
sparen, da hier ein Wert > 256 herauskommt, der immer größer ist als ein 
8-Bit-Wert.

Ob meine Thesen stimmen, musst du aber noch einmal überprüfen. :D

[quaaaaaaz (Gast)]

jo - aber /2560 ist ja auch nicht einfacher also /10

[Mark B. (markbrandis)]

Yalu X. schrieb:
> Was ist denn der ternäre Kehrwert?

Das würde mich jetzt auch mal interessieren.

[schlaubi (Gast)]

Bestimmt ist das gemeint:

Efficient Multiplication and Division Using MSP430

http://focus.ti.com/lit/an/slaa329/slaa329.pdf

[Detlev T. (detlevt)]

quaaaaaaz schrieb:
> jo - aber /2560 ist ja auch nicht einfacher also /10
Das muss man aber auch nicht berechnen. Trotzdem ist meine Idee zu 
kompliziert, wie ich inzwischen eingesehen habe. Die Näherungslösung:

> q = ((dividend + 1) * 51) >> 9

ist für 8-Bit ja brauchbar auf Systemen mit Hardware-Multiplikation 
(z.B. ATMEGA). Das braucht nur einen Inc, LDI von 51, Multiplikation und 
einen Rechtsshift des MSB.

Für 16-Bit und größer würde ich wohl eher eine spezielle 
Divisionsroutine schreiben, da der Divisor ja nur 1-Byte groß ist. 
Außerdem kenne ich ja schon den Wert (0x0a). Das heißt, die ersten 4 
Bits kann ich sofort durchshiften - ohne Vergleich.

[Martin (Gast)]

Was heißt schon Effizienz?

Für 8-Bit / 10 bietet sich ein Array mit 256 Elementen an. Da der 
Divisor durch 2 teilbar ist, kommt man auch mit 128 Elementen aus.

Bei einem 16-Bit Dividenden sieht es leider etwas ungünstig aus ;)

[Christoph db1uq K. (christoph_kessler)]

Hier wird auch mit 51 multipliziert (unter anderem):
http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&t=37150
"Dirty Math Tricks: Adventures in Division by Ten"

ähnliches Thema:
http://www.mikrocontroller.net/articles/AVR_Arithmetik#Bin.C3.A4r_zu_BCD_-_Umwandlung

[Yalu X. (yalu) (Moderator)]

schlaubi schrieb:
> Bestimmt ist das gemeint:
>
> Efficient Multiplication and Division Using MSP430

Danke für den Link. Ja, das wird doofi wohl gemeint haben. Wobei diese
Optimierungsmöglichkeit für Multiplikationen gerade im vorliegenden Fall
nichts bringt, weil die Multiplikatoren der Form 2ⁿ/10 in Binärdarstel-
lung die Form 110011001100... haben, und damit nirgends mehr als 2
aufeinanderfolgende 1-Bits aufweisen. Die Anzahl der benötigten
Additionen und Subtraktionen ist bei der CSD-Methode also genau die
gleiche, wie wenn man die Multiplikation klassisch ausführt (jeweils
ohne HW-Multiplizierer).

[Hagen R. (hagen)]

Dieses ominöse CSD Format kenne ich als 
http://en.wikipedia.org/wiki/Signed-digit_representation
http://en.wikipedia.org/wiki/Non-adjacent_form

"Signed Digit Repesentation in Non Adjacent Form"

Man muß da auch nicht nur mit {0,+1,-1} Signed Digits rechnen, also 2 
Bit Window Size sondern kann zb. auch mit dem Set {0, +-1, +-3, +-5, 
+-7} usw. arbeiten, je nach Windowsize. Die ternäre Form ist nur ein 
Spezialfall bei dem man mit 2 Bit Windowsize einen Binary in NAF 
umwandelt.

Gruß Hagen

[Marc P. (marcvonwindscooting)]

Hallo Leute, da mich das Problem seit 2 Wochen besch"aftigt grabe ich 
den alten Thread nochmals aus.

Prinzipiell kann man bei n-Bit-Zahlen immer eine Konstante finden, so 
dass man bei gegebenem d mit einer n x n -> 2n -Bit Multiplikation 
sozusagen durch d teilen kann - und zwar exakt - vorausgesetzt man ist 
bereit noch 'ne handvoll Stellen rechts zu shiften. Beispiel: 
32-Bit-Unsigned, division durch 10 (DIV = "C" integer division '/', 
unsigned)

M = (2^32 + 9) DIV 10

n / 10 = M*n >> 35

D.h. man muss die oberen 32 bits noch 3 rechtsshiften und fertig!
Und zu allem "Uberfluss ist diese Optimierung mindestens im gcc-4.8.1 
drin, wenn man f"ur einen ARM7 (UMULL, SMULL!) compiliert (-O2).

Allgemein ist die Formel:

$$M = \left\lceil \frac{U}{d} \right\rceil = \mbox{(U+d-1) DIV d}$$

mit:

$$\mbox{n DIV d}\quad := \quad \left\lfloor\frac{n}{d}\right\rfloor$$

Und gilt f"ur:

$$n < \frac{U}{\varepsilon} \qquad\mbox{mit}\qquad\varepsilon:=M\cdot d -U$$

$$U=2^z$$

 muss man passend w"ahlen, z.B. z=35 im obigen Fall.

Wer weiss mehr dar"uber?
War es wirklich n"otig, dass ich das selber herleiten musste, im 
sogenannten Informationszeitalter??
In den gcc-Sourcen hab ich die Optimierung auch noch nicht gefunden... 
:(
Wer hat da ein H"andchen f"ur?

[Peter D. (peda)]

Die interessante Frage ist aber:

Wird diese Operation wirklich 100.000 mal je Sekunde benötigt, damit 
sich eine Optimierung auch lohnt?

Ich hatte mal die Dezimal-Umwandlung nach der Subtraktionsmethode 
geschrieben, weil die ersten AVRs ziemlich knauserig mit Flash waren, 
also zur Codeersparnis.

[M, nicht Q (Gast)]

Peter Dannegger schrieb:
> Die interessante Frage ist aber:
>
> Wird diese Operation wirklich 100.000 mal je Sekunde benötigt, damit
> sich eine Optimierung auch lohnt?

Darauf gibt es folgende Antworten

ja - Dann muss man es machen

nein - Dann sollte man es lassen

weiß nicht - Anhänger des YAGNI-Prinzips würden es lassen; Anhänger 
von "Spare in der Zeit, dann hast du in der Not" würden es machen.

[Oliver (Gast)]

M, nicht Q schrieb:
> Anhänger
> von "Spare in der Zeit, dann hast du in der Not" würden es machen.

Na ja, in der Softwareentwicklung ist das der schnellste Weg ins 
Verderben. Solange man überhaupt keine Vorstellung über 
timing-Anforderungen und tatsächliche Laufzeiten in einem Programm hat, 
führt das nur zu unnötiger Komplexität mit allen Problemen, die sich 
daraus ergeben.

Oliver

[Luther B. (luther-blissett)]

Hacker's Delight beschreibt wie man das multiplikative Inverse 
berechnet, ausserdem Methoden um die Division anzunähern. 
Praktischerweise gibt es den Teil online, der Methoden beschreibt durch 
10 und andere kleine Konstanten zu dividieren (divu10,divs10):

http://www.hackersdelight.org/divcMore.pdf

[Waldo (Gast)]

q=(x*26-x/2+153)/256
liefert mit x von 0 bis 255:
q=runde(x/10)

[TomA. (Gast)]

Mein Vorschlag:

Hex -> BCD, dann 4Bit rechts schieben (=/10), dann BCD -> Hex.

Für Hex -> BCD haben viele Controler einen Assemblerbefehl (DAA oder 
ähnlich), der kann auch per Software nachgebildet werden. Im Ergebnis 
ist nur noch eine BCD-Zahl zwischen 0x00 und 0x25 nach Hex (0x00-0x19) 
zu wandeln, das geht am schnellsten mit einer Tabelle.

Die Funktionsweise der Hex->BCD Wandlung kann man im Befehlssatz eines 
MCS51-Kontrollers, beim Befehl DA A, nachsehen. Sind im Grunde nur zwei 
Additionen, einmal mit 0x06 und einmal mit 0x60.

Ich hoffe ich konnte helfen.
Gruß. Tom

[MarcVonWindscooting (Gast)]

Peter Dannegger schrieb:
> Ich hatte mal die Dezimal-Umwandlung nach der Subtraktionsmethode
> geschrieben, weil die ersten AVRs ziemlich knauserig mit Flash waren,
> also zur Codeersparnis.

Ist denn eine Konstante zur Compile-Zeit berechnen und zur Laufzeit 
diese mit 'nem Parameter multiplizieren und dann shiften komplizierter 
als in einer Schleife zu subtrahieren? Und was wird subtrahiert? 
Brauchen diese Konstanten keinen Platz. Vermutlich ist der Code kleiner 
als bei deiner Subtraktionsmethode, vorausgesetzt man braucht eine lange 
Multiplikation noch sonst irgendwo im Programm.

Und man muss es vielleicht auch so sehen: hat man denn eine Division 
"uberhaupt?
Promimente Beispiele:
ARM7TDMI: kein Divisionsbefehl, aber 32x32=>64 bit Multiplikation!
CortexM3: DIV:2..12 cycles, SMULL/UMULL:4..7cyles, SHIFTs:0..1 cycle
CortexM0: DIV:viele (emuliert), SMULL/UMULL: < viele/2 (experimentell 
best.)

Man muss nicht 100.000 mal in der Sekunde die Konvertierung machen 
m"ussen, es reicht eine einzige, wenn die in total selten auftretenden 
Einzelf"allen eine ISR am rechtzeitigen Ausf"uhren hindert ;-)

Und hab ich nicht extra geschrieben, dass (und unter welchen Bedingungen 
mindestens) gcc das sowieso macht, man also

A)
for (...) {
  digit = '0' + value % 10;  // optimized by gcc
  value = value / 10;  // optimized by gcc
}

statt:

B)
for (...) {
  digit = '0' + value % 10; // I don't care a sh*t
  value = value / 10;  // I don't care a sh*t
}

schreiben darf? Wann ist also A) unn"otige Verkomplizierung von B) die 
geradewegs in die H"olle der Informatik f"uhrt? ;-)

[Axel S. (a-za-z0-9)]

Peter Dannegger schrieb:
> Die interessante Frage ist aber:
>
> Wird diese Operation wirklich 100.000 mal je Sekunde benötigt, damit
> sich eine Optimierung auch lohnt?
>
> Ich hatte mal die Dezimal-Umwandlung nach der Subtraktionsmethode
> geschrieben, weil die ersten AVRs ziemlich knauserig mit Flash waren,
> also zur Codeersparnis.

Die andere Frage ist: Wofür braucht man das? Wenn es (wie von 
Vorpostern vermutet) um eine Binär->Dezimal(string) Wandlung geht, dann 
kann man auch direkt eine Binär->BCD Konvertierung machen. Die ist nur 
unwesentlich aufwendiger als eine einzelne Division durch 10.


XL

[Peter D. (peda)]

Hier nochmal der auf Größe optimierte Code:

;Convert unsigned 16bit to ASCII
;
;input: R17, R16 = 16 bit value 0 ... 65535
;output: R20, R19, R18, R17, R16 = 5 digits (ASCII)
;
bin16_ascii:
  ldi  r20, -1 + '0'
_bcd1:
  inc  r20
  subi  r16, low(10000)
  sbci  r17, high(10000)
  brcc  _bcd1
  ldi  r19, 10 + '0'
_bcd2:
  dec  r19
  subi  r16, low(-1000)
  sbci  r17, high(-1000)
  brcs  _bcd2
  ldi  r18, -1 + '0'
_bcd3:
  inc  r18
  subi  r16, low(100)
  sbci  r17, high(100)
  brcc  _bcd3
  ldi  r17, 10 + '0'
_bcd4:
  dec  r17
  subi  r16, -10
  brcs  _bcd4
  subi  r16, -'0'
  ret

[Johann L. (gjlayde)]

Man kann einfach GCC fragen, indem man x / 10 übersetzt:

#include <stdint.h>

uint16_t udiv10 (uint16_t x)
{
    return x / 10;
}

mit, z.B:

$ avr-gcc -O2 -S -mmcu=atmega8 div10.c

Das ergibt:

udiv10:
  movw r18,r24
  ldi r26,lo8(-51)
  ldi r27,lo8(-52)
  rcall __umulhisi3
  lsr r25
  ror r24
  lsr r25
  ror r24
  lsr r25
  ror r24
  ret

Auf Deutsch:

1) Lade die Konstante -(-1u / 5) = 0xffffcccd

2) Multipliziere x mit dieser Konstanten, wobei die Multiplikation
   eine erweiternde 16u * 16u = 32u Multiplikation ist.  Auf
   einem AVR mit MUL reichen dafür 12 Instruktionen.

3) Schiebe das Ergebnis um 19 Bits nach rechts, bzw. nimm die oberen
   16 Bits und schiebe diese um 3 Bits nach rechts.

Voilà!

Und die funktioniert für alle Eingaben, und du brauchst kein 
Reverse-Engineering, um herauszufinden, für welche Zahlen das geht oder 
nicht.

[Oliver (Gast)]

Johann L. schrieb:
> Man kann einfach GCC fragen, indem man x / 10 übersetzt:

Die Idee ist aber so abwegig, da kommt man doch nicht drauf ;)

Oliver

[Karl H. (kbuchegg)]

TomA. schrieb:
> Mein Vorschlag:
>
> Hex -> BCD, dann 4Bit rechts schieben (=/10), dann BCD -> Hex.
>

Äh. nein.

> Für Hex -> BCD haben viele Controler einen Assemblerbefehl (DAA oder
> ähnlich)

schon, aber das funktioniert nur nach Operationen, die als Operanden 
schon BCD Zahlen hatten und deren Ergebnis (zb nach einer Addition) 
wieder auf BCD korrigiert werden muss.

Ein DAA ist kein allgemeiner Hex-BCD Konverter. Für den kommt man um 
eine Division durch 10 nicht rum.

[Mark B. (markbrandis)]

Johann L. schrieb:
> Und die funktioniert für alle Eingaben, und du brauchst kein
> Reverse-Engineering, um herauszufinden, für welche Zahlen das geht oder
> nicht.

Einmal mehr zeigt sich, dass man das Optimieren in der Regel dem 
Compiler überlassen sollte. Es sei denn natürlich, man verwendet völlig 
ineffiziente Algorithmen - aber das ist bei einer einfachen Divison ja 
nicht der Fall.

[Axel S. (a-za-z0-9)]

Karl Heinz schrieb:
> Ein DAA ist kein allgemeiner Hex-BCD Konverter. Für den kommt man um
> eine Division durch 10 nicht rum.

Doch. Man kann Binär nach BCD umwandeln ohne eine einzige Division. 
Stichwort: Dreierkorrektur


XL

[Markus (Gast)]

Johann L. you made my day!

[Julia (Gast)]

Hat denn mal jemand einen Beispielcode zur effizienten BCD-Umwandlung 
(hin- und zurück)? Hier findet man nur Andeutungen, das zweite Mal 
jetzt, aber nichts Konkretes. Der ATMega hat keine Hardware-BCD-Befehle, 
soweit ich weiß und es gibt leider auch in der gcc-lib keine 
voroptimierten Funktionen. Wenn man googelt, findet man auch nur Code, 
den man genau so selbst schnell zusammengehackt hätte, z.B.

uint8_t byte_to_bcd(uint8_t b) {
  div_t q = div(b, 10);
  return (q.quot << 4) + q.rem;
}

uint8_t bcd_to_byte(uint8_t b) {
  return (b >> 4) * 10 + (b & 0x0F);
}

[Peter D. (peda)]

Julia schrieb:
> Hat denn mal jemand einen Beispielcode zur effizienten BCD-Umwandlung

Wozu sollte man denn sowas benötigen?
Wenn ich dezimal ausgebe, dann entweder 7-Segment oder ASCII.
Packed BCD habe ich noch nie gebraucht.

[Julia (Gast)]

Verschiedene RTCs wollen Daten im BCD-Format. Wenn man die 
weiterverarbeitet, kommt man um eine Umrechnung nicht herum.

[Yalu X. (yalu) (Moderator)]

Von binär nach BCD:

  http://www.eng.utah.edu/~nmcdonal/Tutorials/BCDTutorial/BCDConversion.html

anderherum geht es ganz klassisch, da man dort keine Divisionen, sondern 
nur Multiplikationen braucht, die der ATmega ja bekanntlich kann.

[Johann L. (gjlayde)]

Marc P. schrieb:

> In den gcc-Sourcen hab ich die Optimierung auch noch nicht gefunden...

In gcc/expmed.c:expand_divmod() oder in Unterroutine davon wie 
choose_multiplier().

http://gcc.gnu.org/viewcvs/gcc/trunk/gcc/expmed.c?revision=206289&view=markup#l3853

[Luther B. (luther-blissett)]

Yalu X. schrieb:
> Von binär nach BCD:
>
>   http://www.eng.utah.edu/~nmcdonal/Tutorials/BCDTutorial/BCDConversion.html
>

Was immer gut geht ist die Verwendung von vorberechneten Tabellen. Wenn 
man dort nur Grobwerte speichert, die man aber in wenigen Schritten 
verfeinern kann, ist man schnell und eingermaßen speicherschonend.

typedef struct 
{
  uint8_t quot, rem; 
} divu8_t;

// 32 bytes vorberechnete Werte.
divu8_t div10_tbl[16]={
  {0,0},{1,6},{3,2},{4,8},
  {6,4},{8,0},{9,6},{11,2},
  {12,8},{14,4},{16,0},{17,6},
  {19,2},{20,8},{22,4},{24,0}
  };

// div10 ist nur mehr ein Lookup + eine Korrektur.
divu8_t div10(int n)
{
  divu8_t d=div10_tbl[n>>4]; 

  // n&0xf wurde noch nicht mitdividiert, also:
  d.rem+=n&0xf; 

  // d.rem ist maximal 9+15 = 24, daher:
  if (d.rem>=20) { d.quot+=2; d.rem-=20; }
  else if (d.rem>=10) { d.quot+=1; d.rem-=10; }
  return d;
}

[lolli (Gast)]

hach ja. Seit ich von 8bit AVR auf 32bit Cortex mit FPU umgestiegen bin 
brauch ich sowas nicht mehr. Seitdem ist x/10 wieder x/10 :-))

[Luther B. (luther-blissett)]

lolli schrieb:
> hach ja. Seit ich von 8bit AVR auf 32bit Cortex mit FPU umgestiegen bin
> brauch ich sowas nicht mehr. Seitdem ist x/10 wieder x/10 :-))

Solche Algorithmne sind nicht nutzlos. Die Cortex M1 und M0 haben z.B. 
keine Hardware-Division und auch die Multiplikation darf dort im 
schlimmsten Falle 32 Zyklen dauern. FPGA-Entwickler freuen sich auch 
über Algorithmen die wenig Ressourcen brauchen und rein kombinatorisch 
implementiert werden können.

[Johann L. (gjlayde)]

Eine FPU hilft dir dabei aber nicht :-)

[Marc P. (marcvonwindscooting)]

Johann L. schrieb:

> In gcc/expmed.c:expand_divmod() oder in Unterroutine davon wie
> choose_multiplier().
>
> 
http://gcc.gnu.org/viewcvs/gcc/trunk/gcc/expmed.c?revision=206289&view=markup#l3853

Hey Danke!
Wird 'ne Zeit dauern das durchzuarbeiten...

[Peter D. (peda)]

Julia schrieb:
> Verschiedene RTCs wollen Daten im BCD-Format.

Einmal pro Sekunde umrechnen ist natürlich knallharte Echtzeit. Da kommt 
die CPU ohne super optimierte Umrechnung schnell an ihre Grenzen.

[Julia (Gast)]

Das sicher nicht. Es passiert sogar noch viel seltener (beim Start). 
Aber es zählt mittlerweile jedes einzelne Byte! Insgeheim warte ich ja 
auf den mega648... aber das ist OT.

[Peter D. (peda)]

Julia schrieb:
> Aber es zählt mittlerweile jedes einzelne Byte! Insgeheim warte ich ja
> auf den mega648

Oh, 32kB hast Du schon voll.
Dann kann ich Dir versichern, die RTC-Routinen sind definitiv nicht der 
Flash-Verbraucher. Da müssen noch andere Routinen sein, wo man wirklich 
Code einsparen kann.
Vergiß also die Optimierung der RTC, das ist pure Zeitverschwendung.
Schau mal die Routinen an, die >10% verbrauchen.

[Axel S. (a-za-z0-9)]

Julia schrieb:
> Hat denn mal jemand einen Beispielcode zur effizienten BCD-Umwandlung
> (hin- und zurück)? Hier findet man nur Andeutungen, das zweite Mal
> jetzt, aber nichts Konkretes.

AVR Appnote 204. Der Algorithmus heißt "Dreierkorrektur". Eine sehr 
ausführliche Beschreibung findet sich auf totem Baum: Lampe, Jorke, 
Wengel "Arithmetischen Algorithmen der Mikrorechentechnik".

Und übrigens eignet sich der Algorithmus auch ebenfalls für die 
Gegenrichtung (BCD->Binär). Und zwar wieder ohne Multiplikation. Man muß 
nur Bits schieben und Additionen auf einzelnen Worten (8 Bit oder was 
man hat) konnen.

Peter Dannegger schrieb:
> Wozu sollte man denn sowas benötigen?
> Wenn ich dezimal ausgebe, dann entweder 7-Segment oder ASCII.
> Packed BCD habe ich noch nie gebraucht.

Aha. Für beides brauchst du erstmal einzelne Dezimalziffern. Und zwar am 
besten in der Reihenfolge von vorn nach hinten. Da ist BCD als 
Zwischenformat ziemlich toll.

Einen netten Trick habe ich mal gesehen: die verwendete CPU (z8) kann 
wahlweise binäre oder BCD-Arithmetik. Da wurden alle Rechnungen bis auf 
die letzte binär gemacht. Und im letzten Rechenschritt wurde das 
Ergebnis direkt in BCD ausgerechnet. Die Konvertierung zu 7-Segment 
(genauso wie Kommasetzung, Kommaverschiebung etc.) war dann natürlich 
ein Klacks.


XL

[Peter D. (peda)]

Axel Schwenke schrieb:
> Aha. Für beides brauchst du erstmal einzelne Dezimalziffern. Und zwar am
> besten in der Reihenfolge von vorn nach hinten. Da ist BCD als
> Zwischenformat ziemlich toll.

Ziemlich unsinnig, 2 Ziffern zusammen zu bauen und dann gleich wieder 
auseinander.

Schau Dir mal oben meinen kompakten AVR-Code an, der bastelt direkt 
ASCII ohne Umwege:
Beitrag "Re: effiziente Division durch 10"

[Amateur (Gast)]

Geht es ausschließlich um die Division durch 10, so könnte, je nach 
Geschwindigkeit der Schiebeoperationen auch folgender Ansatz gehen:

8 Bit Division durch 10
SUMME ((X>>4)+(X>>5))

X=X>>4;
Res=X;
Res+= X>>1;

ENTSP 1/0,09375
Bei einer 8-Bit Zahl sind Schiebeoperationen um 8 Bit (die nächste 
Möglichkeit) oder mehr sinnlos.


16 Bit Division durch 10
SUMME ((X>>4)+(X>>5)+(X>>8)+(X>>9)+(X>>12)+(X>>13))

X=X>>4;
Res=X;
X=X>>1;
Res+=X;
X=X>>3;
Res+=X;
X=X>>1;
Res+=X;
X=X>>3;
Res+=X;
Res+=( X>>1);

ENTSP 1/0,0999755859375
Bei einer 16-Bit Zahl sind Schiebeoperationen um 16 Bit (die nächste 
Möglichkeit) oder mehr sinnlos.

Insbesondere bei einer Umsetzung in Assembler dürfte das ein recht 
flotter Heinrich werden;-)

Übrigens: Genauer geht’s Ganzzahlig nicht!

[Axel S. (a-za-z0-9)]

Peter Dannegger schrieb:
> Axel Schwenke schrieb:

>> Aha. Für beides brauchst du erstmal einzelne Dezimalziffern. Und zwar am
>> besten in der Reihenfolge von vorn nach hinten. Da ist BCD als
>> Zwischenformat ziemlich toll.
>
> Ziemlich unsinnig, 2 Ziffern zusammen zu bauen und dann gleich wieder
> auseinander.

Die Ziffern werden gar nicht paarweise zusammengebaut. Vielmehr entsteht 
die BCD-Darstellung bitweise, ganz ähnlich wie das Ergebnis einer 
Division oder Multiplikation.

> Schau Dir mal oben meinen kompakten AVR-Code an, der bastelt direkt
> ASCII ohne Umwege:
> Beitrag "Re: effiziente Division durch 10"

Wenn du den mal auf ein paar mehr Stellen umbaust, ist er nicht mehr so 
kurz. Zum Vergleich der Kern (ohne Kopieren von Eingabe/Ausgabe und 
Sichern der Arbeitsregister) für eine 64-Bit Binär -> BCD Konvertierung. 
Wegen der schlechteren Effizienz der BCD-Darstellung darf die Eingabe 
nur zwischen 0 und 99'999'999 = 0x5f5e0ff liegen. Das ist für das 
Projekt, aus dem das Codeschnipsel stammt, kein Hindernis, aber 
einfachst zu umgehen, wenn man den Zielpuffer um ein 9. Byte vergrößert.

                /* initialize result */                                         
                clr bcd0                                                        
                clr bcd1                                                        
                clr bcd2                                                        
                clr bcd3                                                        
                                                                                
                clr zregh                                                      
                ldi loop, 32                                                    
                                                                                
1:              lsl bin0                                                        
                rol bin1                                                        
                rol bin2                                                        
                rol bin3                                                        
                rol bcd0                                                        
                rol bcd1                                                        
                rol bcd2                                                        
                rol bcd3                                                        
                dec loop                                                        
                breq 3f                                                         
                                                                                
                /* decimal correction "Dreierkorrektur" */                      
                ldi zregl, bcd3+1                                                
2:              ld tmp, -z                                                      
                subi tmp, -0x03                                                 
                sbrc tmp, 3                                                     
                st z, tmp                                                       
                ld tmp, z                                                       
                subi tmp, -0x30                                                 
                sbrc tmp, 7                                                     
                st z, tmp                                                       
                cpi zregl, bcd0                                                  
                brne 2b                                                         
                rjmp 1b                                                         
                                                                                
3:              /* store back bcd result */

Für 64 Bit ist das nicht nur kürzer, sondern auch schneller. Und es ist 
eine ganz simpel aufgebohrte Variante der AVR204 Appnote.

Der komplette Code findet sich in arith.S im Firmwarearchiv zu diesem 
Projekt: Beitrag "AVR-Frequenzzählermodul 1Hz - 40MHz"


XL


Edit: kein 9. Byte, sondern eine 9. Stelle bzw. ein 5. Byte

[Marc P. (marcvonwindscooting)]

Marc P. schrieb:
> Und zu allem "Uberfluss ist diese Optimierung mindestens im gcc-4.8.1
> drin, wenn man f"ur einen ARM7 (UMULL, SMULL!) compiliert (-O2).

Tja, mittlerweile bin ich desillusioniert. gcc-4.8.1 macht die 
Optimierung auf 32-bit Werten, aber nicht bei 16-bit oder 8-bit. Und 
auf dem Cortex-M0 dann folglich nix, ausser stinklahmem Code :-(((
Gerade beim langsameren Cortex-M0 l"asst sich der gcc so gehen...!

Daher hier als Nachtrag, die passenden Konstanten fur 16-bit unsigned 
division durch 10:

M = 52429, z = 19. (32-bit f"ur Multiplikation)

n DIV 10 = (uint32_t)n * 52429ul >> 19  (exakt f"ur alle n<=16 bit)

Eine Umsetzungsvorschlag findet ihr als Anlage. Mit dem *.h kann man 
dann seine Dezimalkonvertierungsroutinen mit den entsprechenden Aufrufen 
gestalten und die Division per #defines (im Makefile) ausw"ahlen.

EDIT: Fehler verbessert

[Mr. Tom (Gast)]

lolli schrieb:
> hach ja. Seit ich von 8bit AVR auf 32bit Cortex mit FPU umgestiegen bin
> brauch ich sowas nicht mehr. Seitdem ist x/10 wieder x/10 :-))

Ich höre schon die Jammerei nach der Steckdose, wenn der Remote-Sensor 
im Dauereinsatz alle paar Messpunkten einen neuen Batteriesatz braucht.