16Bit Variable - überlauf abfangen?

[M.B. (Gast)]

Hallo

ich mache gerade mit einem AVR mega Berechnungen und komme leider nicht 
mit einer 16-Bit Variablen aus. Theoretisch kann ich dabei auf maximal 
17 bit kommen (Berechnungen maximal: 0X 1FFFF). Das Ergebnis muss ich 
dann teilen um einen Mittelwert zu bilden, der Wiederum nur maximal 16 
Bit groß ist.

Jetzt möchte ich aber keine 32 Bit Variable nutzen. Gibts da einen Trick 
um den Überlauf abzufangen und in die Berechnungen mit einfließen zu 
lassen?
(Bedingungen: temp = ADC-Wandlung maximal 1023 (0x3FF), freq: maximal 
128, ungünstister Fall: 1023 * 128 = 0x 1FF80,
Ergebnis max: 0x1FF80 / 128 = 1023)

uint16_t Mittelwert (uint8_t freq)
{
uint16_t ergebnis;/* oder uint32_t, am besten "uint17_t" ;-) */
for(uint8_t i=0; i<freq; i++ )       // freq: X-mal wiederholen
    {
     temp = ADC_Read(3);             // ADC-Wandlung durchführen
     ergebnis += temp;               // Wandlungsergebnisse aufaddieren
    } 
    ergebnis /= freq;               // Summe durch freq teilen = arithm. Mittelwert

return(ergebnis)
}

[Memristor (Gast)]

Du kannst ueberpruefen ob ein Ueberlauf stattfand:

ergebnis += temp;               // Wandlungsergebnisse aufaddieren
if (ergebnis < temp)
    ;                           // Ueberlauf

[Karl H. (kbuchegg)]

M.B. schrieb:

> Jetzt möchte ich aber keine 32 Bit Variable nutzen. Gibts da einen Trick
> um den Überlauf abzufangen und in die Berechnungen mit einfließen zu
> lassen?

Nicht wirklich.
Du kannst höchstens alle Werte vor der Summierung durch 2 teilen, so 
dass du nicht in den Überlauf reinläufst. Aber dadurch verlierst du 
natürlich das letzte Bit.

Da du aber die Bedingungen kennst, ab wann es zu einem Überlauf kommen 
kann, kannst du natürlich auch 2 verschiedene Code Pfade benutzen:
Solange keine Overflow Gefahr besteht, rechnest du alles mit 16 Bit. 
Wird dein freq zu hoch, gehst du auf 32 Bit Berechnung.

[Brumbaer (Gast)]

Du kannst zwei (falls das max <= 0x1FFFE ist) oder drei oder ... 
Teilsummen  bilden indem du die Summenbildung auf entsprechend viele 
Schleifen verteilst. So dass jede Summe garantiert unter 0x10000 bleibt.

Dann addierst du die Teilwerte und überprüfst ob die Summe kleiner als 
0x10000 ist.

Dadurch hast du nicht bei jedem Schleifendurchgang einen zusätzlichen 
Vergleich.

MfG
SH

[tuppes (Gast)]

M.B. schrieb:
> Jetzt möchte ich aber keine 32 Bit Variable nutzen.

Warum nicht? Hast du keinen Speicher mehr für 32 Bit? Oder hast du Angst 
vor dem Performance-Verlust?

Du darfst nicht vergessen, dass eine selbstgebaute Überlaufbehandlung 
auch Speicher und/oder Performance frisst. Die 32-Bit-Variable muss 
nicht die schlechteste Lösung sein.

Karl heinz Buchegger schrieb:
> Du kannst höchstens alle Werte vor der Summierung durch 2 teilen, so
> dass du nicht in den Überlauf reinläufst. Aber dadurch verlierst du
> natürlich das letzte Bit.

... das bedeutet: Das gemittelte Ergebnis ist entweder richtig oder um 1 
LSB zu klein. Eventuell kann man das einfach vernachlässigen.

Falls nicht: Zähle mit, wie oft du beim Teilen durch 2 eine 1 verloren 
hast, und falls das öfter als (freq/2)-mal der Fall war, musst du den 
Mittelwert am Ende um 1 vergrößern.

Aber wie schon oben gesagt: Ich bin nicht sicher, ob man damit wirklich 
schneller ist als wenn man einfach in 32 Bit rechnet.

[Detlev T. (detlevt)]

Hallo M.B.,

