mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik log2(x) invertieren, also (2 hoch x)


Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Für manche Anwendungen mit einem µController benötigt man schon mal
den Logarithmus. Z.B. um Eingangspegel in eine dB-Anzeige zu bringen.

Um die Werte aus dem ADC eines AVR (10-Bit) in ihren log2(x) zu
überführen, hat mir Wikipedia gute Hilfe geleistet.

http://de.wikipedia.org/wiki/Logarithmus
- Berechnung einzelner Binärziffern

Meine ganz plump gestrickte Assembler-Implementation von log2(x)
braucht 78 Byte Code, und ca. 3600 Takte um eine 16-Bit Integer
(in R16 und R17) in 4 Bit Exponent (R18) und 16 Bit Mantisse
(wieder R16 und R17) zu wandeln.
Alle 11 zusätzlich benötigten Register sind hinterher unverändert.

Das verbraucht auf dem kleinsten AVR mit ADC nur wenig Platz, ist
aber bestimmt noch sehr verbesserungsfähig, wenn es schneller oder
kleiner sein muss.

log10(x), oder ln(x) sind daraus mit einer simplen Multiplikation
schnell gemacht.

Wer Interesse hat, kann diese Code-Schnipsel auch gern haben!

Jetzt aber meine Frage: Kennt jemand einen VERGLEICHBAR LEICHT
umzusetzenden Algorithmus, um aus dem log2(x) wieder eine
"normale" 16-Bit-Zahl x zu machen?

