Hallo, ist es möglich eine Zahl (egal ob uint8,16,32) in einen ASCII-String zu wandeln ohne Division oder Modulo? Hintergrund, viele uC besitzen keinen dividierer und müssen das durch Zeitaufwendige Tricksereien bereitstellen. LG
Annalena Grasmann schrieb: > Hintergrund, viele uC besitzen keinen dividierer und müssen das durch > Zeitaufwendige Tricksereien bereitstellen. Und was ist jetzt das Problem dabei? Wenn der µC dabei zu langsam ist, dann ist er für solche Aufgaben halt ungünstig gewählt. > ist es möglich eine Zahl (egal ob uint8,16,32) in einen ASCII-String zu > wandeln ohne Division oder Modulo? Du könntest mit viel Speicher und einer darin abgelegten Tabelle arbeiten. Oder einen speziellen ITOA-Koprozessor anschließen. Aber für die restlichen Ansätze lautet die Antwort: Nein. Denn das "Verstecken" der Division in wiederholten Subtraktionen oder Zustandsautomaten verwendet ja trotzdem eine Division.
Annalena Grasmann schrieb: > und müssen das durch > Zeitaufwendige Tricksereien bereitstellen. Die Frage ist: Ist es wirklich effizienter, durch Tricksereien einen Modulo im itoa() zu vermeiden, anstatt die Tricksereien ins Modulo zu "outsourcen"?
Subtraktion und Schleifen... Was anderes steckt auch nicht hinter einer Division (mit Rest / Modulo).
Für Basen der Form 2^n ist es trivial, ansonsten z.B. zählen, wie häufig man eine Potenz der Basis abziehen kann (beginnend mit der größten, also für Basis 10 und int16: 10000, dann 1000, 100, 10, 1).
Es geht ohne Division, wenn man die Zahl binär in den String schreibt. :-)
Lothar M. schrieb: > Annalena Grasmann schrieb: > >> Hintergrund, viele uC besitzen keinen dividierer und müssen das durch >> Zeitaufwendige Tricksereien bereitstellen. > > Und was ist jetzt das Problem dabei? > Wenn der µC dabei zu langsam ist, dann ist er für solche Aufgaben halt > ungünstig gewählt. >> ist es möglich eine Zahl (egal ob uint8,16,32) in einen ASCII-String zu >> wandeln ohne Division oder Modulo? > > Du könntest mit viel Speicher und einer darin abgelegten Tabelle > arbeiten. Oder einen speziellen ITOA-Koprozessor anschließen. > Aber für die restlichen Ansätze lautet die Antwort: Nein. > Denn das "Verstecken" der Division in wiederholten Subtraktionen oder > Zustandsautomaten verwendet ja trotzdem eine Division. Man könnte auch eine kleinere LUT nehmen und Multiplikationen und additionen im String machen, wenn ich mich nicht irre. Allerdings ist das vermutlich auch nicht unbedingt performanter als die SW Division. Zumal man den Code ja so schreiben kann, dass man nur /10 und %10 braucht, vielleicht bekommt man das ja auch mit LUT optimiert.
Annalena Grasmann schrieb: > ist es möglich eine Zahl (egal ob uint8,16,32) in einen ASCII-String zu > wandeln ohne Division oder Modulo? Natürlich. > Hintergrund, viele uC besitzen keinen dividierer und müssen das durch > Zeitaufwendige Tricksereien bereitstellen. Das sind keine "Tricksereien", sondern Algorithmen. Ich habe in der Schule noch gelernt, wie man schriftlich dividiert. Du nicht?
Annalena Grasmann schrieb: > Hintergrund, viele uC besitzen keinen dividierer und müssen das durch > Zeitaufwendige Tricksereien bereitstellen. Definiere zeitaufwendig. Der MC kann über 1000-mal schneller Dezimalzahlen ausgeben, als ein Mensch sie ablesen kann. Ausgaben sind also in keinster Weise zeitkritisch. Man kann etwas Zeit und Flash sparen, indem man die Ausgabe mittels Subtraktion von Zehnerpotenzen macht. Sobald man aber auch nur eine Berechnung braucht, sind alle Vorteile hinfällig. Ich benutze auf 8-Bittern eh nur noch float, da ich nur so die nötige Dynamik erreiche und mich nicht mit Überläufen und Rundungsfehlern abplagen muß.
Geht es um Zahlen, die schon dezimal vorliegen oder hex? Anscheinend darf es beides sein https://doc.embedded-wizard.de/uint-type?v=8.10 Data types: uint8, uint16, uint32 Represents an unsigned integer number stored with 8, 16 or 32 bit. decimal‑literal 0xhex‑decimal‑literal https://www.mikrocontroller.net/articles/AVR_Arithmetik#Bin%C3%A4r_zu_BCD_-_Umwandlung das ist für hex der erste Schritt, umwandeln in BCD Je nach Algorithmus erhält man einzelne Ziffern oder "gepacktes" BCD mit zwei Stellen in einem Byte. Dann muss man vor die Einzelstelle nur noch "eine 3 davorschreiben" um eine ASCII-Zahl 0x30...0x39 zu erhalten.
:
Bearbeitet durch User
Christoph db1uq K. schrieb: > Je nach Algorithmus erhält man einzelne Ziffern oder "gepacktes" BCD > mit zwei Stellen in einem Byte. Ach richtig, da war ja noch der Shift-Add-3 ... https://en.wikipedia.org/wiki/Double_dabble Nachdem keine spezielle Sprache gefragt war: hier ein paar Lösungen für VHDL ;-) http://www.lothar-miller.de/s9y/categories/44-BCD-Umwandlung
:
Bearbeitet durch Moderator
Danke, die Bezeichnung "Double dabble" kannte ich noch nicht. Habs eingetragen.
Lothar M. schrieb: > Aber für die restlichen Ansätze lautet die Antwort: Nein. > Denn das "Verstecken" der Division in wiederholten Subtraktionen oder > Zustandsautomaten verwendet ja trotzdem eine Division. Nö, durch wiederholtes Subtrahieren ist man immer schneller (weniger Takte) als für jede Dezimalstelle eine komplette Division zu tun. Der tiefere Grund liegt darin, daß man pro Ziffer quasi nur eine Schleife zu durchlaufen hat anstelle soviel Schleifen wie Bits. Und da man zumeist mehr als 10 Bit breite Integer hat, ist das auch bei Dezimalausgabe von hause aus sparsamer als die Division. W.S.
W.S. schrieb: > Nö, durch wiederholtes Subtrahieren ist man immer schneller (weniger > Takte) als für jede Dezimalstelle eine komplette Division Falsch. Rechne es nach.
Axel S. schrieb: > Falsch. Rechne es nach. Hast du schon mal eine Division in einer 8 Bit Maschine selbst geschrieben? Also wo du keinen Divisionsbefehl im Maschinencode zur Verfügung hattest? Aus deinen Worten schließe ich, daß du so etwas noch nie getan hast. W.S.
Axel S. schrieb: > Falsch. Rechne es nach. Rechne Du mal nach. Die Subtraktionsmethode ist schneller als mit Division in Software: Beitrag "Re: 8bis32bit binär in Dezimal ausgeben"
:
Bearbeitet durch User
Peter D. schrieb: > Rechne Du mal nach. Die Subtraktionsmethode ist schneller als mit > Division in Software: > > Beitrag "Re: 8bis32bit binär in Dezimal ausgeben" Da braucht mein Schnipsel in C deutlich länger, kann leider die Zyklen nicht messen da das mein ARM im Atmel Studio nicht zulässt und fürs Zählen bin ich zu Faul.
1 | char *itoa_16(uint16_t val) |
2 | {
|
3 | //asm volatile("BKPT #0");
|
4 | static char digit[5]; |
5 | |
6 | for(uint8_t x = 0; x < sizeof(digit); x++) digit[x] = '0'; |
7 | |
8 | while(val > 9999) { val -= 10000; digit[0]++; } |
9 | while(val > 999) { val -= 1000; digit[1]++; } |
10 | while(val > 99) { val -= 100; digit[2]++; } |
11 | while(val > 9) { val -= 10; digit[3]++; } |
12 | digit[4] += val; |
13 | |
14 | //asm volatile("BKPT #1");
|
15 | return digit; |
16 | }
|
Lothar M. schrieb: > Aber für die restlichen Ansätze lautet die Antwort: Nein. Für was genau? Peter D. schrieb: > Definiere zeitaufwendig. Der MC kann über 1000-mal schneller > Dezimalzahlen ausgeben, als ein Mensch sie ablesen kann. Ausgaben sind > also in keinster Weise zeitkritisch. Das haben sich die Programmierer bei meinem RNS-510 (Autoradio) auch gedacht, deswegen ist er so langsam... Christoph db1uq K. schrieb: > Geht es um Zahlen, die schon dezimal vorliegen oder hex? > Anscheinend darf es beides sein Verstehe die Aussage/Frage nicht. ITOA nutzt eine INT variable also gehe ich auch davon aus. Ansonsten dec = hex = bin.
Annalena Grasmann schrieb: > Hintergrund, viele uC besitzen keinen dividierer und müssen das durch > Zeitaufwendige Tricksereien bereitstellen. Genau aus diesem Grund wurde das BCD Encoding erfunden und einige Uhren laufen rein mit Addition mit diesem Verfahren ohne Division und ohne Lookuptable (z.B. einige RTCs). Michael
Annalena Grasmann schrieb: > ist es möglich eine Zahl (egal ob uint8,16,32) in einen ASCII-String zu > wandeln ohne Division oder Modulo? Hallo, egal ob eher nicht (es sei denn man will grundsätzlich mit 64 Bit Zahlen arbeiten). Aber meistens braucht man sowieso eine Normierung (z.B. 4095 counts auf dem ADC entsprechen 30 V). also in diesem Beispiel: 1. Linksbündiges schieben des 12 Bit ADC Wertes (falls der Prozessor das nicht anbietet) -> 0xFFF << 4 = 0xFFF0 2. Normierung (16 * 16 Bit Multiplikation) mit 32 Bit Ergebnis. (30 V Endwert bei 0xFFF -> 0x3000 x 0x1000 / 0x0FFF = 0x3003) oder 23.45V bei 0xC800 (knapp 0xc810 aber ADC rundet ab) 0xFFF0 x 0x3003 = 0x2fff ffd0 0xc800 x 0x3003 = 0x2582 5800 3. Runden 0x2fff ffd0 + 0x0000 8000 = 0x3000 7fd0 0x2582 5800 + 0x0000 8000 = 0x2582 D800 -> 16-Bit Ergebnis 0x3000 -> 16-Bit Ergebnis 0x2582 bei 23.45V 4. "3" bzw "2" ist nun das erste ASCII zeichen in Schleife tun: (30V ist uninteressant) 5. führendes Digit entfernen (AND 0x0FFF) -> 0x0582 bei 23.45 V 6. Multiplikation mal 0x000A (0x0582 << 1 + 0x0582 << 3) -> 0x3714 bei 23.45V -> 3 als nächste Ziffer 0x46C8 im nächsten Durchlauf -> 4 als nächste Ziffer 0x43D0 im nächsten Durchlauf -> 4 als letzte Ziffer (wg. ADC) Gruß Anja
Annalena Grasmann schrieb: > Da braucht mein Schnipsel in C deutlich länger, kann leider die Zyklen > nicht messen da das mein ARM im Atmel Studio nicht zulässt und fürs > Zählen bin ich zu Faul. Ist ja auch schlecht geschrieben. Besser wäre zum Beispiel Beitrag "Re: schnelle Wandlung long -> ASCII" Auf einem STM32F407 dauert die Wandlung long2a unter 5 µs.
Michael D. schrieb: > Genau aus diesem Grund wurde das BCD Encoding erfunden und einige Uhren > laufen rein mit Addition mit diesem Verfahren ohne Division und ohne > Lookuptable (z.B. einige RTCs). Möglicherweise habe ich einen Denkfehler aber was nützt mir BCD? Wenn die Zahlen in BCD vorliegen ist es natürlich einfach, '0'(48) zu addieren. Liegen die Zahlen aber als INT vor müssen sie trotzdem durch Division/Modulo in BCD umgerechnet werden. Die meisten Zahlen liegen als INT vor (ADC, RTC, usw.). m.n. schrieb: > Ist ja auch schlecht geschrieben. Besser wäre zum Beispiel > Beitrag "Re: schnelle Wandlung long -> ASCII" > Auf einem STM32F407 dauert die Wandlung long2a unter 5 µs. Ich weiß nicht wie es auf dem ARM ist, auf einem AVR ist die l2a schlechter als meine: itoa32: Time: 51us Cycle: 420 Size: 170Byte l2a: Time: 104,87us Cycle: 839 Size: 432Byte und eine menge SRAM
Annalena Grasmann schrieb: > Ich weiß nicht wie es auf dem ARM ist, Komisch, Du hattest doch von ARM geredet: "... da das mein ARM im Atmel Studio ..." > auf einem AVR ist die l2a schlechter als meine: Ich weiß nicht, was Du falsch gemacht hast. Deine Routine schafft nur uint16_t und ignoriert damit das Vorzeichen.
Annalena Grasmann schrieb: > ist es möglich eine Zahl (egal ob uint8,16,32) in einen ASCII-String zu > wandeln ohne Division oder Modulo? Na klar! Man gibt einfach einen Hex String aus...
Christoph db1uq K. schrieb: > Geht es um Zahlen, die schon dezimal vorliegen oder hex? > Anscheinend darf es beides sein Oh mann, frag lieber, ob es sich um integer oder longint oder int64 handelt. Zur Debatte steht hier die Ausgabekonvertierung. Und damit hier wieder etwas Grund hineinkommt, hänge ich eine Quelle zur Ausgabekonvertierung mal dran. Ohne Division. Dafür aber für den Z80. So! W.S.
W.S. schrieb: > Ohne Division. Dafür aber für den Z80. Wahnsinn! Welch ein tolles Programm, welch ein toller Programmierer! Und was soll das Ganze? Kommt gleich noch Lernbetty zum Tee?
Annalena Grasmann schrieb: > ist es möglich eine Zahl (egal ob uint8,16,32) in einen ASCII-String zu > wandeln ohne Division oder Modulo? > Hintergrund, viele uC besitzen keinen dividierer und müssen das durch > Zeitaufwendige Tricksereien bereitstellen https://dse-faq.elektronik-kompendium.de/dse-faq.htm zeigt 32 bit long in ASCII als l2a: [c] static uint32_t tab[] = {2000000000, 1000000000, 800000000, 400000000, 200000000, 100000000, 80000000, 40000000, 20000000, 10000000, 8000000, 4000000, 2000000, 1000000, 800000, 400000, 200000, 100000, 80000, 40000, 20000, 10000, 8000, 4000, 2000, 1000, 800, 400, 200, 100, 80, 40, 20, 10, 0}; void l2a(uint32_t zahl, char *s) // l -> zu wandelnde Zahl, *s -> Ergebnis { register uint8_t t; // i -> tab-index register uint32_t temp; // für schnellere Ausführung register char j; // j -> aktuelle Ziffer uint32_t *tabptr=tab; if( zahl & 0x80000000UL ) // weglassen wenn zahl unsigned, dann 4000000000 in Tabelle ergänzen und t auf 4 initialisieren { zahl = -zahl; *s++ = '-'; // Vorzeichen für negativ ausgeben } t = 2; while ( *tabptr > zahl ) // Vornullen entfernen, entfällt wenn Nullen gedruckt werden sollen { tabptr++; t >>= 1; if(!t) t=8; } j = '0'; // Start = Ziffer '0' while(1) { temp=*tabptr++; if ( zahl >= temp ) // nicht subtrahieren und <0 damit zahl auch unsigned sein könnte { j+=t; zahl-=temp; } t >>= 1; if ( !t ) // Stellenwechsel { *s++ = j; // Ziffer ablegen j = '0'; if(!*tabptr) break; t = 8; } } *s++=j+(uint8_t)zahl; // letzte Stelle immer ausgeben *s = '\0'; // string abschliessen [/pre] weder zeitaufwändig noch getrickst, nur programmieren muss man können hier in C.
Soweit waren wir schon. Dieses Programm stammt vom Michael B. (laberkopp) und wurde oben schon verlinkt.
Michael D. schrieb: > Genau aus diesem Grund wurde das BCD Encoding erfunden und einige Uhren > laufen rein mit Addition mit diesem Verfahren ohne Division und ohne > Lookuptable Wenn es Uhren in Hardware sind, dann laufen die sinnvollerweise nur so: http://www.lothar-miller.de/s9y/archives/88-VHDL-vs.-Verilog-am-Beispiel-einer-Stoppuhr.html Da wäre es Unsinn, die Millisekunden seit Systemstart zu zählen und zur Anzeige umzurechnen. W.S. schrieb: > Hast du schon mal eine Division in einer 8 Bit Maschine selbst > geschrieben? Der eigentliche Witz an dieser speziellen Division ist, dass es eine Division durch die immer gleiche Konstante(!!) 10 ist. Und da kann man schon mal optimieren wie im Beitrag "effiziente Division durch 10" an einigen Beispielen aufgezeigt. Auf eine FPGA kann man dank der vorhandenen und bereits mitbezahlten 32x32 Multiplizierer eine Division durch 10 auch über Multipikation mit z.B. 6554 und anschließendem "Ignorieren" der unteren 16 Bits machen, denn 6554/65536 = 0.10000610351. Genau genug für die 5 Stellen, die in 16 Bit passen.
Annalena Grasmann schrieb: > ist es möglich eine Zahl (egal ob uint8,16,32) in einen > ASCII-String zu wandeln ohne Division oder Modulo? Die Antwort ist entweder "ja" (es geht ohne Divisionsbefehl) oder "nein" (irgendwas äquivalentes muss man stattdessen machen). > Hintergrund, viele uC besitzen keinen dividierer und müssen das > durch Zeitaufwendige Tricksereien bereitstellen. Dein Anwendungsfall braucht ausschließlich eine Division durch eine konstante 10. Ein guter Compiler generiert dafür optimalen Code je nach verfügbarer Hardware. Das kann eine Multiplikation sein (falls vorhanden) oder Shift-And-Add. Ich habe für ein FPGA-Projekt einfach den C-Code (mit Division und Modulo) auf einen optimierenden ARM-Compiler geschmissen, einen kleinen ARM angegeben und das Ergebnis dann in VHDL implementiert - da war keine Division mehr drin.
m.n. schrieb: > Wahnsinn! Naja, du mußt es nicht so laut herausschreien, daß du vom Z80 keine Erinnerung mehr hast. Das wissen die anderen alle. W.S.
S. R. schrieb: > Dein Anwendungsfall braucht ausschließlich eine Division durch eine > konstante 10. Ähem... das stimmt nicht ganz. Man braucht eine Division durch 10 pro auszugebender Stelle. Und dazu muß die Division komplett durchgerechnet werden. Beim Abzieh-Verfahren startet man mit der Subtraktion der jeweils höchsten möglichen Stelle und das geht dann herunter bis eigentlich zur 10, aber in der Praxis bis zur 1, denn der Rest bringt keinen signifikanten Geschwindigkeits- oder Platzvorteil mehr. Die "Division", die eigentlich nur ein paar Subtraktionen ist, braucht nicht komplett durchgerechnet zu werden, sondern nur soweit, bis die Stelle feststeht. Das ist bei einer CPU ohne Divisionsbefehl im Maschinencode günstiger. W.S.
Jim M. schrieb: > Annalena Grasmann schrieb: >> ist es möglich eine Zahl (egal ob uint8,16,32) in einen ASCII-String zu >> wandeln ohne Division oder Modulo? > > Na klar! Man gibt einfach einen Hex String aus... Die Noch-Mehrheit will es halt kompliziert. Aber irgendwann wird kommen die Zeit, ...
W.S. schrieb: >> Dein Anwendungsfall braucht ausschließlich eine Division >> durch eine konstante 10. > Ähem... das stimmt nicht ganz. > Man braucht eine Division durch 10 pro auszugebender Stelle. Korrekt, aber ein Zeichen für (absichtlich) missverstehendes Lesen. Die wichtige Aussage in dem von dir zitierten Satz ist die KONSTANTE ZEHN, denn eine entsprechende Division kann deutlich besser optimiert werden als eine, wie von dir mehrfach vorgeschlagene, allgemeine Division. > Und dazu muß die Division komplett durchgerechnet werden. Muss sie nicht. Sie kann auf Multiplikationen oder Shift-und-Add mit konstanten Faktoren (hier wieder: verstehendes Lesen!) zurückgeführt werden und muss nicht komplett als Division durchgerechnet werden. > Das ist bei einer CPU ohne Divisionsbefehl im Maschinencode günstiger. Diese Aussage ist nicht allgemeingültig, daher für den allgemeinen Fall falsch. Auf einer CPU ohne Divisions- aber mit Multiplikationsbefehl ist die Verwendung von letzterem beispielsweise günstiger - und dein Z80-Code lässt sich mit DAA an zumindest einer Stelle noch weiter optimieren, also schrei bitte etwas leiser:
1 | outhex4: and 0x0F ; input in A |
2 | add a, 0x90 |
3 | daa |
4 | adc a, 0x40 |
5 | daa |
6 | ld c, a |
7 | call conout |
8 | ret |
Und ich wiederhole meine Aussage: Aktuelle Compiler (z.B. gcc) wissen das durchaus können es auch nutzen:
1 | $ arm-none-eabi-gcc -O3 -mcpu=cortex-m3 -c -o div10.o div10.c |
2 | $ arm-none-eabi-objdump -d div10.o |
3 | [...] |
4 | Disassembly of section .text: |
5 | |
6 | 00000000 <div10>: |
7 | 0: 4a03 ldr r2, [pc, #12] ; (10 <div10+0x10>) |
8 | 2: 17c3 asrs r3, r0, #31 |
9 | 4: fb82 2000 smull r2, r0, r2, r0 |
10 | 8: ebc3 00a0 rsb r0, r3, r0, asr #2 |
11 | c: 4770 bx lr |
12 | e: bf00 nop |
13 | 10: 66666667 .word 0x66666667 |
SDCC und avr-gcc verwenden allerdings die normale Division.
S. R. schrieb: > also schrei bitte etwas leiser: Dann zitiere du etwas präziser. Der zitierte Code ist für die Hex-Ausgabe und nicht für's Dezimale. W.S.
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.