Hallo zusammen,
ich müsste eine einfache Potenzberechnung durchführen, in der Form:
f(x)=x^1,4.
In der math.h Bibliothek gibt es dazu ja die pow() Funktion,
allerdings sprengt die Verwendung der Funktion meine
Programmspeicherkapazität, ich nehme, weil die Funktion mit
long-Variablen
definiert ist.
Gibt es hier eine Programmspeicher-sparende Möglichkeit, die Berechnung
dennoch durchzuführen ?
Die mathematische Umformung mit exp und log ist ja leider ähnlich
speicherbedürftig.
Wie kann ist das Problem lösen ?
Danke,
Helge
Helge schrieb:> x hat den Wertebereich int
Ein Bisschen genauer musst du deine Anforderungen schon spezifizieren:
- Hat int auf deinem µC 16 Bit?
- Wenn ja, geht also der Wertebereich von x von -32768 bis +32767?
Der Wertebereich von x**1.4 geht somit bis 2097062 für positive x und
bis -648056-1994510i für negative x.
- Brauchst du tatsächlich komplexe Ergebnisse, oder fängt der
Wertebereich von x vielleicht doch eher bei 0 an?
- Wie genau soll das Ergebnis sein?
- Wieviel Flash-Speicher steht maximal für die Funktion zur Verfügung?
- Wie lange darf die Ausführung der Funktion maximal dauern?
- Auf welchem Prozessor soll das Ganze laufen?
Die Fragen dürfen auch mit "egal" beantwortet werden.
Yalu X. schrieb:> - Hat int auf deinem µC 16 Bit?
Die Variablen sind tatsächlich so groß wie definiert, d.h. es findet bei
255 kein Überlauf statt.
>> - Wenn ja, geht also der Wertebereich von x von -32768 bis +32767?
Der Wertebereich für x muss eigentlich nur von 0-4000 reichen.
> Der Wertebereich von x**1.4 geht somit bis 2097062 für positive x und> bis -648056-1994510i für negative x.>> - Brauchst du tatsächlich komplexe Ergebnisse, oder fängt der> Wertebereich von x vielleicht doch eher bei 0 an?
Der Wertebereich beginnt bei 0
>> - Wie genau soll das Ergebnis sein?
ganzzahlig ist ausreichend
>> - Wieviel Flash-Speicher steht maximal für die Funktion zur Verfügung?
Der Atmega48 hat 4k Flashspeicher, und es waren ca. 95% ausgenutzt, d.h.
ich sollte noch 0,2k Flsachspeicher zur Verfügung haben.
>> - Wie lange darf die Ausführung der Funktion maximal dauern?
Die Zeit ist eher unkritisch, das darf auch 100ms dauern.
>> - Auf welchem Prozessor soll das Ganze laufen?
Atmega48
>> Die Fragen dürfen auch mit "egal" beantwortet werden.
Ich hoffe, ich konnte alles korrekt beantworten.
Die Thematik Variablendefinition etc. ist nicht ganz meine Stärke.
Ich habe die pow() Funktion in math.h vom Datentyp long auf int
reduziert:
/**
The function pow() returns the value of \a __x to the exponent \a
__y.
*/
extern int pow(int __x, int __y) _ATTR_CONST_;
#define powf pow /**< The alias for pow(). */
Leider sinkt dadurch nicht der Speicherbedarf.
Was könnte ich hier noch als Alternative verwenden ?
Ich habe ein Alternative zur pow()-Funktion aus der math.h gefunden:
| int ipow(int b, int e) {
| int p = 1;
|
| for(;;) {
| if(e & 1)
| p *= b;
| e >>= 1;
| if(e == 0)
| break;
| b *= b;
| }
| return p;
| }
|
| /* ... */
| erg = ipow(x, y);
Allerdings kann ich hier im Exponenten keine Kommazahl einsetzen.
Helge schrieb:> Ich habe die pow() Funktion in math.h vom Datentyp long auf int> reduziert:
Meinst Du, daß das irgendwas reduziert, wenn Du den Funktionsprototypen
umschreibst?
Helge schrieb:> Yalu X. schrieb:>> - Hat int auf deinem µC 16 Bit?> Die Variablen sind tatsächlich so groß wie definiert, d.h. es findet bei> 255 kein Überlauf statt.
Das ist keine Antwort auf diese Frage. Was er wissen will ist
sizeof(int), dass ist bei AVRs normalerweise 2 (Byte).
Helge schrieb:> Gibt es hier eine Programmspeicher-sparende Möglichkeit, die Berechnung> dennoch durchzuführen ?> Die mathematische Umformung mit exp und log ist ja leider ähnlich> speicherbedürftig.
Yep. Polynomiale Approximation und/oder anderes numerisches
Herumgetrickse, um die Operation gut zu approximieren. Das ist nicht
unbedingt trivial, aber wird durch den festen Exponenten stark
vereinfacht.
Die Frage ist aber auch, wie schnell muss es sein und wie genau muss das
Ergebnis sein?
Vielleicht reicht es für deine Zwecke, wenn du eine kleine Wertetabelle
mit einigen Stützstellen speicherst und zwischen diesen dann lineare
Interpolation durchführst.
Danke für die Antworten.
greg schrieb:> Die Frage ist aber auch, wie schnell muss es sein und wie genau muss das> Ergebnis sein?
Die Zeit spielt eingentlich keine Rolle, ein ganzzahliges Ergebis reicht
an Genauigkeit aus.
Wenn es keine Möglichkeit gibt, x^1,4 ohne math.h und float
auszurechnen, dann versuche ich das über ein Näherungsverfahren.
greg schrieb:> Yep. Polynomiale Approximation und/oder anderes numerisches> Herumgetrickse, um die Operation gut zu approximieren. Das ist nicht> unbedingt trivial, aber wird durch den festen Exponenten stark> vereinfacht.
Die prinzipielle Vorgehensweise ist also, erst mal in ein Array die
Funktionswerte für f(x)=x^1,4 zu hinterlegen, und dann in der Berechnung
des Funktionswert abzufragen, so wie im Artikel zum LED--Fading:
http://www.mikrocontroller.net/articles/LED-Fading
So müsste es funktionieren, oder ?
Naja, für eine komplette Tabelle hast du doch keinen Platz. Die bräuchte
ja 4000 Einträge bei 0 < x <= 4000. Die Idee ist, dass du nur wenige
Werte speicherst, z.B. im Abstand von 400 x-Werten, und dann für die
Berechnung des Funktionswertes zur Approximation die lineare Funktion
zwischen den beiden benachbarten Tabellenwerten verwendest. Siehe auch:
https://de.wikipedia.org/wiki/Interpolation_%28Mathematik%29#Lineare_Interpolation
ja stimmt, ich hab's eben mit einen array[256] ausgetestet, und dafür
ist der Speicher (knapp) zu klein.
Aber ich könnte das array auch in den EEprom schreiben, oder ?
Da habe ich noch genügend Speicher.
Helge schrieb:> Aber ich könnte das array auch in den EEprom schreiben, oder ?
Probiers halt aus, ich vermute mal das der Hersteller den EEPROM schon
zu schreiben und lesen vorgesehen hat...
Also wenn du kein Zeitproblem hast, dann würde ich mal eine Taylorreihe
aufstellen und das daraus gewonne Polynom implementieren. Ist natürlich
nicht ganz ohne wenn du nur Integer nutzt aber das sollte durchaus
machbar sein. Sowas macht doch spass ;-)
Läubi .. schrieb:> Probiers halt aus, ich vermute mal das der Hersteller den EEPROM schon> zu schreiben und lesen vorgesehen hat...
Ich fürchte der EEprom (256byte im Atmega 48) ist auch zu klein, um die
das uint16[256]-Array aufzunehmen.
Da passen ja wirklich nur ein paar wenige Variablen rein, oder ?
4000^1,4 = 110378, das passt nicht mehr in 16 Bit. Man könnte (mal
wieder) tricksen und /2 den Wert speichern und *2 danach rechnen, kostet
halt 1 Bit Auflösung.
Die Frage ist wie immer, wieviel Fehler kann man sich leisten? 1LSB? 10
LSB? 100LSB? Man könnte über ein logarithmische Kennlinie gehen, so wie
A/u Law
Ist als Funkion leicht relaisierbar.
http://de.wikipedia.org/wiki/A-law
Da die Kurve nur leicht gekrümmt ist, kann man mit einer handvoll
Stützstellen linear interpolieren. Die Stützstellen müsssen ja nicht
gleichmässig verteilt sein.
Falk Brunner schrieb:> 4000^1,4 = 110378, das passt nicht mehr in 16 Bit. Man könnte (mal> wieder) tricksen und /2 den Wert speichern und *2 danach rechnen, kostet> halt 1 Bit Auflösung.
Die Auflösung sollte eigentlich ausreichen, allerdings habe ich ja
dennoch das Problem, dass falls der Wert für x zwischen den Arraywerten
liegt, ich keinen definierten Ausgangswerte erhalte, oder ?
Also falls z.Bsp. x=15 ist und das Array nur für x gleich 10 und 20
einen Datenwert gespeichert hat.
Wie funktioniert denn dann in so einen Fall eine Interpolation ?
Die A-Law Funktion ist ja interessant, aber das muss ich mir noch etwas
genauer ansehen, das habe ich noch nicht kapiert.
Ich brauche aber dazu ja auch eine Wertetabelle für den Logarithmus,
oder ?
Helge schrieb:> Falk Brunner schrieb:>> 4000^1,4 = 110378, das passt nicht mehr in 16 Bit. Man könnte (mal>> wieder) tricksen und /2 den Wert speichern und *2 danach rechnen, kostet>> halt 1 Bit Auflösung.>> Die Auflösung sollte eigentlich ausreichen, allerdings habe ich ja> dennoch das Problem, dass falls der Wert für x zwischen den Arraywerten> liegt, ich keinen definierten Ausgangswerte erhalte, oder ?> Also falls z.Bsp. x=15 ist und das Array nur für x gleich 10 und 20> einen Datenwert gespeichert hat.> Wie funktioniert denn dann in so einen Fall eine Interpolation ?
Siehe
http://de.wikipedia.org/wiki/Interpolation_(Mathematik)#Lineare_Interpolation
>dennoch das Problem, dass falls der Wert für x zwischen den Arraywerten>liegt, ich keinen definierten Ausgangswerte erhalte, oder ?
Oder.
>Also falls z.Bsp. x=15 ist und das Array nur für x gleich 10 und 20>inen Datenwert gespeichert hat.>Wie funktioniert denn dann in so einen Fall eine Interpolation ?
Man zeichnet gedanklich eine Linie zwischen den beiden Punkten.
Mathematik Klasse 10 oder so ;-)
http://de.wikipedia.org/wiki/Interpolation_%28Mathematik%29#Lineare_Interpolation>Ich brauche aber dazu ja auch eine Wertetabelle für den Logarithmus,>oder ?
Nein. man braucht aber ggf. ein paar Hilfsfaktoren.
Vielen Dank für die Antworten !
Ich teste es erstmal mit der linearen Interpolation aus,
falls das nicht ausreicht, wage ich mich an die A-law Thematik.
Hier ist noch ein etwas anderer Ansatz:
Der angehängte Code berechnet für alle natürlichen x ≤ 4522 den
ganzzahligen Anteil von y = x ** 1.4 und erfüllt damit die Anforderungen
an den Wertebereich und die Genauigkeit.
Dafür werden 386 Bytes Flash benötigt (GCC 4.8.2). Damit ist der Code
zwar deutlich kleiner als die pow-Funktion einschließlich der dafür
erforderlichen FP-Basisfunktionen (zusammen ca. 1800 Bytes), passt aber
immer noch nicht in die zur Verfügung stehenden 200 Bytes.
Man könnte nun versuchen, den Code in die 200 Bytes zu pressen, indem
man ihn in Assembler nachzuprogrammiert. Das wäre aber eine Optimierung
von fast 50%, was sicher nicht ganz leicht zu schaffen ist.
Wesentlich einfacher ist es wahrscheinlich, das restliche Programm (ca.
3900 Bytes) mit ein paar Optimierungen auf C-Ebene um etwa 5% zu
verkürzen und damit den fehlenden Flash-Speicher freizuschaufeln.
Die Funktion pow14 sucht per Halbierungsverfahren die größte Zahl y, für
die y⁵ ≤ x⁷ ist. Diese großen Potenzen werden mit der Funktion big_pow
berechnet, die ihrerseits die Funktion big_mul benutzt. Mit big_greater
wird in jedem Schritt geprüft, ob das Zwischenergebnis den Zielwert
überschritten hat.
Der Code kann in gewissen Grenzen durch Ändern von vier Konstanten auch
an andere rationale Exponenten und andere Wertebereiche angepasst
werden:
1
EXP_NOM: Zähler des Exponenten
2
3
EXP_DENOM: Nenner des Exponenten
4
5
BIG_SIZE: Speichergröße der maximal als Zwischenergebnis auftretenden
6
Potenzen (x⁷ und y⁵) in Bytes
7
8
NUM_BITS: Maximale Bitzahl des Resultats
Was mich noch inmteressieren würde: Woher kommt die Konstante 1.4 bzw.
was wird mit der berechneten Potenz angestellt?
Edit:
Ich habe den Code nicht am einem AVR, sondern nur auf dem PC getestet.
Sollten auf dem AVR falsche Ergebnisse geliefert werden oder die
Laufzeit zu hoch sein, bitte Bescheid geben.
Vielen Dank für die ausführliche Antwort, ich teste den Code gleich mal
aus.
Yalu X. schrieb:> Was mich noch inmteressieren würde: Woher kommt die Konstante 1.4 bzw.> was wird mit der berechneten Potenz angestellt?
Die Potenzfunktion mit der Konstante 1,4 benötige ich, um Unterschiede
der Empfindlichkeit von Sensorsignale von verschiedenen Geräten
auszugleichen.
Ich addiere/subtrahiere vom Rohdatenwert die Funktion f(x)=Faktor*x^1,4,
und kalibriere dadurch die einzelnen Geräte auf die gleich
Empfindlichkeit.
Yalu X. schrieb:> Ich habe den Code nicht am einem AVR, sondern nur auf dem PC getestet.> Sollten auf dem AVR falsche Ergebnisse geliefert werden oder die> Laufzeit zu hoch sein, bitte Bescheid geben.
Ich habe pow.c. in mein Projekt eingebunden, und als x eine Konstante
(20) eingegeben und über UART an den Rechner gesendet.
USART_Transmit_String(itoa(pow14(20),buffer,10));
Es kommt aber immer nur 0 raus, laut Taschenrechner sollte 66
rauskommen.
Ich hoffe, dass ich in der Einbindung nichts falsch gemacht habe.
Entschuldigung!
Die Funktion funktioniert einwandfrei,
hab vergessen den Prototypen einzubinden.
Die Codegröße ist auch kein Problem, ich kann mit der AVR-Studio Version
4.19
nur nicht den genauen Speicherbedarf anzeigen lassen.
Die Codegröße des HEX-Files ist ja nicht direkt aussagakräftig.
Vielen Dank an alle Antwortenden,
dieses Forum ist wirklich einsame Klasse !
@ Helge (Gast)
>Die Codegröße ist auch kein Problem, ich kann mit der AVR-Studio Version>4.19>nur nicht den genauen Speicherbedarf anzeigen lassen.
Dann bist du BLIND! Das wird nach JEDEM Compilerlauf im Fenster Build
unten angezeigt! Wahrscheinlich hast du das Fenster ausgebledet oder ein
anders aktiviert!
Kann man per Menu VIEW->Toolbars->Build Output wieder aktivieren.
Falk Brunner schrieb:> Dann bist du BLIND!
Da dachte ich auch erst, aber das Häkchen bei build output ist gesetzt,
und am Ende steht nur "Build succeeded with ...warnings" ohne
Speicherbedarfanzeige.
Ahhh, du hast 4.19, da steckt die Atmel-Toolchain drin. Hmmm, wo man
dort die Speicheranzeige herbekommt weiß ich nicht.
Darum hab ich hier 4.18, die letzte 4er mit direkter avr-gcc
Integration.
Hallo Yalu,
Yalu X. schrieb:> Der Code kann in gewissen Grenzen durch Ändern von vier Konstanten auch> an andere rationale Exponenten und andere Wertebereiche angepasst> werden:> EXP_NOM: Zähler des Exponenten>> EXP_DENOM: Nenner des Exponenten>> BIG_SIZE: Speichergröße der maximal als Zwischenergebnis auftretenden> Potenzen (x⁷ und y⁵) in Bytes>> NUM_BITS: Maximale Bitzahl des Resultats
Der Code kann, wie du schreibst, in gewissen Grenzen, auch noch für
andere
Wertebereiche angewendet werden.
Als default-Wert hast du bei NUM_BITS den Wert 11 eingegeben. Dieser
begrenzt das Ergebnis auf den Maximalwert von 131072, oder ?
Kann ich den Code evtl. noch anpassen, um hier einen höheren Wert
ausrechnen zu lassen ? Ich müsste den einen Wert von 3500 in der Basis
wenigstens mit der Potenz ^2 versehen können.
Erhöhe ich die Variable NUM_BITS kommen aber nur unsinnige Werte raus.
Vielen Dank,
Helge
Helge schrieb:> Erhöhe ich die Variable NUM_BITS kommen aber nur unsinnige Werte raus.
Du musst ggf. auch BIG_SIZE vergößern.
BIG_SIZE muss so groß sein, dass der Wert
mit 8·BIG_SIZE Bits darstellbar ist. Dabei ist b die Bitnummer des
höchstwertigen aller Nullbits des maximal möglichen Ergebnisses ymax in
NUM_BITS-Darstellung.
Beispiel: Es seien EXP_DENOM=5, das größtmögliche Ergebnis ymax=50000
und NUM_BITS=16. Dann hat ymax die Binärdarstellung 1100001101010000₂.
Das höchstwertige Nullbit ist Bit 13 (die dritte Ziffer von links). Das
größte Argument, das in der Funktion pow14 an big_pow übergeben
wird, ist
2¹⁶ - 2¹³ = 1110000000000000₂ = 57344,
der größte Funktionswert von big_pow ist
57344⁵ = 620068855293672868020224
Diese Zahl braucht in der Binärdarstellung mindestens 80 Bits oder 10
Bytes, also wählt man BIG_SIZE=10.
Ist BIG_SIZE zu klein, kann in big_mul ein Überlauf auftreten. Du
kannst diesen Überlauf mit den hier hinzugefügten zwei zusätzlichen
Codezeilen abfragen:
Vielen Dank für die rasche Antwort,
BIG_SIZE habe ich aber auch schon deutlich erhöht. Dabei ergeben sich
aber auch keine sinnvollen Werte, die Grenze in der Ausgabe sind bei mir
immer die 17 Bit bei der Berechnung des Endergebnisses.
Ich muss aber noch alles nochmal richtig nachvollziehen und Gegenrechnen
damit ich hier überhaupt mitreden kann, so richtig habe ich den Code
noch nicht kapiert.
Grüße,
Helge
Ich habe es jetzt geschafft mit den Variabeln BIG_SIZE = 30
NUM_BITS = 24 einen Basiswert von ca. 3000 mit einen Exponenten von
max.2 darzustellen. Der Code läuft also gut soweit, Danke nochmal !