Autor: Benjamin S. (recycler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei einer reinen zweier Multiplikation kannst du auch Shifting 
verwenden. Das ist schneller.

2^3 = 1 << 3 = 8 0b0000 1000

Deswegen multipliziere jede stell mit dem Wert, dh pro Bit von x ein 
Shift Operation + Addition.

pseudo code

res = 0
for jedes bit in x
  if bit gesetzt
     res += 1 << stelle von x
return(res)

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kurz und einleuchtend erklärt, leider löst das nur 1/5 meines Problems!

Dezimal:
log2(4096) = 12,000000
log2(6889) = 12,750079
log2(8192) = 13,000000

Binär für eine 16-Bit-Zahl:

log2(X) = E,M   (4 Bit Exponent, 16 Bit Mantisse)

log2(4096) = 1100 , 0000 0000 0000 0000
log2(6889) = 1100 , 1100 0000 0000 0101
log2(8192) = 1101 , 0000 0000 0000 0000

Mit der vorgeschlagenen Rechnung kann ich prima die
4 Bit Exponent invers-logarithmieren, aber wertvolle
16 Bit Mantisse bleiben unberücksichtigt.

Gibts da nichts einfacheres, als mit einer Tabelle

2^(2^-1) = 46341 / 32768
2^(2^-2) = 38968 / 32768
2^(2^-3) = 35733 / 32768
........ = ...

zu arbeiten?

Autor: Abdul K. (ehydra) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du könntest eine Genauigkeitsgrenze definieren und dann die Sache einem 
automatischen Kurve-Fitter vorwerfen.
Mir fehlen jetzt die genauen Suchbegriffe, aber das Problem sollten 
schon andere vor dir zufriedenstellend gelöst haben.
Nimm mal z.B. einen C-Compiler und schaue, wie der die Funktion in 
Assembler umsetzt.

Oder habe ich da was nicht verstanden?

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja.

Das ganze soll kompakt (vielleicht 100, maximal 200 Byte Code) sein.

Die Genauigkeit ist doch offensichtlich:
Kleiner 16 Bit (10^-4 bis 10^-5).

Autor: Abdul K. (ehydra) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hast du das mit dem C-Compiler probiert?

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Interessante Links zur AVR-Arithmetik bitte hier eintragen:
http://www.mikrocontroller.net/articles/AVR_Arithm...
zur Zweierpotenzbildung habe ich da aber nichts entdeckt, nur zum log.

Autor: Abdul K. (ehydra) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das hat aber primär nix mit AVR zu tun, außer es würden Spezialbefehle 
dieser CPU verwendet.

Auch wenn dieses Forum AVR-lastig ist.

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Jörg H. (idc-dragon)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe auch mal einen log2 programmiert, für ein Fixkomma-Ergebnis. 
Der hat erst geschoben (ergibt den ganzzahligen Anteil), dann den 
verbliebenen Rest mit einer kleinen Tabelle und linearer Interpolation 
bestimmt. Die Tabelle habe ich durch sowas wie "curve Fitting" zuvor auf 
kleinste quadratische Abweichung optimiert. Das war mir genau genug und 
ist sehr schnell, Größenordnung 100 Takte.

Das Prinzip ließe sich auch umkehren: mit dem fraktionalen Anteil einen 
Wert bestimmen, diesen dann um eine Anzahl Bits des ganzzahligen Anteil 
schieben.

Jörg

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Scheint wohl wirklich nur mit einer Tabelle Code- und Speichersparend zu 
verwirklichen sein. Dann liege ich mit meinem Ansatz wohl schon ganz 
richtig.

Komisch, dass so viele Antworten am Logarithmus (Exponent,Mantisse)
vorbeigehen...

Die Bits in der log2-Mantisse vertreten negative Zweierpotenzen.
2^-1 = 0,5     MSB
2^-2 = 0,25    MSB-1
2^-3 = 0,125   MSB-2
usw.           MSB-N

Da helfen triviale Integer-Exponentiationsregeln leider NICHT weiter!

Ist auch kein AVR-lastiges Problem:
Kleine µCs haben nun mal wenig FLASH und RAM und KEINE Fließkomma-
Arithmetik drin. Mit Standard-Fließkomma-Routinen ist schnell der
Programmspeicher ausgereizt...

Also ist angemessen genaue Fixkomma-Arithmetik gefragt.

Mein Spaß am µC ist es, aus begrenzten Ressourcen das Optimum
rauszukitzeln - wo bleibt das Erfolgserlebnis, wenn man's nur
GEKAUFT hat?

Trotzdem vielen Dank für die Beiträge,

oder hat doch noch jemand eine bessere Idee?

Autor: Abdul K. (ehydra) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du fragst hier nach Algorithmen, an deren Lösung andere Jahre bastelten. 
Also ganz konkret nochmals: Warum befragst du nicht den C-Compiler? 
Unterstützt der den Datentyp mit dieser Operation nicht? Es kommt von 
dir keinerlei Antwort!

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Abdul K.:

Welchen Datentyp würdest du denn bevorzugen, um aus 10 Bit
ADC-Daten, die nach etwas Addition, Multiplikation und einer 2,37ten
Wurzel in eine 4-stellige Anzeige gebracht werden soll?

Ansonsten:

1) Weil es, um Flash-Speicher zu sparen, Assembler sein soll.

2) Wurde an C-Compilern NICHT über Jahre gebastelt, bzw. stecken da
KEINE Progrmmierer/innen-Jahre drin?

3) Es gibt nicht nur Datentypen, sondern auch Menschen-Typen, die
ein KLEINES Problem in KLEINEM Speicherplatz lösen möchten.
- Just for Fun!

ALGORITHMEN sind für mich "freie Wissenschaft" und damit etwas,
worüber jeder (DER SIE KAPIERT HAT!) beim passenden Anlass gern und
offen spricht, oder schreibt.

Wenn hier im Forum keiner, der einen effektiveren Algorithmus kennt,
auf diesen Thread aufmerksam geworden ist, habe ich eben Pech gehabt.

