schnelle dezimale Division auf AVR & Co.

[Karl F. (kafido)]

Hallo Leute,

ich hab schon Einiges zum Thema 'schnelle 10er Divisionen auf 8-Bit uCs' 
gelesen (und ausprobiert) und bin zu dem Schluss gekommen, dass die 
Bit-Schieberei nicht unbedingt das NonPlusUltra ist ...
Funktionen wie die hier (http://www.cs.uiowa.edu/~jones/bcd/divide.html) 
beschriebenen sind z.T. langsamer als meine eigenen Testroutinen ...
Ich gehe davon aus dass das daran liegt, dass einige neuere AVRs 
Hardware-Multiplikation beherrschen und somit ein MUL x16 u.U. schneller 
geht als ein <<= 4.
Besonders expensive scheinen Dinge wie "val >>= 14" zu sein. Ein "val 
>>= 8" gefolgt von einem "val >>= 6" ist günstiger. Noch besser ist ein 
"val <<= 2" und danach das höherwertige word verwenden, wenn das dabei 
nicht überläuft ...
Und wenn man mehr als 3 Bits nach links schieben will, ist ein 
MULx8(16,32,64,...) häufig auch günstiger ...

Ich hab grad eine div100000 gebraucht, bei der der Quotient nicht größer 
als 16bit zu werden braucht und bin im Moment an diesem Punkt:

typedef union {
  uint32_t l;
  struct {
    uint16_t w0;
    uint16_t w1;
  };
  struct {
    uint8_t b0;
    uint8_t b1;
    uint8_t b2;
    uint8_t b3;
  };
} u32;

uint16_t div10000 ( uint32_t val ) {
  uint16_t q;
  u32 v, r;
  v.l = val;

  q = v.w1 * 6;
  q += (q >> 4);
  r.l = v.l - (q * 10000L);

  if (r.w1 > 32) {
    r.w1 *= 6;
    q += r.w1;
    r.l = v.l - (q * 10000L);
  }
  r.l *= 1677;
  q += r.b3;
  r.l = v.l - (q * 10000L);

  if (r.w0 >= 10000) {
    r.w0 -= 10000;
    q++;
  }
  return q;
}

Bevor ich jetzt aber weiter optimiere und teste frage ich mich, ob das 
nicht schon jemand vor mir getan hat?
Gesucht sind also (C-) Funktionen, die schnellstmöglich durch 
10/100/1000/10000 teilen ...

Ideas welcome ...

- Karl

[Klaus D. (kolisson)]

Ich mach dir mal einen "BIG SMILEY",
weil wir immer nur dur 2 , 4, 8, 16 teilen.
Das liegt aber daran, dass man sich irgenwann vom 10er System getrennt
hat. Es gibt leider keinen Grund durch 10 oder 100 zu teilen.

Gruss k.

[Purzel H. (hacky)]

Ja. Ist 8192 zu ungenau ? Dann koennte man mit einer Stelle mehr durch 
10240=(2048+8192) Teilen, da waere der Fehler nur noch 2.4%

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Karl F. schrieb:
> Gesucht sind also (C-) Funktionen, die schnellstmöglich durch
> 10/100/1000/10000 teilen ...
Das ist blöd, denn kein uC kann C. Die sprechen alle ihre eigene 
Sprache. Und wenn einer einen Barrel-Shifter hat, dass ist jeder 
x-beliebige Shift immmer mindestens gleich schnell wie eine 
Multiplikation, meist schneller. Also ist die Frage nach DER 
universellen schnellen C-Routine sinnlos.

[Joachim (Gast)]

Moin,

ich kenne zwar auch keine extra C-Funktionen, die dir das Dividieren 
abnehmen, aber man kann fast jede Division so umstricken, daß es auf ein 
Shift hinausläuft. Wenn du "x/10" (bzw. "x * 0,1") machen willst, dann 
kannst du auch "(x * 205) >> 11". Denn "205 / 2048" entspricht ziehmlich 
genau 0,1.
Beispiel für "x / 100": "(x * 41) >> 12"

Bei den ganz großen Zahlen (z.B. 10000) könntest du erstmal durch 8192 
teilen, dann geschickt multiplizieren, daß du anschließend 
rundungsfehlerarm durch 1,221 teilen kannst (10000 / 8192). Sieht zwar 
komisch aus, aber das ist wirklich unglaublich schnell.

Am besten natürlich, du bewegst dich gleich im oktalen Zahlensystem :) . 
Es gibt z.B. auch keinen Grund LUTs auf 0-1000 zu skalieren. 0-1024 ist 
da schon sinnvoller.

/Mach dich frei von der 10!/ ;)

Gruß

[Noah (Gast)]

wenn man 4 mal nach links (oder rechts) schieben will, kann man da mit 
SWP (tauscht unteres und oberes nibble) ziemlich gut abkürzen.

[Noah (Gast)]

Oder man nimmt BCD... Da ist das teilen durch 10 dann auch in hardware 
einfach.  ;-)

[ich (Gast)]

>Oder man nimmt BCD
Da verschiebt man die Probleme auf die BCD-Dezimalwandlung :-)

[Noah (Gast)]

ich schrieb:
> Da verschiebt man die Probleme auf die BCD-Dezimalwandlung :-)

Du meinst sicher BCD <-> Binär. Allerdings kann man ja ALLES in BCD 
machen. Der AVR hat zumindest schonmal ein Half-Carry-Flag. Da ist das 
Addieren kein Problem. Auch Multiplizieren sollte klappen. Wenn man 
jedoch einen großen AVR nimmt, der MUL kann, dann ist das allerdings 
wieder deutlich schneller, aber geht sicher nur binär. War eigentlich 
auch nur ein Scherz mit dem BCD, aber manchmal kommt man damit wirklich 
aus.

