www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Division mittels Array umgehen - Problem: großer Zahlenbereich


Autor: Marcel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Moin zusammen,
ich habe gerade ein kleines Projekt, in dem ich einer Zeit zwischen 2 
Impulsen einen Wert zuweise.
Hierbei messe ich die Zeit zwischen 2 Impulsen mittels Timer und habe 
als Ergebnis eine Millisekundenzahl

Die Zeit schwankt von 163 bis 90000 ms.

aktuell rechne ich den Wert mittels Divsion aus:
impulse_time= timer.stop + (timer.overfl-1) * 250 + (255 - timer.start);

Das klappt auch alles wunderbar.

Anschließend berechne ich daraus den Wert
value = (uint16_t) (1800000/impulse_time);

Mich wurmt es, dass die Divsion fast 500 Cicles braucht, was gerade für 
ein Batteriebetriebenes System, was so schnell wie möglich wieder in den 
Schlaf möchte, echt viel ist.

Jetzt habe ich an eine Tabelle gedacht, wo ich mir dann zu einer 
bestimmten Zahl einen Wert hole, aber 90000-163 = 89837 16Bit-Werte :-D 
Ein bisschen viel.

Habt ihr vielleicht noch ein Möglichkeit parat?

Was mir gerade dazu noch einfällt. Man könnte sich einige Wertepaare 
sparen, da in den unteren Impulszeiten folgendes gilt:

180  10000
...  ...
180  9973
181  9972
...  ...
181  9918

Problem nur, dass diese Abstände immer kleiner werden.



Vielen Dank im Vorraus
Grüße Marcel

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@  Marcel (Gast)

>Mich wurmt es, dass die Divsion fast 500 Cicles braucht, was gerade für
>ein Batteriebetriebenes System, was so schnell wie möglich wieder in den
>Schlaf möchte, echt viel ist.

Bitte? Bei 1 MHz sind das 500us. Wie oft machst du denn diese 
Berechnung?  Wie lange ist dein uC im Sleep Mode?
Ich behaupte einfach mal, dass das nicht mal ansatzweise ein Problem 
ist.
Rechne mal den mittleren Stromverbrauch aus.

MFG
Falk

