ITOA ohne Division/Modulo

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).

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.

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.

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.

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:
> 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.

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.

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, ...

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.