[Karl F. (kafido)]

Hallo Leute,

danke für die Antworten - leider helfen mir die meisten nicht weiter.
Dass man das 10er System vermeidet wo möglich, versteht sich von selbst.
Manchmal geht das halt nicht, z.B. wenn man mit der Umwelt kommunizieren 
muss (Werte auf's LCD oder über die serielle Schnittstelle usw.)

Und selbst reinrassige µC Hardware wie ein DS1307 (der ist mit seinem 
I²C Interface bestimmt nicht dafür konstrutiert um via 74HC247 direkt 
auf irgendwelche 7-Segment-Anzeigen zu gehen) speichern Daten im BCD 
Format statt binär - ich hab schon vor 30 Jahren auf'm PC/AT nicht 
verstanden, warum ... ein einfacher 32bit-Zähler (unixtime) hätte es 
doch auch getan ...

Naja, da sich das Teilen durch 10er-Potenzen nunmal nicht völlig 
vermeiden läßt und ich es manchmal sogar in einer Interruptroutine 
machen muss, suche ich nach schnellen Methoden.

@Jochen: wenn Du Dir mein Code-Beispiel oben angeschaut hättest,
dann hättest Du sicher gesehen, dass ich genau das bereits tue:
*6/65536 bzw. *1677/16777216
(hatte auch schon *13/131072 und *107374/1073741824 drin)
Die hier gezeigte Routine ist auch durchschnittlich um Faktor 3-4 
schneller als das was der C-Compiler produziert, wenn man y = x / 10000 
hinschreibt.

Die C-Funktionen bzw. Lösungsansätze von Jones die ich angesprochen 
hatte sind sicher nicht übel, besonders dann, WENN die CPU einen 
Barrelshifter hat. Meines Wissens hat der AVR aber keinen, dafür können 
die neueren/größeren aber immerhin in 2 Clock Cycles multiplizieren ...
Und mit Hilfe der Multiplikation geht das schneller als mit dem ewigen 
Bit-Shift.

Wenn keiner eine Lösung parat (oder irgendwo mal gefunden) hat - fein.
Dann muss ich halt selber weiter basteln. Aber bitte versucht nicht, mir 
das auszureden ...

Evtl. werd ich's irgendwann in Assembler realisieren, wenn's mir in C zu 
blöd wird, aber auf die Schnelle muss das erstmal bestmöglich in C 
gehen.

Gruß
- Karl

[J.-u. G. (juwe)]

Karl F. schrieb:
> Aber bitte versucht nicht, mir
> das auszureden ...

Will ich auch nicht. Mach nur.

Allerdings werden die von Dir genannten Beispiele:

> Werte auf's LCD oder über die serielle Schnittstelle usw.

üblicherweise nicht in Interruptroutinen behandelt und auf das 
Herauskitzeln der letzten µs kommt es dabei eigentlich auch nicht an.

[Arc N. (arc)]

Karl F. schrieb:
> Wenn keiner eine Lösung parat (oder irgendwo mal gefunden) hat - fein.
> Dann muss ich halt selber weiter basteln. Aber bitte versucht nicht, mir
> das auszureden ...

http://spiral.ece.cmu.edu/mcm/gen.html

J.-u. G. schrieb:
> Allerdings werden die von Dir genannten Beispiele:
>
>> Werte auf's LCD oder über die serielle Schnittstelle usw.
> üblicherweise nicht in Interruptroutinen behandelt und auf das
> Herauskitzeln der letzten µs kommt es dabei eigentlich auch nicht an.

Richtig.
Letztlich kommt's nur auf den Empfänger an: Kann dieser die Werte 
"besser" umrechnen oder müssen ihm "passende" Werte vorgesetzt werden.

@Karl
Einen "passenderen" Controller könnte man auch verwenden...

[Klaus (Gast)]

J.-u. G. schrieb:
> üblicherweise nicht in Interruptroutinen behandelt und auf das
> Herauskitzeln der letzten µs kommt es dabei eigentlich auch nicht an.

Na sag mal, willst du auf dem LCD µs alte Werte lesen ? ;-)

MfG Klaus

[J.-u. G. (juwe)]

Klaus schrieb:
> Na sag mal, willst du auf dem LCD µs alte Werte lesen ? ;-)

Nein, warum fragst Du?

[Detlef _. (detlef_a)]

Karl, keiner will Dir was ausreden. Jeder darf so programmieren, wie er 
oder der Chef das für richtig halten. Wenn Du schnell durch 10 teilen 
mußst machst Du aber wahrscheinlich was falsch.

Schnelle C-Routinen zum Teilen durch Konstanten sind hier angegeben.
http://www.hackersdelight.org/divcMore.pdf

Cheers
Detlef

[Karl F. (kafido)]

Hallo Detlef,

danke, die Routinen von Hackersdelight kenne ich auch schon ...

Das Dumme ist, dass der AVR-GCC Dinge wie 't >>= 15' höchst ineffizient 
zu übersetzen scheint, besonders wenn es sich um 32bit-Werte handelt.
Ich hab mir den resultierenden Assembler-Code noch nicht angesehen, aber 
Laufzeiten gemessen ...
Es sieht so aus als macht er wirklich 15 shifts über alle vier Bytes.

