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.
:
Bearbeitet durch Moderator
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 ?
Angehängte Dateien:
-
x_hoch_1.4.png
2 KB
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.
Ein Beispiel für die lineare Interpolation Sei
Willst du nun den Wert für
rausfinden, rechnest du:
Damit ist
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.
:
Bearbeitet durch Moderator
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.
Vielleicht mal im Fenster hochscrollen? Oder das Fenster größer machen?
Das hilft leider auch nicht. Ich hatte es (bei einer Vorgängerversion ?) schon mal in der Anzeige, aber hier hilft auch das hochscrollen nicht.
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:
1 | static void big_mul(big_t big, uint32_t n) { |
2 | static big_t sum; |
3 | uint16_t tmp; |
4 | uint8_t i, j; |
5 | |
6 | memset(sum, 0, BIG_SIZE); |
7 | for(i=0; i<4; i++) { |
8 | tmp = 0; |
9 | for(j=i; j<BIG_SIZE; j++) { |
10 | tmp += sum[j] + big[j-i] * (uint8_t)n; |
11 | sum[j] = (uint8_t)tmp; |
12 | tmp >>= 8; |
13 | }
|
14 | |
15 | if(tmp) // Überprüfung |
16 | printf("Overflow\n"); // auf Überlauf |
17 | |
18 | n >>= 8; |
19 | }
|
20 | memcpy(big, sum, BIG_SIZE); |
21 | }
|
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
Poste doch mal ein Beispiel, bei dem die Ergebnisse fehlerhaft sind.
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 !
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.