Hallo,
ich möchte den Logarithmus einer Zahl mit dem Prinzip berechnen wie er
in Wikipedia beschrieben ist (siehe Anhang). Leider komme ich da nicht
weiter.
Konkretes Beispiel:
Log2(x) mit x=35
Als erstes soll x in das Gleitkommaformat gewandelt und anschliessend
auf 1<=x<2 normalisiert werden? (Ich verwende den XC8-Compiler mit der
modified 24-bit IEEE754 Darstellung).
Das bedeutet also 35d entspricht 1,000110000000000*2^5
Exponent = 132 = 2^(5+127) = 0x84, Mantisse = 0x0C00 = 3072d, Vorzeichen
pos.
35d = 35.0 wird also vom Compiler als:
0 10000100 000110000000000 (VZ+Exp+M) = 0x420C00 dargestellt.
Jetzt müsste ich doch gemäss dem Algorithmus x quadrieren und Abfragen,
ob die Zahl >2 ist. Wenn >2 dann die Zahl durch zwei teilen.
Irgendwie komme ich da nicht weiter. Vielleicht hat das schon mal jemand
gemacht und kann mir weiterhelfen?
Besten Dank.
Michael S. schrieb:> Hallo,>> ich möchte den Logarithmus einer Zahl mit dem Prinzip berechnen wie er> in Wikipedia beschrieben ist (siehe Anhang). Leider komme ich da nicht> weiter.> Konkretes Beispiel:> Log2(x) mit x=35
Die Binärdarstellung von 35 lautet (8Bit) 00100011
Die linkste 1 ist an der Bitposition 6, also lautet der Vorkommaanteil
des log2 von 35 schon mal 5, weil ja 2 hoch 5 gleich 32 ist. 32 ist ein
bischen weniger als 35, also gibt es noch Nachkommastellen. Welche sind
das?
Und genau da kommt jetzt das Verfahren ins Spiel.
praktisch gesehen kannst du dir das Abzählen der Bits sparen, wenn du
einfach sukzessive durch 2 teilst, bis das Ergebnis im Bereich 1 bis 2
liegt und mitzählst, wie oft du dividieren musstest.
1
35 / 2 = 17.5 1 mal
2
17.5 / 2 = 8.75 2 mal
3
8.75 / 2 = 4.375 3 mal
4
4.375 / 2 = 2.1875 4 mal
5
2.1875 / 2 = 1.09375 5 mal
Das Ergebnis, während der Normierung erhalten, ist dasselbe wie vorher:
Der ganzzahlige Anteil des Logarithmus von 35 lautet 5.
Um jetzt noch den Nachkommaanteil (binär) zu erhalten, lässt du den
Algorithmus wie in deinem Link beschrieben, weiterlaufen.
Aber die Quadratur- und Divisionsoperationen für die Nachkommastellen
muss ich dann doch alle in Gleitkommaformat durchführen, d.h. der
Rechenaufwand ist auch sehr hoch? Oder muss man diese Operationen mit
Festkomma-Arithmetik durchführen?
Die Division ist doch nur durch 2, also in Fixed-Point trivial zu
implementieren.
Ansonsten brauch man nur Vergleiche (easy) und Quadrieren, also
Multiplikation. Die in Fixed-Point ist auch kein Hexenwerk, z.b. für 2
32-Bit Zahlen, die den Wert in Q18.14 enthalten:
1
#include<stdint.h>
2
3
uint32_tmul_Q18_14(uint32_ta,uint32_tb)
4
{
5
return(a*b)>>14;
6
}
Weil a und b bereits < 2 sind, sind sie als uint32 < 2^16. Die
Multiplikation läuft also nicht über. Wenn man zusätzlich noch runden
will:
1
uint32_tmul_Q18_14(uint32_ta,uint32_tb)
2
{
3
uint32_tab=a*b+(1u<<13)
4
returnab>>14;
5
}
Und noch einfacher wird's mit Fixed-Point Unterstützung im Compiler,
z.B. mit avr-gcc 4.8+:
Wie soll das denn funktionieren z.B. mit a=b=1.09375?
Daraus wird ja beim Datentyp uint_32t oder überhaut uint eine "1".
Oder muss ich gedanklich das Komma schieben? Z.Bsp. rechnen 1093*1093?
Dann gibts allerdings irgendwann einen Überlauf.
Aha, ich glaube jetzt ist der "Cent" (ich glaube früher hieß der
Groschen :-) gefallen:
Ich habe mal das hier probiert, das sollte glaub ich gemeint sein mit
Fixpoint-Arithmetik:
Das habe ich bisher noch nicht verwendet, man lernt doch jeden Tag was
dazu...
1
#include<xc.h>
2
#include<stdint.h>
3
4
int32_tfp(doublevalue,int8_tQ)
5
{return(int32_t)(value*(1<<Q));}
6
7
8
intmain(intargc,char**argv)
9
{
10
floatzahl1=1.09375;
11
floatzahl2=1.09375;
12
int8_tg=0;
13
int8_th=0;
14
int16_ty=0;
15
16
g=fp(1.094,6);// g (Q6) = 70
17
h=fp(2.5,4);// h (Q4) = 40
18
y=g*h;// y (Q10) = g (Q6) * h (Q4)
19
20
g=fp(zahl1,6);// g (Q6) = 70 (1.09375*2^6)
21
h=fp(zahl2,6);// h (Q6) = 70 (1.09375*2^6)
22
y=g*h;// y (Q12) = g(Q6) * h(Q6) = 4900 (1.19629*2^12)
Ich habe jetzt folgendes Programm, dass mir den Log2 einer Zahl (20000)
berechnet und das Ergebnis stimmt bis auf kleine Abweichungen mit dem
des Taschenrechners überein:
Log2(20000) = Log10(20000)/Log10(2) = 14.28771
Aber die Berechnungszeit bis zum Ergebnis ist alles Andere als
brauchbar, das geht schneller mit
erg = Log10(20000)*3.322
Aber so in etwa sollte das dem Prinzip entsprechen?
1
#define _XTAL_FREQ 16000000ULL
2
#include<xc.h>
3
#include<stdint.h>
4
#include<math.h>
5
6
int32_tfp(doublevalue,int8_tQ)
7
{
8
return(int32_t)(value*(1<<Q));
9
}
10
11
intmain(intargc,char**argv)
12
{
13
uint8_typei,j=0;
14
int32_tb=0;
15
uint32_typezerg=0;
16
uint16_typeintval=0;
17
floaterg=0;
18
floatvalue=0;
19
20
21
erg=0;
22
intval=20000;
23
value=intval;
24
i=0;
25
while(intval>=2)
26
{
27
intval>>=1;
28
i++;/*i=14*/
29
}
30
zerg+=i;/*Ganzzahl (Vorkommastellen) in Zwischenergebnis =14*2^15*/
31
zerg<<=15;/*Ganzzahl normieren auf 24bit float-Format (VZ+Exp(8)+M(15))*/
Sinn und Zweck des Algorithmus' ist float zu vermeiden. Ansonsten
bist du mit der Potenzreihe von logf besser bedient da sie bestimmt
weniger (float-)Multiplikationen braucht.
Du überlegst dir welche Genauigkeit du brauchst (sowohl für's Ergebnis
als auch während der Berechnung) und ersetzt float durch einen adäquaten
Fixed-Point Typ nebst passender Arithmetik.
Hier ist eine für 8-Bit-Mikrocontroller optimierte Version, die keine
FP-Berechnungen und keine Shift-Operationen mit variabler Weite
verwendet.
Die Funktion fixlog2 berechnet den Zweierlogarithmus für ganzahlige x
von 1 bis 65535. Das Ergebnis ist eine 16.16-Zahl (jeweils 16 Bits von
und nach dem Komma), die mit der Funktion print16_16 ausgegeben wird.
Der maximale absolute Fehler beträgt 0.000051.
Je nachdem, wie gut der Compiler die einzelnen Berechnungen optimiert,
kann man den Code evtl. durch andere Formulierungen noch etwas schneller
machen. Man kann auch durch eine bessere Rundung der Zwischenergebnisse
die Genauigkeit noch etwas verbessern, allerdings braucht das dann auch
wieder etwas mehr Rechenzeit.
Da in der For-Schleife x immer in [1,2) liegt, d.h. das höchstwertige
Bit immer gesetzt istund damit keine Information trägt, könnte man evtl.
die Formeln so umformen, dass stattdessen mit x'=x-1 gerechnet wird.
x' hat dadurch eine zusätzliche Nachkommastelle, was möglicherweise auch
das Ergebnis im 1 Bit genauer macht. Man muss dabei allerdings mögliche
Überläufe von q=x² geschickt verhindern, was den Algorithmus wieder
etwas aufwendiger macht.
Ich bin mir nicht sicher, ob der Code tatsächlich schneller als die
(wesentlich genauere) log2-Funktion aus math.h ist. Am besten probierst
du es aus. Immerhin werden hier 16 32-Bit-Multiplikationen ausgeführt,
was auf einem 8-Bit-µC ohne Hardwaremultiplizierer auch eine ganze Weile
dauert.
Damit du siehst, in welchem Festkommaformat jeweils gerechnet wird, habe
ich dieses als Kommentar neben die einzelnen Zeilen geschrieben.
Vielen Dank Yalu für Deine Hilfe. Das Programm ist sehr kompakt und auch
schnell. Ich habe gestern abend auch noch mal einen Versuch gestartet
und bin auf u.a. Lösung gekommen. Wenn ich beide Berechnungen
vergleiche, braucht meine ca. 500 Cycles länger als Deine mit ca. 7000.
Es sind noch zwei Berechnungen drin, die jeweils ca. 1000 Cycles
brauchen:
Vielleicht kann man die noch optimieren.
Wenn man die for-Schleife auf 8 begrenzt, wird es nochmal ein Stück
schneller, allerdings auch etwas ungenauer.
Hier z.Vgl. mein Code:
1
#include<xc.h>
2
#include<stdint.h>
3
#include<math.h>
4
5
6
int32_tfp(doublevalue,int8_tQ)
7
{
8
return(int32_t)(value*(1<<Q));
9
}
10
11
intmain(intargc,char**argv)
12
{
13
int8_ti,j=0;
14
int16_tb=0;
15
int32_terg=0;
16
uint16_tintval=0;
17
floatvalue=0;
18
uint32_tfp_value=0;
19
20
erg=0;
21
intval=20000;
22
value=intval;
23
i=0;
24
while(intval>=2)
25
{
26
intval>>=1;
27
i++;/*i=14*/
28
}
29
erg+=i;/*Ganzzahl (Vorkommastellen) in Zwischenergebnis =14*2^15*/
30
erg<<=15;/*Ganzzahl normieren auf 24bit float-Format (VZ+Exp(8)+M(15))*/
Hallo Michael S.,
ich habe diesen Thread mit Interesse verfolgt und möchte gerne von Dir
noch erfahren für was benötigst Du den log zur Basis 2 ?
Besonderen dank an Yalu X. für den Fixpunkt Algorithmus.
Den Logarithmus brauche ich für einen Lichtsensor, mit dem ich die
Helligkeit eines Displays ändere. Bei den verschiedenen
Beleuchtungsstärken (Nacht, Zimmerbeleuchtung, Sonne) ist für mich ein
logarithmisches Verhalten besser geeignet.
Michael S. schrieb:> Den Logarithmus brauche ich für einen Lichtsensor, mit dem ich die> Helligkeit eines Displays ändere. Bei den verschiedenen> Beleuchtungsstärken (Nacht, Zimmerbeleuchtung, Sonne) ist für mich ein> logarithmisches Verhalten besser geeignet.
Wäre für sowas nicht ein einfacher LUT besser (einfacher, schneller,
simpler)?!
Eine Lookup-Table lohnt sich nur für AVRs ohne MUL-Befehl, also ATtinys
sowie ATmega16U2. Hierbei wird nur der Bereich [1..2> in die Tabelle
gesteckt, also für die Nachkommastellen. Der ganzzahlige Teil wird wie
oben mittels clz (count leading zeros) ermittelt.
Statt die Tabelle mit einem externen Skript zu generieren lässt sich
diese mit C++14 vom Compiler erstellen:
Henrik H. schrieb:> Eine Lookup-Table lohnt sich nur für AVRs ohne MUL-Befehl, also ATtinys> sowie ATmega16U2.
Dauert dein Studium schon so lange, dass du erst nach 10 Jahren auf
diese Erkenntnis kommst?
Helmut -. (dc3yc)
>Dauert dein Studium schon so lange, dass du erst nach 10 Jahren auf>diese Erkenntnis kommst?
Die Zeit hättest du ja verwenden können, um sein Ergebnis früher zu
posten.
Ich finde es äußerst nützlich, wenn funktionierende Codebeispiele
ausgeschrieben werden.
@Henrik Danke :-)
Michael S. schrieb:> Den Logarithmus brauche ich für einen Lichtsensor, mit dem ich die> Helligkeit eines Displays ändere.
Ein schönes Beispiel, warum die konkrete Anwendung immer an den Anfang
einer Frage gehört. Dann hätte man sich die ganze Arbeit sparen können
und einfach eine Tabelle mit max 16 Stützwerten hingeschrieben.
Peter D. schrieb:> Ein schönes Beispiel, warum die konkrete Anwendung immer an den Anfang> einer Frage gehört.
... am Besten auch gleich mitsamt dem Definitionsbereich der benötigten
Formel. Kein Mensch kommt auf die Idee, für so weniger Werte einen LOG
einzubauen. Das tun nur Programmierer. Physiker nehmen dafür dann sogar
noch MATLAB und einen C-Coder.
Andi schrieb:> Peter D. schrieb:>> Ein schönes Beispiel, warum die konkrete Anwendung immer an den Anfang>> einer Frage gehört.>> ... am Besten auch gleich mitsamt dem Definitionsbereich der benötigten> Formel. Kein Mensch kommt auf die Idee, für so weniger Werte einen LOG> einzubauen. Das tun nur Programmierer. Physiker nehmen dafür dann sogar> noch MATLAB und einen C-Coder.
Ja, das geht sogar noch weiter: In nahezu allen Fällen liefert auch ein
Log2-basierender Algorithmus hinreichend gute Ergebnisse und das sehr
schnell und ohne speicherfressende Tabellen. Der reale Gamma-Wert wird
dadurch zwar nicht korrekt abgebildet, aber es ist eben für die meisten
Fälle doch hinreichend nah dran.
Das liegt daran, dass schon der jeweilige "Aktor" (meist ja PWM) sowieso
oft viel zu wenig Auflösung hat, um der tatsächlichen Gamma-Kurve
korrekt folgen zu können.
Ob S. schrieb:> In nahezu allen Fällen liefert auch ein> Log2-basierender Algorithmus hinreichend gute Ergebnisse
Tabellen sind aber das Schnellste. Auch beim LOG2.
Michael S. schrieb:> Den Logarithmus brauche ich für einen Lichtsensor, mit dem ich die> Helligkeit eines Displays ändere.
Dann ist dein Problem nicht die Berechnung des Logarithmus, sondern die
Auflösung deines Stellgliedes im unteren Helligkeitsbereich.
Welchen Dynamikbereich willst du abdecken und was schafft deine
Helligkeitssteuerung?