Autor: Benjamin S. (recycler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schreib halt mal deine Formel hin, dann wird sie begutachtet. vlt findet 
sich eine einfachere lösung. so lässt sich auch eine genauigkeit 
abschätzen. bei nem adc wandler kannst eh meist die letzten bit 
wegschmeisen. wieso dann bis auf die 10. nachkomma stelle anzeigen?

Autor: Abdul K. (ehydra) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ralli, wir können nicht ahnen das du Experimentalprogrammierung 
betreibst. Sowas geht hier regelmäßig unter.

Ein guter C-Compiler ist nicht wesentlich schlechter als ein guter 
Assembler-Programmierer, aber schneller und billiger.
Vorteile hat man bei Handcodierung nur, wenn man was nutzen kann was der 
Compiler nicht weiß oder nicht versteht!
Im Keil-C stecken z.B. 25 Jahre Entwicklung. Da kommste nicht sooo 
schnell ran.

Du ziehst die Wurzel u.a. aus einer Addition? Ist dir aber schon klar, 
das das Quatsch ist - außer du hast Spaß an einer künstlichen 
Auflösungsverringerung.
Ich würde da stupide in float hauen. Nachdenken lohnt nicht. Die 
Umwandlung in BCD ist vermutlich mindestesn genauso lang wie dein 
verkürzter hypothetischer antilog.

Aber vielleicht findet sich ja was. Will dir nicht den Spaß verderben.

Als ich noch jung und hübsch war, hab ich mal den Gaußschen Algorithmus 
für lineare Gleichungssysteme in genau 511 Byte auf einem 
programmierbaren Taschenrechner FX-602P gequetscht. Inkl. dynamischer 
Speicherverwaltung und alphanumerischer Indexabfrage auf dem Display der 
Koeffizienten. Der Schulunterricht war halt langweilig, Laptops noch 
keine erfunden. Vielleicht H4 ?

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hat niemand was zur Frage?

@ Benjamin S.:  Maximal 4 Dezimalstellen. (2^10 ~ 10^4)
Ganz abgesehen davon, dass in diesem Forum hier oft die tollsten
Genauigkeitserweiterungen durch Mehrfachsampling propagiert werden.

@ Abdul K.: Ist die Wurzel aus einer Summe ungenauer, als die
aus Produkten, Quotienten, oder BCD-Quintatoren...???

Autor: Abdul K. (ehydra) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ralli schrieb:
> Hat niemand was zur Frage?
>
> @ Benjamin S.:  Maximal 4 Dezimalstellen. (2^10 ~ 10^4)
> Ganz abgesehen davon, dass in diesem Forum hier oft die tollsten
> Genauigkeitserweiterungen durch Mehrfachsampling propagiert werden.

Mehrfachsampling ist eine gängige Technik für ADC.


>
> @ Abdul K.: Ist die Wurzel aus einer Summe ungenauer, als die
> aus Produkten, Quotienten, oder BCD-Quintatoren...???

Die Wurzel aus einer S ist tendenziell/drastisch ungenauer als aus P 
oder Q. Taylor-Reihenentwicklung zeigt das.

Google "Quintator" brachte nur Müll. Was soll das sein?

Außerdem gibts noch den Genauigkeitsverlust durch arithmetische 
Umformung. Bei DSP-Algorithmen gibt man regelmäßig 4 Bit zu!

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Auch wenn es nicht zu meiner Frage passt:

@ Abdul K.:
Die Wurzel aus 2 x 4 ist ungenauer, als
die Wurzel aus 4 + 4?

Wenn du das erklären kannst, machst du mich schlauer!

Autor: Abdul K. (ehydra) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nö. Ich bin doch nicht dein Idiot! Gehst du mit allen so um? 
Anscheinend.

Autor: Nosnibor (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein interessantes Problem, da hier die übliche Methode fürs 
Festkommarechnen (Integerarithmetik + Skalieren) nicht hilft.

Der einzige Weg, der mir einfällt, benutzt wiederholtes Wurzelziehen, 
d.h.
 - Zwischenergebnis = 1, gemäß Vorkommaanteil geshiftet; W = Wurzel(2)
 - Wenn das erste Nachkommabit gesetzt, Zwischenergebnis mit W 
multiplizieren
 - W = Wurzel(W)
 - Wenn das zweite Nachkommabit gesetzt, Zwischenergebnis mit W 
multiplizieren
 - W = Wurzel(W)
...
Das Wurzelziehen kann man natürlich durch eine Tabelle ersetzen, wenn 
man es eilig (und Speicher übrig) hat.

Nun bin ich neugierig, ob der Compiler es besser machen würde. Ein 
bißchen Suchen in den avr-libc-Quelltexten (exp.S) ergibt, daß die auch 
irgendwann vor dem Problem stehen,
>  2**(-x) for 0 <= x < 1
berechnen zu müssen. An der Stelle wird dann einfach die universelle 
Polynomfunktion mit einer passenden Tabelle aufgerufen.

Das ist jetzt enttäuschend; Polynomapproximation ist irgendwie 
"gemogelt", weil man damit auf die gesuchte Funktion überhaupt nicht 
eingeht; außerdem braucht es häufig mehr Zeit und Speicherplatz als eine 
"richtige" Lösung. Der Vorteil ist, daß es weniger Speicherplatz 
braucht, als eine "richtige" Wurzelfunktion plus ein "richtiger" 
Logarithmus plus ein CORDIC plus... Wenn man in seinem Programm mehrere 
dieser Funktionen braucht, ist das "Mogeln" also gerechtfertigt.

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Nosnibor

Das sieht aus, wie die Umkehrung von

http://de.wikipedia.org/wiki/Logarithmus
-> Berechnung einzelner Binärziffern

Aber das Wurzelziehen ist auch nicht soooo leicht gemacht...

Habe mit der Tabellenlösung weitergemacht:

2^(2^-1)  = 46341 / 32768
2^(2^-2)  = 38968 / 32768
2^(2^-3)  = 35733 / 32768
...
2^(2^-15) = 32769 / 32768

Das bisherige Ergebnis:

log2(2-Byte-Zahl) -> 4 Bit Exponent und 2 Byte Mantisse
     und anschließend
pwr2(4 Bit Exponent und 2 Byte Mantisse) -> 2-Byte-Zahl

Dauer: < 1 ms bei 8 MHz
Fehler < 0,01% für 2-Byte-Zahlen von 1...65535.

Das sollte für die Umwandlung von 10-Bit Sensorwerten in db,
oder ähnliche Aufgaben mehr als ausreichend sein.
Als Beigabe sind z.B. "krumme" Wurzelrechnungen damit auf
eine Multiplikation reduziert - auch wenn hier vielleicht
nur 0,1% Genauigkeit drin sind.

Komisch, dass niemand sonst sich damit beschäftigt hat(?)

Bei allen Threads mit "dB" und Ähnlichem, wurde immer viel
geschwafelt, aber keiner brachte mal nen konstruktiven
Lösungsvorschlag, der über die super-simple Bestimmung des
Exponenten hinausging.

Autor: Abdul K. (ehydra) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kannst du deinen Algorithmus mal in ausführbares C gießen?

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja da bin ich reingefallen, ich hätte auch an die üblichen Tricks 
"(Integerarithmetik + Skalieren)" gedacht, dass das hier nicht geht war 
mir nicht klar.
Wikipedia nennt ziemlich knapp eine Berechnungsmöglichkeit für "real 
powers"/ "Reelle Exponenten"
http://en.wikipedia.org/wiki/Exponentiation#Real_powers
http://de.wikipedia.org/wiki/Potenz_%28Mathematik%...
damit braucht man eine Multiplikation mit einer Konstanten und einen 
Algorithmus für die e-Funktion, das ist vielleicht eher zu finden, 
CORDIC wurde schon genannt.

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Christoph Kessler

Ist doch nur eine Verlagerung von x^2 nach e^2 - siehst du da einen
Vorteil?

@  Abdul K.

- Wie gesagt, das Ganze soll mit definiert (!) beschränkter Genauigkeit
auf KLEINEN µCs wie dem Tiny24 oder vergleichbaren PICs etc. laufen.

- Bit-Shiftereien in C zu SCHREIBEN ist anstrengender, als in ASM.

- Es sollte dir doch als C-Spezialist für µCs keine Probleme bereiten,
meine angedeutete Vorgehensweise in C zu schreiben!

- Sollte ich meine Vorgehensweise zu kryptisch formuliert haben,
kann ich sie nächste Woche noch mal in Schönschrift verfassen.

Bis dann!

(Oder hat noch jemand eine Idee?)

Autor: Benjamin S. (recycler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi Ralli,
ich glaub du weißt immer noch nicht was du willst. Die Eierlegende 
Wollmilchsau auf nem µC gibt es nicht.

In C shiftet man mit a = x << c; Da ist nix anstrengend.

Es wird aber von einer mathematischen Vereinfachung auf allgemeinem x^y 
geredet.

Schreib am besten auf, was du machen willst, und wovon du ausgehst. Vlt 
beschreist du dein Grundproblem. "-> Ich habe eine Formel aus dem 
Wikipedia dort wird log und x^y verwendet". oder irgendwas in der art. 
dann wird dir auch jemand helfen. Wie gesagt, entweder klein und schnell 
oder genau und langsam. Irgendwo muss man Federn lassen.

Autor: Abdul K. (ehydra) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ralli schrieb:
> @ Christoph Kessler
>
> Ist doch nur eine Verlagerung von x^2 nach e^2 - siehst du da einen
> Vorteil?

Hm. Ich kenne das als Logarithmenrechnen-Grundlage. Mußte man auch 
früher auf diversen Taschenrechnern machen, die nur einen einzigen 
bestimmten Logarithmus kannten.


>
> @  Abdul K.
>
> - Wie gesagt, das Ganze soll mit definiert (!) beschränkter Genauigkeit
> auf KLEINEN µCs wie dem Tiny24 oder vergleichbaren PICs etc. laufen.
>
> - Bit-Shiftereien in C zu SCHREIBEN ist anstrengender, als in ASM.

Dann interessiert es aber nur die AVR-Jünger.


>
> - Es sollte dir doch als C-Spezialist für µCs keine Probleme bereiten,
> meine angedeutete Vorgehensweise in C zu schreiben!

Ich bin leider kein C-Freak. Aber selbst als eingefleischter Hardwarer 
kommt man nicht an kleinen C-Programmen vorbei.


>
> - Sollte ich meine Vorgehensweise zu kryptisch formuliert haben,
> kann ich sie nächste Woche noch mal in Schönschrift verfassen.
>

Nö, laß mal. Ich brauche es nicht.


Eigentlich schreibe ich eh hier viel zu viel und sollte mein Scope mal 
wieder einschalten.

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die e-Funktion geht eben mit Cordic, hier gibts Beispieltext in C:
http://www.voidware.com/cordic.htm
double expCordic(double a)
{
    double sinhp, coshp;
    coshp = invGain2;
    sinhp = 0;
    cordit2(&coshp, &sinhp, &a, -1);
    return sinhp + coshp;
}
zuerst werden iterativ gleichzeitig sinh und cosh berechnet, dann 
addiert. Pro Iteration wird das Ergebnis ein Bit genauer (jede dritte 
Iteration muß hier allerdings wiederholt werden, das ist so beim 
hyperbolischen Cordic). Eine Cordic-Berechnung speziell auf AVR ist hier 
zu finden:
https://sourceforge.net/projects/avrfix/
http://www.mikrocontroller.net/articles/AVR-CORDIC
http://www.mikrocontroller.net/articles/AVR_Arithm...

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.