Macht man dagegen ein (t >>= 8) gefolgt von einem (t >>= 7) sieht es 
schon besser aus - da scheint er wohl wirklich ganze Bytes zu shiften.
(t.b0 = t.b1, t.b1 = t.b2, t.b2 = t.b3, t >>= 7)

Noch schneller geht in diesem Fall ein 't >>= 16' gefolgt von 't <<= 1' 
mit nachträglicher Korrektur des entstandenen Fehlers ... seufz

Am schnellsten geht's, wenn man den Kram über eine Union addressiert und 
so statt 't >>= 16' gleich einfach nur das obere 16-bit Wort nimmt.

Nachdem ich das soweit herausgefunden hatte, dachte (hoffte) ich halt, 
dass da auch schon jemand vor mir drauf gekommen ist und es evtl. schon 
eine fertige Lösung (auf AVR zugeschneidert) gibt ...

Letzendlich werd ich wohl wirklich die divu10/100/1000/10000 in 
Assembler schreiben müssen, dann ist gut.

Ach, dass ich was falsch (bzw. zumindest nicht optimal) mache kann sehr 
wohl sein - ich bin ja schließlich gerade dabei, Code zu optimieren.
Dabei ist mir in diesem Fall die resultierende Größe relativ egal, es 
geht um Laufzeit. Wenn der gesamte Code dadurch ein Kilobyte größer 
wird, stört mich das erstmal nicht ...

Gruß
- Karl

[Karl H. (kbuchegg)]

Karl F. schrieb:

> Nachdem ich das soweit herausgefunden hatte, dachte (hoffte) ich halt,
> dass da auch schon jemand vor mir drauf gekommen ist und es evtl. schon
> eine fertige Lösung (auf AVR zugeschneidert) gibt ...


Der springende Punkt ist, dass sowas im Regelfall keinen Menschen 
wirklich stört. Wenn dein Timing so knapp ist, dass es auf die paar 
Shifts ankommt, dann geht man sowieso auf Assembler. Und ob ein AVR in 
der Hauptschleife jetzt ein paar Takte mehr rumtrödelt oder nicht, ist 
meistens völlig egal.

Viele die auf dieser Ebene meinen, die Welt retten zu können, haben oft 
ganz andere Probleme. Und das beginnt sehr oft bei ungeschicktem 
Programmaufbau.


Wobei man sagen muss: die 32-Bit Arithmetik ist anscheinend wirklich 
nicht des GCC große Stärke. Die Klage hat man schon öfter gehört. Aber 
noch ist der Leidensdruck anscheinend nicht groß genug, dass sich jemand 
erbarmt.

[Peter D. (peda)]

J.-u. G. schrieb:
>> Werte auf's LCD oder über die serielle Schnittstelle usw.
>
> üblicherweise nicht in Interruptroutinen behandelt und auf das
> Herauskitzeln der letzten µs kommt es dabei eigentlich auch nicht an.

Kann ich nur zustimmen.
Ich hatte noch nie das Problem, schnell /10 zu rechnen. Jede Ausgabe für 
den Menschen ist über 1000 mal schneller, als er ablesen kann.
Und CPU-Intern ist dezimal kein Thema, da geht alles binär viel besser.

Ich hab spaßeshalber mal ne eigene Dezimalausgabe probiert. Am 
schnellsten geht da die Subtraktionsmethode:

http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&p=525463#525463


Peter

[Anja (Gast)]

Karl F. schrieb:
> Letzendlich werd ich wohl wirklich die divu10/100/1000/10000 in
> Assembler schreiben müssen, dann ist gut.

Warum multiplizierst Du nicht einfach mit 0.1?  = 0x199A
Ich skaliere bei Ausgaben ans LCD normalerweise so daß das 
höchstwertigste Nibble die höchstwertigste Dezimalstelle ergibt. Danach 
brauche ich lediglich immer mit 10 multiplizieren um die nächste Stelle 
ins höchstwertigste Nibble zu kriegen.

Gruß Anja

[Karl F. (kafido)]

Anja schrieb:
> Karl F. schrieb:
>> Letzendlich werd ich wohl wirklich die divu10/100/1000/10000 in
>> Assembler schreiben müssen, dann ist gut.
>
> Warum multiplizierst Du nicht einfach mit 0.1?  = 0x199A

tu ich ja ...


> Ich skaliere bei Ausgaben ans LCD normalerweise so daß das
> höchstwertigste Nibble die höchstwertigste Dezimalstelle ergibt. Danach
> brauche ich lediglich immer mit 10 multiplizieren um die nächste Stelle
> ins höchstwertigste Nibble zu kriegen.

das klingt interessant - aber auf Anhieb klappt das nicht.
Ich steh wohl irgendwie grad auf'm Schlauch.
Kannst Du mal ein paar Zeilen (pseudo?) Code posten?

Gruß
- Karl

[Anja (Gast)]

Karl F. schrieb:
> Kannst Du mal ein paar Zeilen (pseudo?) Code posten?

Also folgendes Beispiel:
Eingangsspannung am ADC 1.235V
Referenzspannung 5.070V (Kalibrierwert aus EEPROM = 0x511F s.u.).
Gemessener Wert = 1.235/5.07 * 65536 (linksbündig gemessen)
                = 0x3E40 bei 10 Bit ADC.

Skalierung auf höchstwertigstes Nibble: 5.07 * 65536 / 16 = 0x511F

-> Meßwert * 0x511F (32-Bit-Ergebnis) = 0x13B9C9C0
-> 1. Anzeigeziffer = 1
-> 0x03B9C9C0 * 0xA = 2541E180
-> 2. Anzeigeziffer = 2
-> 0x0541E180 * 0xA = 3492CF00
-> 3. Anzeigeziffer = 3
-> 0x0492CF00 * 0xA = 2DBC1600
-> 4. Anzeigeziffer = 2  (oder 3 gerundet)

