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?
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)
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?
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?
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).
Hast du das mit dem C-Compiler probiert?
Interessante Links zur AVR-Arithmetik bitte hier eintragen: http://www.mikrocontroller.net/articles/AVR_Arithmetik#Weblinks zur Zweierpotenzbildung habe ich da aber nichts entdeckt, nur zum log.
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.
Wikipedia hat einige Vorschläge: http://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation die englische bietet noch ein paar mehr: http://en.wikipedia.org/wiki/Exponentiation#Efficiently_computing_an_integer_power http://en.wikipedia.org/wiki/Exponentiation_by_squaring http://en.wikipedia.org/wiki/Addition-chain_exponentiation
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
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?
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!
@ 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.
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?
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 ?
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...???
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!
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!
Nö. Ich bin doch nicht dein Idiot! Gehst du mit allen so um? Anscheinend.
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.
@ 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.
Kannst du deinen Algorithmus mal in ausführbares C gießen?
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%29#Reelle_Exponenten
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.
@ 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?)
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.
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.
Die e-Funktion geht eben mit Cordic, hier gibts Beispieltext in C: http://www.voidware.com/cordic.htm
1 | double expCordic(double a) |
2 | {
|
3 | double sinhp, coshp; |
4 | coshp = invGain2; |
5 | sinhp = 0; |
6 | cordit2(&coshp, &sinhp, &a, -1); |
7 | return sinhp + coshp; |
8 | }
|
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_Arithmetik/Sinus_und_Cosinus_%28CORDIC%29
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.