es wäre natürlich hilfreich zu wissen, warum du keine 32-Bit-Variable 
nutzen willst. Wenn es um Zeit geht: Die AD-Wandlung braucht ja auch 
Zeit, die man dafür prima nutzen kann.

Da du ohnehin nicht arithmetisch mittelst, kannst du aber auch gleich 
das letzte Bit wegschmeißen. Das führt nur zu einem Fehler, wenn bei 
ausnahmslos allen(!) Messwerten das LSB=1 ist.

Gruß, DetlevT

[Karl H. (kbuchegg)]

tuppes schrieb:

> Falls nicht: Zähle mit, wie oft du beim Teilen durch 2 eine 1 verloren
> hast, und falls das öfter als (freq/2)-mal der Fall war, musst du den
> Mittelwert am Ende um 1 vergrößern.

Die Idee gefällt mir.
Das ist eigentlich gar nicht so schwer zu realisieren.

> Aber wie schon oben gesagt: Ich bin nicht sicher, ob man damit wirklich
> schneller ist als wenn man einfach in 32 Bit rechnet.

Ich denke er fürchtet sich vor der 32 Bit Division zum Schluss.
Ob die Summierung in uint16_t oder in uint32_t passiert, ist sicherlich 
nicht der große Zeitfaktor. Und wenn doch, kann man das über eine 
Umstellung der ADC Funktion auffangen, wie schon richtig angemerkt 
wurde. Ich denke allerdings nicht, dass das die große Performance 
bringt.

Aber deine Idee der Korrektur des letzten Bits hat was (sofern das 
überhaupt relevant ist)

[M.B. (Gast)]

Hallo zusammen,

zunächst einmal vielen Dank für Eure Hilfe. Besonders freut mich, dass 
es so viele Lösungsmöglichkeiten gibt! Vielen Dank dafür.

Ich habe natürlich selber noch ein bischen hin und her probiert und habe 
im moment die Lösung von

Brumbaer schrieb:
> Du kannst zwei (falls das max <= 0x1FFFE ist) oder drei oder ...
> Teilsummen  bilden indem du die Summenbildung auf entsprechend viele
> Schleifen verteilst. So dass jede Summe garantiert unter 0x10000 bleibt.

eingbaut. Ich weiß noch nicht ob ich damit glücklich bin, denn dann 
brauche ich ja auch wieder zwei Variablen bzw. eine Hilfsvariable:

Mittelwert1 = Mittelwert(64);
Hilfsvariable = Mittelwert(64);
Mittelwert1 = (Mittelwert1 + Hilfsvariable) / 2;

Daher passt dann wirklich die uint32_t obwohl ich dann 15 Bit 
"verschenke"
oder gehts auch so:
(Mittelwert1 = 16Bit)

Mittelwert1 = (Mittelwert(64) + Mittelwert(64))/2;

tuppes schrieb:
> Warum nicht? Hast du keinen Speicher mehr für 32 Bit? Oder hast du Angst
> vor dem Performance-Verlust?
Das Programm ist noch nicht fertig, und ich wollte nicht mit 1000 
Variablen um mich schmeißen. Vielleicht brauche ich den Platz irgendwann 
mal. Ich möchte halt schon im sehr frühen Stadium Ressourcenschonend 
arbeiten.
Und du kennst das ja: Dann mache ich hier noch eine Variable hin, ist ja 
noch genug Platz. Hier auch noch eine; die 2 Byte. [...] und irgendwann 
ist der Speicher voll.

Karl heinz Buchegger schrieb:
> Ich denke er fürchtet sich vor der 32 Bit Division zum Schluss.

Davor fürchte ich mich definitiv nicht, denn ein aufsummieren für die 
AD-Wandlung mache ich immer mit einem Vielfachen von 2, sodass ich bei 
der 32-Bit Division nur Bits schieben muss!

Nochmals vielen Dank für die vielen Lösungsansätze. Werde mich für eine 
der genannten noch entscheiden müssen.

Einen schönen Tag noch...

[Falk B. (falk)]

@  M.B. (Gast)

>mal. Ich möchte halt schon im sehr frühen Stadium Ressourcenschonend
>arbeiten.

Löblich. Aber man kann es auch übertreiben. Das was du hier zelebrierst 
ist Paranoia.

>noch genug Platz. Hier auch noch eine; die 2 Byte. [...] und irgendwann
>ist der Speicher voll.

Passiert so schnell nicht.

MFG
Falk

[Hc Z. (mizch)]

"We should forget about small efficiencies, say about 97% of the time: 
premature optimization is the root of all evil."  (Knuth)

