Eins durch x (1/x) Annäherung

Festkomma Division? Flotte Divisionsroutinen gibts bei Atmel. Falls du 
nen AVR benutzt.

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.

Dein Problem und Dein Ansatz ist nicht wirklich zu verstehen...

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.

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

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.

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

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.