die 4. Stelle ist natürlich wegen der 10 Bit ADC-Auflösung "gelogen".

Bei 10-Bit ADC reicht auch im normalfall wenn man nur die 
höchstwertigsten 16 Bit (ggf. gerundet) von der 32-Bit Multiplikation 
weiterverwendet.

Die Multiplikation * 10 kann natürlich auch durch
Wert = (Wert << 1)
und Wert = Wert + (Wert << 2) bei Prozessoren ohne Multiplikationsbefehl
durchgeführt werden.

Gruß Anja

[Karl F. (kafido)]

Hallo Anja,

danke für das Beispiel!
Ich muß gestehen, ich hab noch nicht ganz verstanden, warum es 
funktioniert, aber es geht - zumindest wenn man nur 3 relevante Stellen 
hat (ADC-Wert) dort tut auch ein evtl. Anzeigefehler von +- ein paar 
Digits nicht weh.

Wenn ich aber eine beliebige Zahl (z.B. 12345 0x3039) exakt auf's 
Display kriegen will, klappt das mit der Methode nicht (oder bin ich nur 
zu doof?)
Ich vermute, dass durch die Multiplikation mit dem 16-Bit Korrekturwert 
sich ab der 3. oder 4. Dezimalstelle Fehler einschleichen ...

Bevor ich mir da weiter die Hirnwindungen zermalme:
Sagst Du, mit dieser Methode könnte man alle 16-Bit Werte von 0-65535 
korrekt auf's Display bringen? Oder nur 'ungefähr'?
Letzteres ist für meinen Anwendungsfall nicht zu gebrauchen.
Ich muß in der Lage sein, Werte genau anzuzeigen - vgl. sprintf("%5u", 
w) bzw. manchmal brauche ich auch bis zu 8 Stellen sprintf("%8lu", w)
Damit kommen wir etwas weg von der reinen Dezimalteilung hin zu einer 
schnellen itoa() Funktion - dort verwende ich z.Zt. modifizierte 
Routinen von jones (s. Anfangspost) ...

Naja, wie auch immer ... was ich suche, scheint es nicht zu geben.
Ich kann mich erinnern, dass manche anderen Compiler besser optimieren 
und sogar selbstständig Dinge wie 'a *= 2' in 'a <<= 1' übersetzen, je 
nach dem, was die jeweilige CPU besser kann - aber solche Optimierungen 
scheint der AVR-GCC nicht zu machen. Also bleibt für die optimale Lösung 
wohl wirklich nur ein paar Assembler-Routinen ...
... da werd ich mich bei Gelegenheit mal dran machen ...

Gruß
- Karl

[Anja (Gast)]

Karl F. schrieb:
> Ich vermute, dass durch die Multiplikation mit dem 16-Bit Korrekturwert
> sich ab der 3. oder 4. Dezimalstelle Fehler einschleichen ...

Hallo,

im verwendeten Beispiel ist die Arithmetik auf etwa 12 Bits genau. (Ein 
Nibble geht ja für die Formatierung verloren). Für den 10-Bit Wert eines 
ADCs reichts. Ansonsten hat natürlich der Skalierungsfaktor einen 
Rundungsfehler den man durch höhere Auflösung (32 oder 64 Bit) zwar 
verkleinern kann, der aber nie = 0 wird.

Wenn Du exakte Werte brauchst fährst du wahrscheinlich durch Subtraktion 
von festen Werten 10000, 1000, 100, 10 und zählen besser als durch eine 
Multiplikation.

Gruß Anja

[Karl F. (kafido)]

Ich verwende - wie gesagt - eine von mir modifizierte Routine nach der 
Idee von Jones ...
Sieht derzeit so aus:

typedef union {
  uint16_t w;
  struct {
    uint8_t b0;
    uint8_t b1;
  };
} uint16_u;

void uitoa( uint16_u n, char *buf ) {
  uint8_t d3, d2, d1, d0;
  uint16_t t;
  uint16_u h;

  d0 = n.b0;
  d1 = d0 >> 4;
  d0 &= 0xF;
  d2 = n.b1;
  d3 = d2 >> 4;
  d2 &= 0xF;

  t = 6 * (d3 + d2 + d1) + d0;
  h.w = t * 0xCD;
  h.b1 >>= 3;
  d0 = t - 10 * h.b1;

  d1 += h.b1 + 9*d3 + 5*d2;
  h.w = d1 * 0xCD;
  h.b1 >>= 3;
  d1 -= 10 * h.b1;

  d2 <<= 1;
  d2 += h.b1;
  h.w = d2 * 0x1A;
  d2 -= 10 * h.b1;

  d3 = h.b1 + 4*d3;
  h.w = d3 * 0x1A;
  d3 -= 10 * h.b1;

  *buf++ = h.b1 + '0';
  *buf++ = d3 + '0';
  *buf++ = d2 + '0';
  *buf++ = d1 + '0';
  *buf++ = d0 + '0';
  *buf=0;
}

Damit hab ich bisher die besten Ergebnisse, wobei das sicher noch zu 
verbessern geht ...

Gruß
- Karl

[willi (Gast)]

Karl F. schrieb:
> Damit hab ich bisher die besten Ergebnisse, wobei das sicher noch zu
> verbessern geht ...

Wozu die ganze Würgerei mit einem 8-Bitter?
Nimm irgendeinen 32-Bitter (ARM7, PIC32, ...) und die Bitschuppserei hat 
ein Ende.