Das schreibst Du (TE) jetzt 100 mal.

[Läubi .. (laeubi)]

Falk Brunner schrieb:
> Passiert so schnell nicht.
Zumal die Variablen nur auf dem Stack leben solange bis die Funktion 
verlassen wird.
Dieses einsamme "temp" verwundert mich da auch etwas, das wird doch 
hoffentlich keine GLobale Variable sein um Variablennamen "zu sparen".

[Karl H. (kbuchegg)]

M.B. schrieb:

> Karl heinz Buchegger schrieb:
>> Ich denke er fürchtet sich vor der 32 Bit Division zum Schluss.
>
> Davor fürchte ich mich definitiv nicht, denn ein aufsummieren für die
> AD-Wandlung mache ich immer mit einem Vielfachen von 2, sodass ich bei
> der 32-Bit Division nur Bits schieben muss!

Irrtum.
Dein Compiler weiß davon nichts.
Für den ist freq erst mal eine Unbekannte.
Wenn du da durch dividierst, muss tatsächlich dividiert werden.

[Karl H. (kbuchegg)]

Läubi .. schrieb:

> Dieses einsamme "temp" verwundert mich da auch etwas, das wird doch
> hoffentlich keine GLobale Variable sein um Variablennamen "zu sparen".


LOL

Auch ein richtiges Initialisieren von ergebnis auf 0 könnte den 
Ergebnissen zuträglich sein. Womit wir bei einer Abart von Knuth wären

* machs zuerst richtig
* dann sieh nach ob du Optimieren musst
* und erst dann: fang an zu optimieren

uint16_t Mittelwert (uint8_t freq)
{
  uint32_t ergebnis = 0;

  for(uint8_t i=0; i<freq; i++)
    ergebnis += ADC_Read(3);
  
  return (uint16_t)( ergebnis / freq );
}

[tuppes (Gast)]

M.B. schrieb:
> und ich wollte nicht mit 1000
> Variablen um mich schmeißen

Wie du schon selber erkannt hast, belegen auch die Hilfsvariablen Platz, 
du gewinnst also nichts.

Dafür opferst du aber die Geradlinigkeit des Codes. N Werte aufsummieren 
und durch N teilen ist eine Aufgabe, die an Übersichtlichkeit kaum zu 
überbieten ist und die, glatt runterprogrammiert, keine Probleme machen 
wird.

Bei Tricks wie diesem hier

Mittelwert1 = Mittelwert(64);
Hilfsvariable = Mittelwert(64);
Mittelwert1 = (Mittelwert1 + Hilfsvariable) / 2;

wäre ich da schon misstrauischer.

[M.B. (Gast)]

Ich habe heute eine Menge dazu gelernt!
Nochmals danke, auch für die Tipps zwischen den Zeilen!

[M.B. (Gast)]

Karl heinz Buchegger schrieb:
> M.B. schrieb:
>
>> Karl heinz Buchegger schrieb:
>>> Ich denke er fürchtet sich vor der 32 Bit Division zum Schluss.
>>
>> Davor fürchte ich mich definitiv nicht, denn ein aufsummieren für die
>> AD-Wandlung mache ich immer mit einem Vielfachen von 2, sodass ich bei
>> der 32-Bit Division nur Bits schieben muss!
>
> Irrtum.
> Dein Compiler weiß davon nichts.
> Für den ist freq erst mal eine Unbekannte.
> Wenn du da durch dividierst, muss tatsächlich dividiert werden.

Stimmt, das habe ich sozusagen vorausgesetzt und nicht weiter bedacht. 
Jetzt ist es aber so, dass ich das weiß und der compiler nur noch nicht. 
Wie kann ich dem Compiler mitteilen, das "er nur schieben" muss. Ich 
benutze die Funktion für verschiedene Berechnungen und freq ist zwar oft 
unterschiedlich, aber immer ein Vielfaches von zwei.

Hast du einen Tipp wie ich den Schiebeoperator anhand von freq 
unkompliziert ermitteln kann?
Meine erste Idee ist eine Schleife, in der freq so lange geteilt wird, 
bis sie 1 ist und die anzahl mitzählen. Ist es die einzige Möglichkeit? 
Wenn ja, soll ich die Division so stehen lassen? Oder mir diese "Mühe" 
machen. heißt: Bringt das was?

[M.B. (Gast)]

Optisch ist es ja einfach:

64(d) = 0100 0000(b)
********************
        7654 3210 Stelle