Autor: user (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

wie wäre es mit dem Aufstellen der Tabelle in umgekehrter Reihenfolge:

bis jetzt hast du ja y = f(x) in der Tabelle gespeichert, das heist für 
jeden x-Wert einen y-Wert, da aber viele y-Werte gleich sind wäre eine 
Idee die Tabelle andersherum zu speichern.

also in deinem Fall:

180  10000
181  9972
182  9930
usw.

und dann in dieser Tabelle mit Teile und Herrsche zu suchen, d.h du hast 
den x-Wert und vergleichst mit dem Wert in der Mitte der Tabelle, wenn 
der wert Größer ist dann machst du das gleiche im oberen Teil sonst im 
unteren, bis du den Wert gefunden hast. Das Brauch dann ld(n) Schritte. 
Du speicherst also Wertebereiche.

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
...
impulse_time= timer.stop + (timer.overfl-1) * 250 + (255 - timer.start);
...

Ich hätte jetzt 2 Timerwerte erwartet. Warum 3 und warum die 
Multiplikation mir 250?

Autor: Oliver (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Abgesehen davon, daß ich das genauso sehe wie Falk, stellt sich die 
Frage, was du anschliessend mit dem ausgerechneten Wert "value" machst. 
Vielleicht lässt ich ja da die Division vereinfachen oder gar ganz 
vermeiden.

Marcel schrieb:
> Man könnte sich einige Wertepaare
> sparen,

Genaugenommen gibt es 11042-20+1 = 11023 verschiedene Ergebniswerte. Ist 
aber für eine Tabelle immer noch viel.

Wobei die Auflösung bei den unteren Impulszeiten durch die Impulslänge, 
bei den oberen durch die Rundung auf ganze Zahlen im Ergebnis beschränkt 
wird (ganz oben sind es 5s-Schritte). Wenns denn eh nicht so genau sein 
muß, lässt sich da vielleicht ein Faktor 30 reinrechnen, dann kommst du 
mit einer 16-bit-Division aus.

Oliver

Autor: Andreas R. (rebirama)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Falk Hau doch nicht immer gleich so auf die Pauke. Es scheint für mich 
so, dass du bei jedem Frager vom schlimmsten ausgehst und als ahnungslos 
abstempelst.

@ topic
500µs sind je nach Anwendung wirklich viel Zeit/Strom.

Wenn du mit reduzierter Genauigkeit auskommst, lohnt sich eventuell die 
Interpolation in einer Tabelle mit weniger Einträgen. Die darin 
vorkommende Division kann als schneller Shift implementiert werden.

Für die Linearisierung eines Temperatursensors habe ich das mal gemacht, 
aber das Prinzip lösst sich auch auf eine Division übertragen.

int16_t adc_to_temp(uint16_t adc){
  /* Calculates temperature from sensor values by interpolating over a lookup table*/
  uint8_t i,j;
  //table must have 17 entrys!
  static int16_t lookup  [] ={150,78, 56, 44, 35, 27, 21, 15,10,5,0,-6,-11,-18,-26,-38,-55};
  if ((adc<5) || (adc>1018)) return 150;//prevent shorted/open sensor missbehavior  
  i=adc/64;//caclulate entry, which is just below adc value
  j=adc%64;//relative position between the two nearest table entrys
  int16_t temp = (lookup[i]*(64-j)+lookup[i+1]*j)/64;//interpolate beween two entrys
  return temp;
}


Dauert 72 Takte incl der Plausibilitätsprüfung. Könnte noch schneller 
werden, wenn du durch 256 statt 64 teilst.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Anschließend berechne ich daraus den Wert
> value = (uint16_t) > (1800000/impulse_time);

Gib doch mal ein paar Datentypen an.
impulse_time ist ein unsigned long?

Da dein maximaler Wert 90000 ist, hast du schon untersucht was es bringt 
bzw. im Ergebnis ausmacht wenn du zb alles vorher durch 2 dividierst.
Durch 2 dividiert sich leicht und bringt deine 90000 auf 45000 runter. 
45000 passt aber in einen unsigned int -> 16 Bit Division anstatt 32 Bit 
Division.

Autor: Stefan Ernst (sternst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Marcel schrieb:
impulse_time= timer.stop + (timer.overfl-1) * 250 + (255 - timer.start);
> Das klappt auch alles wunderbar.

Ich sehe allerdings nicht, wie diese Formel korrekt sein kann. Entweder 
der Timer läuft bei 250 über, oder bei 255. Beides geht ja wohl kaum. 
Und wenn es einfach nur ein durchlaufender 8-Bit Timer ist (was ich 
vermute), sind sogar beide Zahlen falsch.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@  Andreas R. (rebirama)

>@ Falk Hau doch nicht immer gleich so auf die Pauke. Es scheint für mich
>so, dass du bei jedem Frager vom schlimmsten ausgehst und als ahnungslos
>abstempelst.

Das ist allzuoft auch so :-0
Und was mich in solchen Dingen immer wieder reizt ist, dass die Leute 
nicht nachgedacht haben sondern einfach losplappern, meistens eher 
jammern.
Wenn sich jemand mal Gedanken gemacht, selbst wenn sie falsch sind, und 
das in dem Posting rüberkommt, sieht das ganz anders aus. Und 
dementsprechend auch meine Reaktion. Siehe Netiquette.

>500µs sind je nach Anwendung wirklich viel Zeit/Strom.

DENKE! RECHNE! REDE!

In der Reihenfolge. Und da der OP mit dem Timer und ICP Zeitdifferenzen 
misst, ist beim AVR sowieso keine riesiges Stromsparpotentiel, weil nur 
der Idle-Mode verfügbar ist.

MfG
Falk

Autor: Andreas R. (rebirama)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Falk

> DENKE! RECHNE! REDE!
du hast "lesen" vergessen, denn der OP hat nichts von ICP geschrieben 
;-)

Ich gehe davon aus, dass der OP den Timer mit externem 32kHz Uhrenquarz 
betreibt und den Atmel bei Overflow oder Interrupts aus dem Sleep holt. 
Sonst wären die 500µs wirklich nicht so schlimm. Es ist ja nicht mal 
klar, dass es überhaupt ein Atmel ist, da kann der OP wirklich noch 
nachbessern.

Sieht für mich etwas nach einem Tacho im Batteriebetrieb aus, da sollte 
es schon sparsam sein.

die 250 sind hoffentlich ein Tippfehler.

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
für die Berechnung von z.B. 2^18/163 bis 2^18/90000 (man muß dann noch 
mit 1800000/2^18 multiplizieren) bietet sich auch die Iteration

x(k+1)=x(k)*(2-a*x(k))

an, die konvergiert gegen 1/a, leider nicht so schnell, für 1/163 muß 
man 20 Runden oder so rechnen, 1/90000 geht in 5 Runden, wenn man mit a 
als Startwert für x anfängt. Das ganze ist bestimmt auch noch pimpfähig, 
z.B. indem man den Startwert über nen Polynom berechnet oder mal richtig 
googelt.

Wenn der OP mit zeitlichen und technischen Randbedingungen rausrückt, 
kan man da mal kucken. Sein Interesse scheint aber leider erlahmt zu 
sein.

math rulez!

Cheers
Detlef

Autor: Oliver (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Detlef _a schrieb:
> die konvergiert gegen 1/a, leider nicht so schnell

Hm. Kannst du das für 90000 mal vorrechnen (ganzzahlig)?

Oliver

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>Hm. Kannst du das für 90000 mal vorrechnen (ganzzahlig)?
Der Konvergenzradius ist 1, das muß man normieren, ich habs in float 
ausprobiert. Für Integerrechnung ist m.E. kein signifikant anderes 
Konvergenzverhalten zu erwarten.

clear all;
a=90000/2^18;
x=a;
for(k=1:30)
 x=x*(2-a*x);
 disp(sprintf('%.8e ',[x x-1/a]))
end;
return

6.46177879e-001 -2.26653323e+000
1.14900277e+000 -1.76370835e+000
1.84474831e+000 -1.06796280e+000
2.52113621e+000 -3.91574897e-001
2.86006912e+000 -5.26419867e-002
2.91175970e+000 -9.51408726e-004
2.91271080e+000 -3.10768397e-007
2.91271111e+000 -3.33066907e-014
2.91271111e+000 4.44089210e-016

Cheers
Detlef

Autor: Oliver (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Detlef _a schrieb:
> Für Integerrechnung ist m.E. kein signifikant anderes
> Konvergenzverhalten zu erwarten.

Das kommt auf deine Definition von signifikant an.

>a=90000/2^18
ergibt ganzzahlig gerechnet 0. Damit wird aus deiner Interation:
>x=x*(2);
und das ist nach einem wie nach 5 Interationsschritten mit Startwert 
x=a=0 immer noch 0.

Abgesehen davon hat deine Formel je Durchlauf 2 Multiplikationen und 
eine Subtraktion. Macht bei 5 Durchläufen 10 Multiplikationen und 5 
Subtraktionen, zugl. der Schleife. Ob das in signifikant (=überhaupt) 
weniger Zyklen als den o.a. 500 Zyklen zu machen ist, ist sehr fraglich.

Oliver

Autor: Marcel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,
vielen Dank für eure rege Beteiligung
Vorweg ich benutze den Atmega169P


Falk Brunner schrieb:
> Wie oft machst du denn diese
> Berechnung?

Die Impulse kommen 24 Stunden pro Tag, mal schneller, mal langsamer.
Ganz nach dem Motto Kleinvieh macht auch Mist.

Falk Brunner schrieb:
> Wie lange ist dein uC im Sleep Mode?

Mein Programm ist so strutkruiert, dass die Interrupts Flags setzen. 
Sind alle Flags wieder gecleart, dann schläft er wieder ein.

Martin schrieb:
> Ich hätte jetzt 2 Timerwerte erwartet. Warum 3 und warum die
> Multiplikation mir 250?

Ja das war meine Schuld, hätte ich erklären sollen. Ich benutze nebenbei 
eine RTC, das heißt ich brauche Start UND Stopp ;)

250 ist von mir ein Korrekturterm im "Mittel". Der Grund ist, dass die 
RTC ja nur alle 1s / 255 = 4 ms inkrementiert. Das heißt ich habe immer 
einen Ungenauikeitsfaktor drinn.
Die Berechnung muss nicht allzu genau sein. Sprich eine Streuung von 
+-8ms sind voll O.K!

Falk Brunner schrieb:
> In der Reihenfolge. Und da der OP mit dem Timer und ICP Zeitdifferenzen
> misst, ist beim AVR sowieso keine riesiges Stromsparpotentiel, weil nur
> der Idle-Mode verfügbar ist.

Doch wenn du die RTC nimmst, schon ;)


Oliver schrieb:
> Wenns denn eh nicht so genau sein
> muß, lässt sich da vielleicht ein Faktor 30 reinrechnen, dann kommst du
> mit einer 16-bit-Division aus.
Das verstehe ich nicht ganz. Ist das so schlimm, wenn man mal 8-bit mal 
16-bit Division durchgeführt.

Das mit der "Umkehrfuntionstabelle" nachdem Teile Herrsche-Prinzip ist 
auch echt ne gute Lösung!

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@  Marcel (Gast)

>Die Impulse kommen 24 Stunden pro Tag, mal schneller, mal langsamer.
>Ganz nach dem Motto Kleinvieh macht auch Mist.

ZAHLEN!!!

>Mein Programm ist so strutkruiert, dass die Interrupts Flags setzen.
>Sind alle Flags wieder gecleart, dann schläft er wieder ein.

Apfelmus ist Mus aus Äpfeln. Danach hat aber keiner gefragt. Sondern 
nach ZAHLEN!

>RTC ja nur alle 1s / 255 = 4 ms inkrementiert.

1/256.

> Das heißt ich habe immer
>einen Ungenauikeitsfaktor drinn.

Du hast einen Denkfehler.

>Doch wenn du die RTC nimmst, schon ;)

Dann möchte man wenigstens die Grundrechenarten beherrschen. Und Null 
ist auch eine Zahl.

>Das verstehe ich nicht ganz. Ist das so schlimm, wenn man mal 8-bit mal
>16-bit Division durchgeführt.

Aber über 500 popelige Takte jammern? Ohje.

Der AVR ist ein 8-Bit Prozessor, seine Register sind 8-Bit breit. 
Addieren und Subtrahieren kann er direkt und schnell. Bei breiteren 
Daten muss der das mit mehreren Registern und Operatione zusammenbauen, 
das dauer länger.

MFG
Falk

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Oliver schrieb:
> Detlef _a schrieb:
>> Für Integerrechnung ist m.E. kein signifikant anderes
>> Konvergenzverhalten zu erwarten.
>
> Das kommt auf deine Definition von signifikant an.
>

Meiner Erfahrung nach kann man durch geeignete Skalierung in diesem Fall 
ein vergleichbares Konvergenzverhalten erzwingen, also 1/10 mehr 
Iterationen oder so.

>>a=90000/2^18
> ergibt ganzzahlig gerechnet 0. Damit wird aus deiner Interation:
>>x=x*(2);
> und das ist nach einem wie nach 5 Interationsschritten mit Startwert
> x=a=0 immer noch 0.

Olli, mal lesen:  Ich habe das Beispiel in float gerechnet.

> Abgesehen davon hat deine Formel je Durchlauf 2 Multiplikationen und
> eine Subtraktion. Macht bei 5 Durchläufen 10 Multiplikationen und 5
> Subtraktionen, zugl. der Schleife. Ob das in signifikant (=überhaupt)
> weniger Zyklen als den o.a. 500 Zyklen zu machen ist, ist sehr fraglich.
>

Ja, das stimmt. Aber ich erwähnte ja schon das vorhandene Pimppotential. 
Aber da ja der OP jetzt doch alle Zeit der Welt für die Berechnung zu 
haben scheint machts nicht soviel Spaß, da weiter drüber nachzudenken, 
interessant ist es aber schon.

Cheers
Detlef

Autor: Oliver (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Detlef _a schrieb:
> Olli, mal lesen:  Ich habe das Beispiel in float gerechnet.
Das war mir bewusst, und genau das war der Grund meiner Nachfrage.

Detlef _a schrieb:
> Meiner Erfahrung nach kann man durch geeignete Skalierung in diesem Fall
> ein vergleichbares Konvergenzverhalten erzwingen,
und handelt sich damit dann gleich wieder 32bit-Operationen ein.

Das ist sicherlich alles in allem eine nette Lösung, aber hier völlig am 
Thema vorbei.

Oliver

Autor: Detlef _a (detlef_a)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Was ich für themenrelevant halte und was nicht kannst Du getrost mir 
überlassen.

Beim Lesen Deiner Postings ist mir nen Comic wieder eingefallen, den ich 
schon vergessen hatte( danke dafür), ich hab ihn mal angehängt.

Cheers
Detlef

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Detlef _a schrieb:

>> und das ist nach einem wie nach 5 Interationsschritten mit Startwert
>> x=a=0 immer noch 0.
>
> Olli, mal lesen:  Ich habe das Beispiel in float gerechnet.

Du musst aber zugeben, dass das Ersetzen einer ulong Division durch 
einen Haufen Floating Point Operationen aller Wahrscheinlichkeit nach 
nicht so das Gelbe vom Ei sein wird.

Es gilt 500 Taktzyklen zu schlagen. Im Moment seh ich noch nicht 
wirklich, wie du das schaffen willst.

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz, da hast Du mich ja geschickt am technischen Ehrgeiz gepackt.

Kucks Du hier:
Beitrag "Integer division, Reciprocal of an integer value, Kehrwert eines integers"

Danke für das schöne Problem, hat Spaß gemacht.

Cheers
Detlef

Autor: Oliver (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hm. Nah dran, aber noch nicht ganz da.

651 Zyklen bei einer Iteration für die Berechnung von 1/163. Leider auf 
16 bit begrenzt, der ursprüngliche Wertebereich von 163 bis 90000 klappt 
damit nicht.

Aber sonst richtig schönes old-school C ;-)

Oliver

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.