[Karl F. (kafido)]

willi schrieb:
> Wozu die ganze Würgerei mit einem 8-Bitter?
> Nimm irgendeinen 32-Bitter (ARM7, PIC32, ...)

Ganz Einfach: Weil ich bei Bastelprojekten lieber mit CPU's arbeite, die 
im DIL-Gehäuse verfügbar sind und die ich bei Bedarf auch mal auf ein 
Breadboard stecken kann bzw. auf eine Lochrasterplatine löten.
Die meisten meiner uC-Projekte sind Einzelstücke, für die sich die 
Entwicklung einer aufwändigen Platine nicht lohnt. Das Zeugs wird 
entweder auf Lochraster aufgebaut oder es gibt eine einfache einseitige 
Platine und gut ist.

Zeig mir ne 32bit CPU, die diese Kriterien erfüllt und ich überleg mir 
das nochmal ...

Irgendwie gibt es in allen Foren das gleiche Problem:
Es finden sich immer Haufenweise Leute die einem das ausreden wollen, 
was man machen möchte und nur wenige, die einem helfen ...

Ich nenne das immer das Ikea-Phänomen:
"Gefällt Dir die gelbe Tasche? Dann nimm' doch eine Blaue."

- Karl

[Matthias L. (Gast)]

>> Ich skaliere bei Ausgaben ans LCD normalerweise so daß das
>> höchstwertigste Nibble die höchstwertigste Dezimalstelle ergibt. >Danach
>> brauche ich lediglich immer mit 10 multiplizieren um die nächste Stelle
>> ins höchstwertigste Nibble zu kriegen.

>das klingt interessant - aber auf Anhieb klappt das nicht.
>Ich steh wohl irgendwie grad auf'm Schlauch.
>Kannst Du mal ein paar Zeilen (pseudo?) Code posten?



Beitrag "Re: Problem mit ADC an mega128"
Beitrag "Re: Problem mit ADC an mega128"

[Karl H. (kbuchegg)]

Karl F. schrieb:


> Irgendwie gibt es in allen Foren das gleiche Problem:
> Es finden sich immer Haufenweise Leute die einem das ausreden wollen,
> was man machen möchte und nur wenige, die einem helfen ...

Weil du dir selber das Leben schwer machst.
Zeig ein konkretes Projekt, sag wo du Zeitprobleme hast und die Sache 
sieht anders aus.

Aber aufs Geratewohl eine Division durch 10 um ein paar Prozent zu 
beschleunigen, die dann eh keiner braucht, weil die LCD Ausgabe auch so 
immer noch schnell genug ist und künstlich runtergebremst werden muss, 
ist nicht sinnvoll.

[Peter D. (peda)]

Karl F. schrieb:
> Es finden sich immer Haufenweise Leute die einem das ausreden wollen,

Die meisten sehen einfach keinen Sinn darin, in etwas Aufwand zu 
stecken, der sich nirgends bemerkbar macht.
Der Flaschenhals ist nicht die Dezimalfunktion des Compilers, sondern 
der langsame Mensch.

Ich mache absichtlich in meine Programme Delays rein, damit neue Werte 
nicht schneller als alle 200ms dargestellt werden.
2 .. 5 Anzeigen/s werden als ergonomisch empfunden, darum machen das 
auch die meisten Meßgeräte so.

Ich geb zu, als Anfänger habe ich auch so schnell angezeigt, wie der ADC 
hergeben konnte. Das gibt dann die bekannten flimmernden 88888 zu sehen. 
Der Mensch kann dann die Werte nicht mehr unterscheiden.


Peter

[Abdul K. (ehydra)]

Karl F. schrieb:

> Zeig mir ne 32bit CPU, die diese Kriterien erfüllt und ich überleg mir
> das nochmal ...
>

Ließ mir doch keine Ruhe ;-) Die einzige <aktuelle> die ich kenne, ist 
der Propeller von Parallax: DIP40 und wirklich auch 32Bit.
Ansonsten helfen aber Adapter auch ganz gut.


> Irgendwie gibt es in allen Foren das gleiche Problem:
> Es finden sich immer Haufenweise Leute die einem das ausreden wollen,
> was man machen möchte und nur wenige, die einem helfen ...
>
> Ich nenne das immer das Ikea-Phänomen:
> "Gefällt Dir die gelbe Tasche? Dann nimm' doch eine Blaue."

Da ist was dran.

[Johann L. (gjlayde)]

Schmerzfrei und ohne Divisionseinheit durch 10 zu teilen geht für eine 
8-Bit Zahl so:

uint8_t div10 (uint8_t a)
{
   a = (205 * a) >> 8;
   return a >> 3;
}

und so sieht auch der Code aus, den avr-gcc 4.7 dafür erzeugt, wenn man 
a / 10 hinschreibt (übrigens auch für viele andere Divisionen mit 
konstantem Divisor).

Ganz analog geht's für eine 16-Bit Zahl, wobei die Konstante zur 
Multiplikation dann 52429 ist. Aber selbst diese Kapriolen brauch man in 
neuen Compilerversionen wie gesagt nicht mehr zu machen weil avr-gcc sie 
beherrscht.

[Karl F. (kafido)]

Peter Dannegger schrieb:
> Ich mache absichtlich in meine Programme Delays rein, damit neue Werte
> nicht schneller als alle 200ms dargestellt werden.
> 2 .. 5 Anzeigen/s werden als ergonomisch empfunden, darum machen das
> auch die meisten Meßgeräte so.