"1"-Bit an 6. Stelle

x/64 = x um 6 Stellen nach Rechts schieben

[Jan (Gast)]

Vielleicht so:

uint8_t shift = 0;

while(freq > 0)
  {
  freq >> 1;
  shift++;
  }
return (uint16_t)( ergebnis >> shift);

Gruss, Jan

[Karl H. (kbuchegg)]

Jan schrieb:

> return (uint16_t)( ergebnis >> shift);

Das willst du auf jeden Fall vermeiden. Mit variabler Anzahl shiften ist 
immer schlecht.

    while( freq > 0 ) {
      freq /= 2;
      ergebnis /= 2;
    }

[Jan (Gast)]

>> Mit variabler Anzahl shiften ist immer schlecht.

Warum?

Gruss, Jan

[Karl H. (kbuchegg)]

Jan schrieb:
>>> Mit variabler Anzahl shiften ist immer schlecht.
>
> Warum?

Weil der AVR das nicht mit einer eigenen Operation kann und der Compiler 
das in eine Schleife aufdröseln muss.

Dein Code wird zu dem hier:

  uint8_t shift = 0;
  uint8_t tmp;

  while(freq > 0)
  {
    freq >> 1;
    shift++;
  }

  for( tmp = 0; tmp < shift; ++tmp )
    ergebnis >> 1;

  return ergebnis;

Da kannst du dann aber das Schieben gleich in die erste Schleife 
reinverfrachten und musst als Nebeneffekt nicht in shift mitzählen.

Und bitte:
Wenn du Division meinst, dann schreib auch Division. Der Compiler 
ersetzt das dann schon durch Schieben, wenn es geht.

[Falk B. (falk)]

@  Jan (Gast)

>> Mit variabler Anzahl shiften ist immer schlecht.
>Warum?

Weil das auf dem AVR und ähnlichen kleinen Mikrocontrollern relativ 
langsam ist.

MFG
Falk

[Jan (Gast)]

aha

[Jan (Gast)]

> Wenn du Division meinst, dann schreib auch Division. Der Compiler
> ersetzt das dann schon durch Schieben, wenn es geht.

Falsch:
Die Frage war ja, wie kriegt man die Schiebeoperation hin. Also meinte 
ich nicht Division.

Aber Deine Lösung ist unzweifelhaft eleganter. ;-)

Gruss, Jan

[Karl H. (kbuchegg)]

Jan schrieb:
>> Wenn du Division meinst, dann schreib auch Division. Der Compiler
>> ersetzt das dann schon durch Schieben, wenn es geht.
>
> Falsch:
> Die Frage war ja, wie kriegt man die Schiebeoperation hin.

Die macht schon der Compiler rein, wenn es möglich ist.

> Also meinte
> ich nicht Division.

Aber im Kontext der Aufgabenstellung ist das logisch gesehen zunächst 
eine Division. Also schreib auch Division hin und überlass es dem 
Compiler sich was zu überlegen, wie man die Dinge schnell implementieren 
kann.

[M.B. (Gast)]

Hallo nochmal,
die Lösung von K-H Buchegger gefällt mirsehr gut, sie ist schlicht und 
effektiv.

Karl heinz Buchegger schrieb:

 while( freq > 0 ) {
       freq /= 2;
       ergebnis /= 2;
     }

Aber sollte es nicht korrekterweise

while( freq > 1 )

 heißen, ansonsten wird eine Division zuviel gemacht.

[brumbaer (Gast)]

Ich möchte kein Spielverderber sein, aber das funktioniert nur wenn Freq 
eine 2er Potenz ist.

Oben stand aber ein Vielfaches von zwei.

Oder habe ich etwas überlesen ?

MfG
SH

[M.B. (Gast)]

brumbaer schrieb:
> Ich möchte kein Spielverderber sein, aber das funktioniert nur wenn Freq
> eine 2er Potenz ist.
>
> Oben stand aber ein Vielfaches von zwei.
>
> Oder habe ich etwas überlesen ?
>
> MfG
> SH
Du hast recht, war auch so gemeint mit der zweier-Potenz!!
Streiche: Vielfaches von 2 --> Setze 2er-Potenz!

Aber danke für den Hinweis

[Karl H. (kbuchegg)]

M.B. schrieb:

> Aber sollte es nicht korrekterweise

while( freq > 1 )

 heißen,
> ansonsten wird eine Division zuviel gemacht.

Ja.
War nur ein Schnellschuss von mir, ohne groß nachdenken.