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. :)
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... %)
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.
> 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.
Stichwort: Multiplikation mit dem ternären Kehrwert. Suchen darfst selber.
Dem Threadstarter geht es um Ganzzahldivision. Da ist ein ternärer Kehrwert nicht wirklich hilfeich.
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.
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 :-)
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.
Folgende Idee für 8 Bit: Mathematisch gilt doch sicher
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
Bestimmt ist das gemeint: Efficient Multiplication and Division Using MSP430 http://focus.ti.com/lit/an/slaa329/slaa329.pdf
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.
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 ;)
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
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).
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
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:
mit:
Und gilt f"ur:
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?
:
Bearbeitet durch User
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.
:
Bearbeitet durch User
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.
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
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
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
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? ;-)
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
Hier nochmal der auf Größe optimierte Code:
1 | ;Convert unsigned 16bit to ASCII |
2 | ; |
3 | ;input: R17, R16 = 16 bit value 0 ... 65535 |
4 | ;output: R20, R19, R18, R17, R16 = 5 digits (ASCII) |
5 | ; |
6 | bin16_ascii: |
7 | ldi r20, -1 + '0' |
8 | _bcd1: |
9 | inc r20 |
10 | subi r16, low(10000) |
11 | sbci r17, high(10000) |
12 | brcc _bcd1 |
13 | ldi r19, 10 + '0' |
14 | _bcd2: |
15 | dec r19 |
16 | subi r16, low(-1000) |
17 | sbci r17, high(-1000) |
18 | brcs _bcd2 |
19 | ldi r18, -1 + '0' |
20 | _bcd3: |
21 | inc r18 |
22 | subi r16, low(100) |
23 | sbci r17, high(100) |
24 | brcc _bcd3 |
25 | ldi r17, 10 + '0' |
26 | _bcd4: |
27 | dec r17 |
28 | subi r16, -10 |
29 | brcs _bcd4 |
30 | subi r16, -'0' |
31 | ret |
Man kann einfach GCC fragen, indem man x / 10 übersetzt:
1 | #include <stdint.h> |
2 | |
3 | uint16_t udiv10 (uint16_t x) |
4 | {
|
5 | return x / 10; |
6 | }
|
mit, z.B: $ avr-gcc -O2 -S -mmcu=atmega8 div10.c Das ergibt:
1 | udiv10: |
2 | movw r18,r24 |
3 | ldi r26,lo8(-51) |
4 | ldi r27,lo8(-52) |
5 | rcall __umulhisi3 |
6 | lsr r25 |
7 | ror r24 |
8 | lsr r25 |
9 | ror r24 |
10 | lsr r25 |
11 | ror r24 |
12 | 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.
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
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.
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.
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
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.
1 | uint8_t byte_to_bcd(uint8_t b) { |
2 | div_t q = div(b, 10); |
3 | return (q.quot << 4) + q.rem; |
4 | }
|
5 | |
6 | uint8_t bcd_to_byte(uint8_t b) { |
7 | return (b >> 4) * 10 + (b & 0x0F); |
8 | }
|
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.
Verschiedene RTCs wollen Daten im BCD-Format. Wenn man die weiterverarbeitet, kommt man um eine Umrechnung nicht herum.
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.
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
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.
1 | typedef struct |
2 | {
|
3 | uint8_t quot, rem; |
4 | } divu8_t; |
5 | |
6 | // 32 bytes vorberechnete Werte.
|
7 | divu8_t div10_tbl[16]={ |
8 | {0,0},{1,6},{3,2},{4,8}, |
9 | {6,4},{8,0},{9,6},{11,2}, |
10 | {12,8},{14,4},{16,0},{17,6}, |
11 | {19,2},{20,8},{22,4},{24,0} |
12 | };
|
13 | |
14 | // div10 ist nur mehr ein Lookup + eine Korrektur.
|
15 | divu8_t div10(int n) |
16 | {
|
17 | divu8_t d=div10_tbl[n>>4]; |
18 | |
19 | // n&0xf wurde noch nicht mitdividiert, also:
|
20 | d.rem+=n&0xf; |
21 | |
22 | // d.rem ist maximal 9+15 = 24, daher:
|
23 | if (d.rem>=20) { d.quot+=2; d.rem-=20; } |
24 | else if (d.rem>=10) { d.quot+=1; d.rem-=10; } |
25 | return d; |
26 | }
|
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 :-))
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. 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...
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.
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.
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.
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
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"
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!
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.
1 | /* initialize result */ |
2 | clr bcd0 |
3 | clr bcd1 |
4 | clr bcd2 |
5 | clr bcd3 |
6 | |
7 | clr zregh |
8 | ldi loop, 32 |
9 | |
10 | 1: lsl bin0 |
11 | rol bin1 |
12 | rol bin2 |
13 | rol bin3 |
14 | rol bcd0 |
15 | rol bcd1 |
16 | rol bcd2 |
17 | rol bcd3 |
18 | dec loop |
19 | breq 3f |
20 | |
21 | /* decimal correction "Dreierkorrektur" */ |
22 | ldi zregl, bcd3+1 |
23 | 2: ld tmp, -z |
24 | subi tmp, -0x03 |
25 | sbrc tmp, 3 |
26 | st z, tmp |
27 | ld tmp, z |
28 | subi tmp, -0x30 |
29 | sbrc tmp, 7 |
30 | st z, tmp |
31 | cpi zregl, bcd0 |
32 | brne 2b |
33 | rjmp 1b |
34 | |
35 | 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
:
Bearbeitet durch User
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
:
Bearbeitet durch User
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.