Hallo Peter,

das ist ja klar, das mach ich auch (fast) so ...
Aber die CPU hat in meinem Anwendungsfall ziemlich viel zu tun, so dass 
ich schon die verschiedensten Verrenkungen mache um unnötige delay()s zu 
sparen.
Beispiel: auf den ADC muss man üblicherweise warten, es sei denn, man 
läßt ihn einen Interrupt auslösen ...
Auf das Interface des LCD muss man auch warten (das HD44780-Datenblatt 
sagt: 40us nach jedem Nibble bzw. Byte (4Bit/8Bit))
Ich muss die Daten nicht schneller ausgeben, aber ich will nicht die 
CPU-Zeit mit warten verbringen, also hab ich die LCD-Ausgabe in eine 
Interrupt-Routine gelegt, die sowieso ~1000x pro Sekunde aufgerufen 
wird.
Auszugebender Text wird in einen Puffer geschrieben und die ISR schreibt 
ganz nebenbei jede ms ein Byte raus - somit hat das Display sogar fast 
1000us zwischen zwei Bytes, aber ich muß nicht auf's Display warten.
Genauso mache ich es mit dem ADC - ich starte ihn am Ende dieser ISR und 
am Anfang der nächsten Runde lese ich das Ergebnis. Ziel dieser 
Programmierung ist, nur einen zentralen Wartepunkt im Programm zu haben, 
dann, wenn wirklich nichts anderes zu tun ist. Auf diese Art und Weise 
hab ich mein Timing am besten im Griff ... und ich kann am ehesten 
beurteilen, wieviel Zeitreserven ich noch frei habe für zusätzliche 
Aufgaben ...

Und:
Teilen durch 10 bzw. multiplizieren mit 10 muss ich halt immer mal 
wieder an verschiedenen Stellen. So hab ich z.B. einen Drehencoder (mit 
Beschleunigung) für eine Eingabefunktion vorgesehen. Da aber hier nicht 
ein (Maus-)Cursor bewegt wird, sondern Zahlenwerte eingestellt werden, 
habe ich es als angenehmer empfunden, wenn die Beschleunigung nicht 
binär arbeitet, sondern in 10er Schritten: Dreht man langsam, ändert 
sich die einer-Stelle, dreht man schneller, springt der Cursor auf die 
10er Stelle und man ändert diese usw. - dadurch ändert sich immer nur 
eine Ziffer, das gibt ein deutlich ruhigeres Bild als wenn alle Ziffern 
zappeln - naja, MIR gefällt das so jedenfalls besser ...
Die beiden Phasen des Drehencoders und ein paar Tasten werden natürlich 
in derselben ISR() von oben mit eingelesen und mit Vertikalzählern 
entprellt.

Das nur als ein paar kleine Beispiele ...

Übrigens: auch wenn die Grundregel lautet: ISR immer so kurz wie möglich 
machen, halte ich es in vielen Fällen der regelmäßig wiederkehrenden 
Signalverarbeitung u.U. für sinnvoll, gewisse Aufgaben gleich in der ISR 
zu erledigen - da stehen die Werte noch in den CPU-Registern und die 
Aufgabe kann am schnellsten erledigt werden. Wenn ich die Variablen ans 
Hauptprogramm übergeben muß, dann müssen diese als volatile deklariert 
werden und bei jedem Zugriff aus dem Speicher gelesen/geschrieben werden 
- somit ist wieder jegliche Compileroptimierung beim Teufel ...

Vielleicht liege ich damit ja falsch, aber bisher erscheint mir diese 
Vorgehensweise sinnvoll ...

Allerdings wollte ich (zumindest im Moment) ja gar nicht über diesen 
ganzen Kram diskutieren, sondern ich hab einfach nur nach schnellen 
Routinen für die Dezimaldivision gesucht ...

Unabhängig davon finde ich die Methode von lippy (danke!) sehr 
interessant, allerdings nur wenn es sich um Analogwerte handelt und man 
keine größere Präzision als 10 Bit braucht. 16 Bit und mehr lassen sich 
auf diese Weise wohl nicht sinnvol auf's Display bringen ...

Gruß
- Karl

[Karl F. (kafido)]

Abdul K. schrieb:
>
> der Propeller von Parallax: DIP40 und wirklich auch 32Bit.

Hab mir grad mal ein paar Infos zu dem Teil reingezogen ...
... das ist wirklich nicht übel!

Aber eigentlich mag ich mich nicht mit noch einer CPU rumärgern.
Es hat doch jede CPU so ihre Besonderheiten und es dauert immer eine 
ganze Weile, bis man sich 'zu Hause' fühlt ...
Ich hab - angefangen mit Z80 und 6502 - über 68000, 80x86 mich noch mit 
80xx (8049/8051), 80535 und 6800 rumgeärgert - und seit geraumer Zeit 
mit ATmel ATmega/ATtiny ... irgendwann ist auch mal gut.
Da würden mich dann eher noch die XLINX & Co. interessieren, aber da war 
wieder das Problem mit dem Package ...

Gruß
- Karl

[Karl H. (kbuchegg)]

Karl F. schrieb:

> Beispiel: auf den ADC muss man üblicherweise warten, es sei denn, man
> läßt ihn einen Interrupt auslösen ...

Jep

