Hallo, Welche Möglichkeit hätte ich, auf einem Mikrocontroller eine Annäherung für 1/x zu erhalten? Momentan nutze ich eine Wertetabelle, ich bin dadurch aber auf ein bestimmtes Verhältnis gebunden. Liese sich das auch irgendwie möglichst einfach berechen (Addition und Multiplikation sind kein Problem, Divisionen wären kritisch)? Der Wert muss nicht sonderlich genau sein, momentan nutze ich 16-Bit-Integer. Gleitkomma ist nicht machbar (Echtzeit)! Viele Grüße, Thorsten
thorsten schrieb: > Der Wert muss nicht sonderlich genau sein, momentan nutze ich > 16-Bit-Integer. Gleitkomma ist nicht machbar (Echtzeit)! Für eine Approximation ist es wichtig, den Wertebereich und den erlaubten Fehler zu wissen. Verrate uns mehr.
42 schrieb: > Für eine Approximation ist es wichtig, den Wertebereich und den > erlaubten Fehler zu wissen. Verrate uns mehr. Momentan sieht es so aus:
1 | 64260, 32130, 21420, 16065, 12852, 10710, 9180, 8032, 7140, 6426, |
2 | 5842, 5355, 4943, 4590, 4284, 4016, 3780, 3570, 3382, 3213, 3060, 2921, 2794, 2678, |
3 | 2570, 2472, 2380, 2295, 2216, 2142, 2073, 2008, 1947, 1890, 1836, 1785, 1737, |
4 | 1691, 1648, 1606, 1567, 1530, 1494, 1460, 1428, 1397, 1367, 1339, 1311, 1285, |
5 | 1260, 1236, 1212, 1190, 1168, 1148, 1127, 1108, 1089, 1071, 1053, 1036, 1020, 1004, |
6 | 989, 974, 959, 945, 931, 918, 905, 892, 880, 868, 857, 846, 835, 824, 813, 803, |
7 | 793, 784, 774, 765, 756, 747, 739, 730, 722, 714, 706, 698, 691, 684, 676, 669, |
8 | 662, 656, 649, 643, 636, 630, 624, 618, 612, 606, 601, 595, 590, 584, 579, 574, |
9 | 569, 564, 559, 554, 549, 545, 540, 536, 531, 527, 522, 518, 514, 510, |
Die jeweilige Zahl durch den Wert 170 ergibt das Ergebnis: 64260/170 = jede 378. Ausgabe wird übersprungen 510/170 = jede 3. Ausgabe wird übersprungen usw. Je nach Wert aus der Tabelle wird entweder ganz leicht bis zu genau einem Drittel aller Ausgaben übersprungen. Schön wäre es nun, so etwas auch zur Laufzeit einstellbar zu haben. Beispielsweise so, dass bei der höchsten Stufe ein Viertel oder gar die Hälfte übersprungen wird. Wie könnte man so etwas lösen?
Sieh dir doch mal die Berechnung an ob sich die nicht umstellen lässt. Dadurch lässt sich eine solche Division oftmals durch eine für Integerberechnung günstigerer Variante ersetzen. Eine solche Division ( egal ob 1/x oder y/x) ist auf µC ohne APU immer ungünstig und sollte wenn irgend möglich durch Multiplikation und Shiften ( division durch 2^x) ersetzt werden.
thorsten schrieb: > 64260/170 = jede 378. Ausgabe wird übersprungen Wenn es eine irgendwie geartete "Ausgabe" gibt, was spricht dagegen, bei jeder den Divisor abzuziehen und bei <= 0 wird übersprungen ?
Du teilst immer durch 170 ? In dem Fall wäre es so günstiger: #define factor1 = (2^16 / 170) // das rechnet der Preprocessor des Compilers aus und dann im code : ergebnis = ((x * factor1) >> 16) Dazu noch die passenden casts und variablengrößen.
MWS schrieb: > Wenn es eine irgendwie geartete "Ausgabe" gibt, was spricht dagegen, bei > jeder den Divisor abzuziehen und bei <= 0 wird übersprungen ? Ziel ist es mit jeder Stufe aus der Tabelle um einen ähnlichen Anteil mehr Ausgaben zu überspringen. Der Wert 170 ist dabei von mir verwendet worden um die 16 Bit des Integers möglichst weit ausnutzen zu können. (65535 / 378 = 173,3730) Es wird der Wert aus der Tabelle geladen und bei jeder Ausgabe wird 170 abgezogen. Ist das Ergebnis weniger als 170 wird die nächste Ausgabe übersprungen und wieder der Wert aus der Tabelle addiert. Durch die Beschaffenheit der mathematischen Funktion sind die Änderungen zwischen den ersten Stufen groß und dann immer kleiner werdend: 64260 ent. 178 32130 ent. 189 usw. 522 ent. 3,0706 518 ent. 3,0471 514 ent. 3,0235 510 ent. 3 Mein Problem ist, dass ich keine Bruchteile von Ausgaben überspringen kann. Momentan geht es mit der Wertetabelle ja auch ohne größere Rechnerei. Aber halt nur in einem festen Verhältnis und das würde ich eben gerne aufweichen. Aber wie?
Wüsste jetzt nicht, wie eine 1,1 fache "Ausgabe" bei gleicher Periode gehen soll. Das Gezeigte sieht mir wie der Versuch einer logarithmische Tabelle aus. Und wenn Du mit der Info was das werden soll, etwas freigiebiger wärst, dann bekämst Du sicher einfacher 'ne bessere Antwort.
Hallo, ich glaube dass jedem, der das bisherige gelesen hat, klar ist, dass die Zahl 1/x (für x = beliebiger Integer) nicht als Integer darstellbar ist! Das heisst dass man sich irgendwie eine Komma-Darstellung überlegen muss da man ja auch mit diesem Wert igendwann weiterrechnen will. Wenn eine Gleitkomma-Darstellung nicht geht dann überlegt man sich halt eine (eventuell vereinfachte) Festkomma-Darstellung. Eine einfache Variante einer Festkomma-Darstellung wäre dass man (um bei 16-Bit zu bleiben) die ganze Rechnung (Division) gedanklich mit den 2^16-fachen Werten durchspielt. Das Ergebnis, ein Integer, ist dann gleichzusetzten mit einem Festkomma-Wert auf 1/65536 genau. Die dazu nötige 16-bit Division lässt sich mit 16-Shift Operationen, 16 Vergleichen und 16 bedingten Subtraktionen durchführen. Gruss Stefan
MWS schrieb: > Wüsste jetzt nicht, wie eine 1,1 fache "Ausgabe" bei gleicher Periode > gehen soll. Das Gezeigte sieht mir wie der Versuch einer logarithmische > Tabelle aus. > Und wenn Du mit der Info was das werden soll, etwas freigiebiger wärst, > dann bekämst Du sicher einfacher 'ne bessere Antwort. Ich habe eigentlich nicht viel mehr Informationen zur Verfügung: Es gibt 126 Stufen der Ausgabe (Menge oder Geschwindigkeit wie man es halt auffasst), je nach Stufe sollen bestimmte Eingangswerte übersprungen werden und nicht zur Ausgabe gelangen. Also habe ich mir Gedanken gemacht, wie ich dies realisieren könnte. Aufgrund der 1/x-Geschichte war eine Wertetabelle daher mein erster Ansatzpunkt. Ich habe also gerechnet: 126 Stufen x 3 (Kehrwert von 1/3) = 378 (Höchster Wert) Davon wird nun je nach Stufe die Wertigkeit abgezogen und das Verhältnis mal 170 gesetzt. Ich habe folgenden Code zur Bestimmung der Werte der Tabelle genutzt: (Visual C#)
1 | double[] test = new double[127]; |
2 | |
3 | for (int n = 1; n <= 127; n++) |
4 | {
|
5 | int skipfrom = 379 - n; |
6 | int skipmaximum = 378; |
7 | int delta = skipmaximum - skipfrom; |
8 | double ratio = (double)skipmaximum / (double)delta; |
9 | |
10 | ratio *= 170; |
11 | ratio = Math.Round(ratio); |
12 | |
13 | test[n - 1] = ratio; |
14 | }
|
Damit funktioniert es ja. Aber wenn ich jetzt beispielsweise nicht 1/3 sondern nur 1/4 haben wollte, müsste ich die sämtlichen festen Werte ändern und bräuchte eine komplett andere Wertetabelle. Genau das ist mein Problem. Die Eingabe, die Ausgabe, das Überspringen der Werte anhand des "Abzieh"-Algorithmus usw. funktioniert wie gewünscht. Nur das feste Verhältnis stört mich nun. Ich wäre ja schon zufrieden, wenn ich anhand eines einfachen Algorithmus die Wertetabelle zur Laufzeit bestimmen könnte. So gäbe es nur einmal beim Einschalten den Rechenaufwand und der Rest könnte so ablaufen wie jetzt auch. Nur halt anstatt der 170 einen anderen Schwellenwert und natürlich andere Werte in der Tabelle. Es hakt quasi "nur" daran, weiterhin dieses exponentielle Verhalten zu erreichen.
MWS schrieb: > Wüsste jetzt nicht, wie eine 1,1 fache "Ausgabe" bei gleicher Periode > gehen soll. Das Gezeigte sieht mir wie der Versuch einer logarithmische > Tabelle aus. Doch, durch die Tabelle geht das ja. Über die Zeit gemessen werden im Beispiel 514 / 170 = 3,0235 im Falle von einer Million Eingabewerten halt 330.739 Werte übersprungen, der Rest wird ausgegeben. Teilt man 1.000.000 / 330.739 erhält man wieder 3,0235. Quasi zeitlich integriert. Pro Wert kann man natürlich nicht 1,1 verwerfen oder ausgeben, aber über die Summe stimmt es dann wieder. Daher ja auch die feste Multiplikation mit 170 um den Zahlenbereich der 16 Bit möglichst weit auszuschöpfen und so den Fehler zu minimieren. Mit 32 Bit ginge es natürlich noch genauer, aber das wäre zu viel des Guten.
thorsten schrieb: > Es gibt 126 Stufen der Ausgabe (Menge oder Geschwindigkeit wie man es > halt auffasst), je nach Stufe sollen bestimmte Eingangswerte > übersprungen werden und nicht zur Ausgabe gelangen. So was
1 | in = [ 1 2 3 4 5 6 7 8 9 ... 1000 1001 ...] |
2 | 1/2 ^ ^ ^ |
3 | 1/3 ^ ^ ^ |
Warum geht dann einfaches Abzählen nicht? Festkommaarithmetik (einfache Addition)
Ich verstehe Thorstens Anliegen auch nicht, aber der Kehrwert der Zahl aa berechnet sich iterativ so: x(k+1)=x(k)*(2-aa*x(k)) Das geht schnell und gut,anfangen mit x(0)=aa. Für integer geeignete Skalierung verwenden. Cheers Detlef
Kann es sein daß das was du versuchts zu beschreiben im Verhalten einem Phasenakku eines DDS-Generators entspricht. Also je größer der Eingangswert desto kleiner die Periodendauer? Gruß Anja
detlef_A schrieb: > Ich verstehe Thorstens Anliegen auch nicht, aber der Kehrwert der Zahl > aa berechnet sich iterativ so: > > x(k+1)=x(k)*(2-aa*x(k)) > > Das geht schnell und gut,anfangen mit x(0)=aa. Für integer geeignete > Skalierung verwenden. Bzw. wenn Abzählen möglich ist und Festkomma verwendet wird
1 | Init: fk = Festkomma-Kehrwert berechnen |
2 | cnt = 1 in der gewählten Festkomma-Darstellung |
3 | Loop: |
4 | cnt = cnt - fk |
5 | if (cnt <= 0) ... |
Statt einer Kostanten von einer per Tabelle errechneten Variablen, zieh' doch eine Variable von einer Konstanten ab. Die Variable kannst Du dynamisch per Multiplikation erzeugen.
>Gleitkomma ist nicht machbar (Echtzeit)!
Was auch mal nix miteinander zu tun hat. Echtzeit: garantierte
Abarbeitung im Zeitinterval i. Echtzeit muss nicht zwangsläufig
schneller sein als nicht-Echtzeit, garantiert nur die Verarbeitungszeit.
Anja schrieb: > Kann es sein daß das was du versuchts zu beschreiben im Verhalten einem > Phasenakku eines DDS-Generators entspricht. > > Also je größer der Eingangswert desto kleiner die Periodendauer? Nein, der Eingangswert beeinflusst nicht die Ausgabefrequenz. Es ist viel mehr so, dass die Werte mit einer festen Frequenz abgetastet werden, jedoch nur in einer variablen Ausgangsfrequenz weiterverarbeitet werden können. Variabel heißt in diesem Falle abgestuft mit 126 Stufen. Wie könnte man das beispielhaft beschreiben? Angenommen wir hätten einen MP3-Player, der Audiodaten mit 60 kHz wiedergeben wollte, die Samplerate zum Verstärker hin jedoch zwischen 60 kHz und 40 kHz variieren könnte (um mein Beispiel mit 1/3) aufzugreifen. Am PC wäre so etwas kein Problem. Lineare Interpolation und das Problem ist vom Tisch. Aber hier habe ich ja das Problem, dass die Daten, anders als Audiodaten in einem MP3-Player, kein Anfang und kein Ende haben. Das Verhältnis muss also kontinuierlich ausgegeben werden. Arc Net schrieb: > So wasin = [ 1 2 3 4 5 6 7 8 9 ... 1000 1001 ...] > 1/2 ^ ^ ^ > 1/3 ^ ^ ^ > > Warum geht dann einfaches Abzählen nicht? Festkommaarithmetik (einfache > Addition) Vielleicht stehe ich gerade wirklich auch einfach nur auf der Leitung, aber so einfach erscheint mir das nicht. Angenommen ich lege fest, dass ich in der höchsten Stufe jeweils jeden dritten Wert verwerfen will (also ein Drittel), dann habe ich doch: Stufe 1: 1/378, Stufe 2: 2/378, Stufe 3: 3/378... Stufe 126: 126/378 (genau ein Drittel) Will ich nun aber nur jeden fünften Wert verwerfen (also ein Fünftel), dann hätte ich doch: Stufe 1: 1/630, Stufe 2: 2/630, Stufe 3: 3/630... Stufe 126: 126/630 (genau ein Fünftel) Da nicht der Nenner dieses Bruchs variabel ist (der geht ja immer nur von 1 bis 126), sondern der Zähler (nämlich 126 * (Anteil der zu verwerfenden Werte) ^ -1) tue ich mich ja gerade so schwer. detlef_A schrieb: > Ich verstehe Thorstens Anliegen auch nicht, aber der Kehrwert der Zahl > aa berechnet sich iterativ so: > > x(k+1)=x(k)*(2-aa*x(k)) > > Das geht schnell und gut,anfangen mit x(0)=aa. Für integer geeignete > Skalierung verwenden. Der Kehrwert an sich nützt mir ja nicht viel. Da kämen ja wieder Zahlen wie 3,xxxx heraus. Wie bekomme ich diesen Wert so skaliert, dass ich die so errechneten Werte in die Tabelle übernehmen kann? Ohne Look-Up-Table komme ich sowieso nicht aus, dafür kommen die Werte viel zu schnell, daher wäre eine einmalige Rechnung zu beginn nicht das Problem.
thorsten schrieb: > Der Wert muss nicht sonderlich genau sein, momentan nutze ich > 16-Bit-Integer. Gleitkomma ist nicht machbar (Echtzeit)! Der PIC24F(V)32KA macht eine 32/16 Bit Division in 19 Takten also etwas mehr als 1us. Andere Prozessoren sind noch schneller. Gruß Anja
thorsten schrieb: > Ohne Look-Up-Table komme ich sowieso nicht aus, dafür kommen die Werte > viel zu schnell, daher wäre eine einmalige Rechnung zu beginn nicht das > Problem. Also doch DDS-Phasenakku. auf Stufe 1 addierst du für jeden Eingangsmeßwert immer den Wert 173 (eigentlich 173,375...) auf ein 16-Bit Summen-Register. Jedesmal wenn Du einen Überlauf kriegst (CY-Bit gesetzt) verwirfst Du den Meßwert, ansonsten wird er weiter gegeben. Jeder 378. Wert wird nicht ausgegeben. auf Stufe 126 wird immer 126 * 173(,375) = 21845 addiert. Jedes 3. mal entsteht der Überlauf. Das sollte jeder Prozessor der Hardware-Multiplikation hat in maximal 10 Takten schaffen. Gruß Anja
thorsten schrieb: > Angenommen ich lege fest, dass ich in der höchsten Stufe jeweils jeden > dritten Wert verwerfen will (also ein Drittel), dann habe ich doch: > > Stufe 1: 1/378, Stufe 2: 2/378, Stufe 3: 3/378... Stufe 126: 126/378 > (genau ein Drittel) > > Will ich nun aber nur jeden fünften Wert verwerfen (also ein Fünftel), > dann hätte ich doch: > > Stufe 1: 1/630, Stufe 2: 2/630, Stufe 3: 3/630... Stufe 126: 126/630 > (genau ein Fünftel) Wenn ich dich richtig verstanden habe, willst du einen Eingabedatenstrom so ausdünnen, dass jeweils k von n Werten übersprungen werden und das möglichst gleichmäßig. In Stufe 3 des ersten Beispiels wäre also k=3 und n=378. Wenn die Eingabewerte forlaufend mit 1, 2, 3, 4, 5 ... durchnummeriert sind, erwartest du in diesem Fall, dass die Werte Nr. 126, 252, 378, 504 usw. übersprungen werden. Ist das so richtig? Wenn ja, brauchst du dazu weder Divisionen noch Multiplikationen noch Festkommaarithmetik. Anjas Phasenakku zielt schon in die richtige Rich- tung, ein ähnliches Prinzip wird auch beim Rastern von Linien in der Computergrafik angewandt (Bresenham-Algorithmus). So geht's:
1 | #include <stdio.h> |
2 | |
3 | unsigned int dummy_input() { |
4 | static unsigned int wert; |
5 | |
6 | return ++wert; |
7 | }
|
8 | |
9 | void dummy_output(unsigned int wert) { |
10 | printf("%d ", wert); |
11 | }
|
12 | |
13 | int main(void) { |
14 | int k = 3, n = 378; // es sollen jeweils k von n Werten übersprungen werden |
15 | unsigned int wert; |
16 | int sum; |
17 | |
18 | sum = 0; |
19 | for (;;) { |
20 | wert = dummy_input(); // Wert einlesen |
21 | if ((sum += k) < n) |
22 | dummy_output(wert); // Wert ausgeben |
23 | else
|
24 | sum -= n; // Wert überspringen und Summe zurücksetzen |
25 | }
|
26 | printf("\n"); |
27 | return 0; |
28 | }
|
Anja schrieb: > thorsten schrieb: >> Ohne Look-Up-Table komme ich sowieso nicht aus, dafür kommen die Werte >> viel zu schnell, daher wäre eine einmalige Rechnung zu beginn nicht das >> Problem. > > Also doch DDS-Phasenakku. Danke! Mir war der Begriff DDS-Phasenakku nicht geläufig. Ich muss aber auch dazu sagen, dass ich mit solchen Samplewert/Messwert-Geschichten bisher noch nie etwas zu tun gehabt hatte! Daher habe ich vermutlich direkt eine zu komplizierte Lösung vor Augen gehabt. Dank deiner Rechnung habe ich es aber nun verstanden. Ein Glück. Es ist im Prinzip immer nur einmalig 65535/(126*Verhältnis^-1) zu rechnen. Das Ergebnis wird dann jeweils mit der Stufe multipliziert und schon ist der Rest klar. Jetzt habe ich sogar auch noch die Wertetabelle eingespart. In der Tat, die Multiplikation ist überhaupt kein Problem. Ich nutze ebenfalls PIC24.
Yalu X. schrieb: > Wenn ich dich richtig verstanden habe, willst du einen Eingabedatenstrom > so ausdünnen, dass jeweils k von n Werten übersprungen werden und das > möglichst gleichmäßig. > > In Stufe 3 des ersten Beispiels wäre also k=3 und n=378. Wenn die > Eingabewerte forlaufend mit 1, 2, 3, 4, 5 ... durchnummeriert sind, > erwartest du in diesem Fall, dass die Werte Nr. 126, 252, 378, 504 usw. > übersprungen werden. > > Ist das so richtig? Ja, genau so habe ich das gemeint. Hatte ich mich zu undeutlich ausgedrückt? Das tut mir Leid! > Wenn ja, brauchst du keine Divisionen, nicht einmal Multiplikationen. > Anjas Phasenakku zielt schon in die richtige Richtung, ein ähnliches > Prinzip wird auch beim Rastern von Linien in der Computergrafik ange- > wandt (Bresenham-Algorithmus). Du brauchst dazu nicht einmal Festkom- > maarithmetik: Dein Code entspricht ja ungefähr dem, was ich bisher realisiert hatte. Bloß umständlicher durch die Wertetabelle und der Multiplikation mit 170. Es scheiterte nur daran zu erkennen, dass dies prinzipiell mit allen möglichen Verhältnissen funktioniert... Danke, dass du dir die Mühe mit dem Code gemacht hast! Du hast natürlich Recht, es geht sogar mit einfachem Addieren und Vergleichen. Immerhin: Für die Zukunft passiert mir dieser Fehler garantiert nicht mehr.
Bitte 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.