Hallo Existiert ein algorithmus um möglichst effizient einen unsigned int (32 bit) in seine 10er stellen aufzuschlüsseln? Also mit weniger als 18 mul/div/mod operationen. (Mein softcore hat kein HW mul, daher sind diese operationen sehr zeitintensiv).
:
Bearbeitet durch User
Divisionen ?
1 | 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}; |
2 | |
3 | void l2a(uint32_t zahl, char *s) // l -> zu wandelnde Zahl, *s -> Ergebnis |
4 | {
|
5 | register uint8_t t; // i -> tab-index |
6 | register uint32_t temp; // für schnellere Ausführung |
7 | register char j; // j -> aktuelle Ziffer |
8 | uint32_t *tabptr=tab; |
9 | |
10 | |
11 | if( zahl & 0x80000000UL ) // weglassen wenn zahl unsigned, dann 4000000000 in Tabelle ergänzen und t auf 4 initialisieren |
12 | {
|
13 | zahl = -zahl; |
14 | *s++ = '-'; // Vorzeichen für negativ ausgeben |
15 | }
|
16 | t = 2; |
17 | while ( *tabptr > zahl ) // Vornullen entfernen, entfällt wenn Nullen gedruckt werden sollen |
18 | {
|
19 | tabptr++; |
20 | t >>= 1; |
21 | if(!t) t=8; |
22 | }
|
23 | j = '0'; // Start = Ziffer '0' |
24 | while(1) |
25 | {
|
26 | temp=*tabptr++; |
27 | if ( zahl >= temp ) // nicht subtrahieren und <0 damit zahl auch unsigned sein könnte |
28 | {
|
29 | j+=t; |
30 | zahl-=temp; |
31 | }
|
32 | t >>= 1; |
33 | if ( !t ) // Stellenwechsel |
34 | {
|
35 | *s++ = j; // Ziffer ablegen |
36 | j = '0'; |
37 | if(!*tabptr) break; |
38 | t = 8; |
39 | }
|
40 | }
|
41 | *s++=j+(uint8_t)zahl; // letzte Stelle immer ausgeben |
42 | *s = '\0'; // string abschliessen |
43 | }
|
Aus https://dse-faq.elektronik-kompendium.de/dse-faq.htm
Max M. schrieb: > Existiert ein algorithmus um möglichst effizient einen unsigned int (32 > bit) in seine 10er stellen aufzuschlüsseln? Mir fällt da "shiftadd3" und "double dabble" ein. Die nötigen Multiplikationen werden da durch Shifts erledigt.
Worum geht es hier eigentlich genau? Ich meine, ich habe 10 Zehen, die funktionieren auch noch ganz gut obwohl das früher wohl noch viel besser ging. https://dl.acm.org/doi/pdf/10.1145/258726.258836 32 Bit haben üblicherweise 8 Hexstellen, und da kann man die einzelnen Fs oder was immer, einfach logisch bearbeiten.
Rbx schrieb: > Worum geht es hier eigentlich genau? Umwandlung von 32 bit unsigned int zu ASCII. (Das grundlegende Problem ist die Umwandlung 2er Kompl. zu 10er komplement). Dies möglichst ohne division oder mudulo. Selbst Multiplikationen sind zeitintensiv - da all diese operationen von der CPU nicht nativ unterstüzt.
Rbx schrieb: > 32 Bit haben üblicherweise 8 Hexstellen Aber weil der TO keine Hex-Zahlen will, sondern Dezimalzahlen, ist der größte mit 32 Bit darstellbare Wert eben 4294967296 und das sind 10 Dezimalstellen. Max M. schrieb: > fpga_eth ... > Mein softcore Wenn du da ein FPGA hast und einen Softcore, dann kannst du das doch einfach gleich in Hardware machen und als "Funktionsbaustein" verwenden: - http://www.lothar-miller.de/s9y/archives/34-Vektor-nach-BCD.html - http://www.lothar-miller.de/s9y/archives/84-Binaer-nach-BCD-mit-1-Takt-pro-Stelle.html Oder für die ganz harten im Garten eine Monsterkombinatorik: - http://www.lothar-miller.de/s9y/archives/67-Vektor-nach-BCD-kombinatorisch.html
:
Bearbeitet durch Moderator
Max M. schrieb: > Existiert ein algorithmus um möglichst effizient einen unsigned int (32 > bit) in seine 10er stellen aufzuschlüsseln? Also mit weniger als 18 > mul/div/mod operationen. Warum sollte man sowas verrückte tun? Das menschliche Auge ist mit seiner Ablesegeschwindigkeit selbst einem kleinen PIC12 hoffnungslos unterlegen.
Max M. schrieb: > Hat wer einen C-Code für unsigned int 32b to ASCII? Wenn du ein wenig, nur ein klitzekleines Stück selber was machen würdest, dann wäre das ein Ansatz: - https://www.google.com/search?q=double+dabble+c+code Schon den ersten Treffer musst du nur von 16 Bit auf 32 Bit "aufbohren": - https://github.com/ankurpawar/C_code/blob/master/doubleDabble.c Und auch beim 2. kann man die Idee dahinter klar erkennen: - https://gist.github.com/shannietron/04d6b655772301103f0a1012ba48b17a Ich bin mir sicher, dass du mit ein wenig Nachdenken herausfindest, wie man das auf 32 Bit erweitern kann. Und herauszufinden, wie man dann von BCD nach ASCII kommt, sollte auch für einen Anfänger keine Viertelstunde dauern.
:
Bearbeitet durch Moderator
Peter D. schrieb: > Warum sollte man sowas verrückte tun? Weil ich das in der ISR mache und diese kurz halten möchte. Lothar M. schrieb: > Wenn du da ein FPGA hast und einen Softcore, dann kannst du das doch > einfach gleich in Hardware machen und als "Funktionsbaustein" verwenden: Ja wäre eine Möglichkeit, oder einfach nur die performantere Ausführung des Softcores auswählen. Also giebt etliche Workaround Möglichkeiten. Aber da dieses vermutlich Jahrzehnte alte Problem schon längst in C gelöst zu schein scheint: "double dabble" - benötige ich eig nur kurz eine C implementierung dieser Funktion und das Thema kann geschlossen werden.
Max M. schrieb: > Peter D. schrieb: >> Warum sollte man sowas verrückte tun? > Weil ich das in der ISR mache Ich habe mit hoher Wahrscheinlichkeit einen Programmfehler gefunden.
Lothar M. schrieb: > Max M. schrieb: >> Peter D. schrieb: >>> Warum sollte man sowas verrückte tun? >> Weil ich das in der ISR mache > Ich habe mit hoher Wahrscheinlichkeit einen Programmfehler gefunden. Ja müsste nicht zwingend in der ISR sien... Hat wer nun eine Double dabble basierende uint 2 ascii funktion in C?
Max M. schrieb: > Weil ich das in der ISR mache und diese kurz halten möchte. Das habe ich noch nie benötigt. Typisch macht man Ausgaben nur 2..5 mal je Sekunde, um eine ergonomische Darstellung zu bewirken. Öfter läßt die Anzeige unangenehm flackern und behindert die Ablesbarkeit. Sich ständig ändernde Werte können dann unlesbar werden ("88888888"). Max M. schrieb: > Aber da dieses vermutlich Jahrzehnte alte Problem schon längst in C > gelöst zu schein scheint Der erfahrene C-Progger nimmt dafür itoa, sprintf usw.. Sich selber was basteln macht man nur als Programmieranfänger. Hier mal was aus meinen Anfängen:
1 | u8 valout( s16 val ) // decimal output -999 ... 9999 |
2 | {
|
3 | u8 i; |
4 | |
5 | if ( val > 9999 || val < -1999 ) |
6 | {
|
7 | write_digit( DIG3, BLANK ); |
8 | write_digit( DIG2, BLANK ); |
9 | write_digit( DIG1, BLANK ); |
10 | write_digit( DIG0, BLANK ); |
11 | return 1; |
12 | }
|
13 | |
14 | i = 0; |
15 | if ( val & 0x8000 ) |
16 | {
|
17 | val = -val; |
18 | i = MINUS; // minus sign |
19 | }
|
20 | while ( val >= 1000 ) |
21 | {
|
22 | val -= 1000; |
23 | i++; |
24 | }
|
25 | write_digit( DIG3, i ); |
26 | |
27 | i = 0; |
28 | while ( val >= 100 ) |
29 | {
|
30 | val -= 100; |
31 | i++; |
32 | }
|
33 | write_digit( DIG2, i ); |
34 | |
35 | i = 0; |
36 | while ( val >= 10 ) |
37 | {
|
38 | val -= 10; |
39 | i++; |
40 | }
|
41 | write_digit( DIG1, i ); |
42 | write_digit( DIG0, val ); |
43 | |
44 | return 0; |
45 | }
|
Max M. schrieb: > Lothar M. schrieb: >> Max M. schrieb: >>> Weil ich das in der ISR mache >> Ich habe mit hoher Wahrscheinlichkeit einen Programmfehler gefunden. > > Ja müsste nicht zwingend in der ISR sien... > > Hat wer nun eine Double dabble basierende uint 2 ascii funktion in C? Jemand soll Dir 5 Zeilen Code anpassen, damit Du den Programmfehler beibehalten kannst?
Jörg schrieb: > Reicht das auch? > Beitrag "bin2bcd & bcd2bin, 8-6-4 digits, double dabble algorithm" Perfekt danke! Peter D. schrieb: > Der erfahrene C-Progger nimmt dafür itoa, sprintf usw.. Sich selber was > basteln macht man nur als Programmieranfänger. Ach so! Int2Ascii ohne mul/div/mod zum Anfang ist ein guter Einstieg. Auch wesentlich einfacher zu programieren als sprintf oder itoa zu nutzen. Um sprintf oder itoa zu nutzen muss man natürlich schon ein erfahrener C-Progger sein. Und wer itoa oder sprintf nutzt ohne die eigenschaften der CPU zu kennen - macht auch gar nix falsch... Bruno V. schrieb: > Max M. schrieb: >> Lothar M. schrieb: >>> Max M. schrieb: >>>> Weil ich das in der ISR mache >>> Ich habe mit hoher Wahrscheinlichkeit einen Programmfehler gefunden. >> >> Ja müsste nicht zwingend in der ISR sien... >> >> Hat wer nun eine Double dabble basierende uint 2 ascii funktion in C? > > Jemand soll Dir 5 Zeilen Code anpassen, damit Du den Programmfehler > beibehalten kannst? Man möge euch für das finden des Fehlers in Ehren halten. Dank des algorithmuses kann dies nun problemlos in der ISR bleiben.
:
Bearbeitet durch User
Max M. schrieb: > Um sprintf oder itoa zu nutzen muss man natürlich schon ein > erfahrener C-Progger sein. Ja, es braucht schon etwas Zeit, um sprintf lieben zu lernen. Aber die mächtigen Formatierungsoptionen entschädigen einen dafür. Ich möchte es nicht mehr missen. Dann muß man nicht für jede Sonderlocke hunderte Spezialfunktionen definieren.
Bitte 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.