> Auf das Interface des LCD muss man auch warten (das HD44780-Datenblatt
> sagt: 40us nach jedem Nibble bzw. Byte (4Bit/8Bit))
> Ich muss die Daten nicht schneller ausgeben, aber ich will nicht die
> CPU-Zeit mit warten verbringen, also hab ich die LCD-Ausgabe in eine
> Interrupt-Routine gelegt, die sowieso ~1000x pro Sekunde aufgerufen
> wird.
> Auszugebender Text wird in einen Puffer geschrieben und die ISR schreibt
> ganz nebenbei jede ms ein Byte raus - somit hat das Display sogar fast
> 1000us zwischen zwei Bytes, aber ich muß nicht auf's Display warten.

Jep

> Genauso mache ich es mit dem ADC - ich starte ihn am Ende dieser ISR und
> am Anfang der nächsten Runde lese ich das Ergebnis.

Ich benutz dazu eher selten ISR. Nach dem Auslesen des ADC starte ich 
ihn gleich wieder neu. Nach einer Runde in der Hauptschleife ist der ADC 
dann bereits fertig, ich hol mir das Ergebnis und starte wieder den ADC.

> Ziel dieser
> Programmierung ist, nur einen zentralen Wartepunkt im Programm zu haben,
> dann, wenn wirklich nichts anderes zu tun ist.

Jep. Das ist auch völlig normal und auch richtig so.

> Und:
> Teilen durch 10 bzw. multiplizieren mit 10 muss ich halt immer mal
> wieder an verschiedenen Stellen. So hab ich z.B. einen Drehencoder (mit
> Beschleunigung) für eine Eingabefunktion vorgesehen. Da aber hier nicht
> ein (Maus-)Cursor bewegt wird, sondern Zahlenwerte eingestellt werden,
> habe ich es als angenehmer empfunden, wenn die Beschleunigung nicht
> binär arbeitet, sondern in 10er Schritten:

Ist soweit alles klar.
Aber auch da brauchst du keine Optimierung in der Division. Alles, aber 
auch wirklich alles, an dem ein Mensch beteiligt ist, ist nicht soweit 
zeitkritisch, dass es auf eine Millisekunde mehr oder weniger ankommt. 
Die kann kein Mensch feststellen. Du optimierst dann an etwas rum, was 
nix bringt.

Beim Betreten der Funktion die Zahl durch Division in die einzelnen 
Stellen zerlegen und beim Drehen dann die jeweilige Stelle erhöhen oder 
verringern. Ist der Benutzer fertig, mittels Multiplikationen aus den 
Stellen wieder die endgültige Zahl zusammensetzen. Ist schnell genug und 
schnellr braucht es nicht sein.

> Das nur als ein paar kleine Beispiele ...

... die immer noch keinen Fall aufzeigen, bei dem sich der Aufwand 
lohnt.

>
> Übrigens: auch wenn die Grundregel lautet: ISR immer so kurz wie möglich
> machen, halte ich es in vielen Fällen der regelmäßig wiederkehrenden
> Signalverarbeitung u.U. für sinnvoll, gewisse Aufgaben gleich in der ISR
> zu erledigen

Ist ja auch in Ordnung. Solange das die Bearbeitung einer ISR nicht zu 
lange verzögert, dass andere Interrupts in Gefahr laufen nicht mehr 
rechtzeitig ausgeführt zu werden.

> Wenn ich die Variablen ans
> Hauptprogramm übergeben muß, dann müssen diese als volatile deklariert
> werden und bei jedem Zugriff aus dem Speicher gelesen/geschrieben werden
> - somit ist wieder jegliche Compileroptimierung beim Teufel ...

Auch dagegen kann man mit Hilfsvariablen etwas tun.
>

[Jobst M. (jobstens-de)]

Karl F. schrieb:
> mich noch mit 80xx (8049/8051), 80535 und 6800 rumgeärgert

Ach, wenn Du den 8051 kennst - den gibt es im DIP und er kann teilen in 
4 Takten ;-)
Und es gibt auch schnelle Derivate ...


Und wenn Du ASM-libs für AVR benötigst - die findest Du hier unter 
Technical notes:

http://elm-chan.org/


Gruß

Jobst

[Jobst M. (jobstens-de)]

Karl F. schrieb:
> ... das ist wirklich nicht übel!

Doch. Die Interpretersprache, aus der man sich, selbst wenn man sie 
nicht benutzen möchte, erst mal befreien muß.


Gruß

Jobst

[Peter D. (peda)]

Karl F. schrieb:
> Dreht man langsam, ändert
> sich die einer-Stelle, dreht man schneller, springt der Cursor auf die
> 10er Stelle und man ändert diese usw.

Mache ich ohne Division, ich setze die Schrittweite auf 1, 10, 100 usw.


Karl F. schrieb:
> Übrigens: auch wenn die Grundregel lautet: ISR immer so kurz wie möglich
> machen, halte ich es in vielen Fällen der regelmäßig wiederkehrenden
> Signalverarbeitung u.U. für sinnvoll, gewisse Aufgaben gleich in der ISR
> zu erledigen

Es hängt natürlich von der konkreten Anwendung ab, aber meine Erfahrung 
entspricht der Regel.
Macht man viel im Interrupt, passiert es entweder unnötig schnell oder 
unnötig oft. Es kann sogar passieren, daß sich Interrupts verdrängen. In 
der Mainloop kommt aber jeder mal dran.

Auch hast Du im Interrupt einen größeren Satz an Registern zu retten, 
wenn Du viele Funktionen aufrufst. Und das jedesmal, also nicht nur, 
wenn z.B. eine Funktion alle 1000ms aufgerufen wird.


Karl F. schrieb:
> Wenn ich die Variablen ans
> Hauptprogramm übergeben muß, dann müssen diese als volatile deklariert
> werden und bei jedem Zugriff aus dem Speicher gelesen/geschrieben werden

Da kann man mit einem Macro nur den einen Zugriff im Main als volatile 
casten.

Karl F. schrieb:
> 16 Bit und mehr lassen sich
> auf diese Weise wohl nicht sinnvol auf's Display bringen ...

Die Subtraktionsmethode hast Du Dir angeschaut?

Hier noch ein Beispiel:
Beitrag "Formatierte Zahlenausgabe in C"


Peter

[Karl F. (kafido)]

Karl Heinz Buchegger schrieb:
>
> Ist soweit alles klar.
> Aber auch da brauchst du keine Optimierung in der Division.

Vermutlich hast Du damit Recht ...
... aber man braucht auch keinen 3-Liter V6 Motor im Auto, und trotzdem 
fahren genug davon rum ;-)  (von V8 bis V12 ganz zu schweigen ...)

Aber was spricht denn dagegen, es 'gleich richtig' zu machen? Wenn da
so ein Idiot (ich) sich die Arbeit machen will, dann lass ihn doch!
Ich hatte halt gehofft, dass es vor mir schon einen anderen Idioten 
gegeben hat ;-)

Ich versuche meistens von vorneherein einigermaßen optimierten Code zu 
schreiben statt hinterher aufräumen zu müssen. Vielleicht bin ich das 
von früher her einfach noch so gewohnt. Ich hab z.B. schon auf dem 64er 
(6502/6510) ne komplette Phasenanschnittsteuerung mit 64 Stufen für 32 
Kanäle programmiert, das ist - auf einer CPU mit 1MHz die 
durchschnittlich 4 Taktzyklen pro Befehl braucht - gar nicht so einfach. 
Das Projekt zur Videosignalerzeugung mit dem AVR ist sicherlich ähnlich 
anspruchsvoll, wenn auch insgesamt um eine 1-2 Größenordnungen schneller 
...

Beim Layouten von (einseitigen!) Platinen geb ich meistens auch keine 
Ruhe, bis es ohne (oder zumindest mit möglichst wenig) Drahtbrücken geht 
...

Ich hoffe, hier Niemanden verärgert zu haben.

Gruß
- Karl

[Karl H. (kbuchegg)]

Karl F. schrieb:

> Aber was spricht denn dagegen, es 'gleich richtig' zu machen?

Oh, wenn du wüsstest :-)

Ich ärgere mich jetzt schon fast 3 Jahre mit geerbtem Code rum, von 
Leuten die in den letzten 15 Jahren es 'gleich richtig' gemacht haben. 
Anstelle den Compiler arbeiten zu lassen haben sie beim Schreiben von 
Code immer nur ihre lokalen Optimierungen im Sinn gehabt. Der Effekt: 
unwartbarer Code, der keinerlei vernünftige Struktur aufweist. Alles ist 
mit jedem über 25 Ecken verbunden, greif an einer Stelle ein und alles 
fällt auseinander.

Und das geilste: Schriebt man dann, soweit das geht, die Dinge neu aber 
diesmal ohne gleich nach Optimierungen zu schielen, dann ist der Code 
meistens mindestens 40% kleiner und meistens auch noch schneller :-) Und 
als Nebeneffekt: Seltsame Fehler fallen auch noch weg.


> Das Projekt zur Videosignalerzeugung mit dem AVR ist sicherlich
> ähnlich anspruchsvoll,

Das ist ein anderes Thema. Da benötigst du aus technischen Gründen 
jeden Taktzyklus. Da wirst du von mir kein Wort hören.
Aber User Interface. So dumm kann man fast nicht tun, dass Ein/Ausgaben 
zu langsam sind. Die sind höchstens in der Bedienung her besch.... weil 
ein unlogisches Paradigma verwendet wird. Aber die Eingabe an sich ... 
da muss man sich schon anstrengen, um eine konventionelle Lösung von der 
Stange so langsam zu kriegen, dass sie unbenutzbar wird.

[Karl F. (kafido)]

Peter Dannegger schrieb:
>
> Die Subtraktionsmethode hast Du Dir angeschaut?

ja, klar ... aber am liebsten wäre mir eine Methode, die - unabhängig 
vom Wert - immer gleich lange braucht. Sonst gibst's nämlich bei stark 
ausgelasteter CPU irgendwann mal die sogenannte 'race-condition', weil 
die Ausgabe von 4711 zufällig länger braucht ... :(


> Hier noch ein Beispiel:
> Beitrag "Formatierte Zahlenausgabe in C"

Ich hab hier zwar wirklich schon sehr viel gelesen, aber DAS kannte 
ich nicht!

> Die Ausgabe der Zahl erfolgt auf ein 2*16 LCD per Timerinterrupt.
> Die Ausgabe im Interrupt ist besonders effektiv, da das Main
> nicht durch die LCD-Wartezeiten belastet wird.

Kommt mir irgendwie bekannt vor :) ... ist mir sofort symphatisch ...

- Karl

Nachtrag: was mir schon bei sprintf(buffer, "%4u", n) nicht gefällt ist, 
dass man die maximale Anzahl von Stellen nicht angeben kann. Wenn also 
eine Zahl größer ist als erwartet, gibt's ein Buffer-Overflow.
Insofern würde ich die Routine noch um einen 'rigid' mode ergänzen, bei 
der max=min ist, sprich: eine genau definierte Anzahl von Zeichen.
Ansonsten: coole Sache - wenn ich das früher gefunden hätte, hätte mir 
das eine Menge Arbeit erspart, denn ich habe so ziemlich die gleichen 
Funktionen selber geschrieben ...