Forum: Compiler & IDEs schnelle Indizessberechnung für Array auf Mikrocontroller


von G. B. (geri)


Angehängte Dateien:

Lesenswert?

Hallo zusammen

Ich habe einen Wert x und möchte daraus den Index in einer Datentabelle 
berechnen.

Zwischen dem Wert x und dem Arrayindex besteht allerdings kein linearer 
Zusammenhang (siehe Bild). Das positive ist aber, dass die Kurvenform 
keine grosse Rolle spielt. Es besteht höchstenfalls die Notwendigkeit, 
dass die Indizesse am Anfang rascher wechseln als jene bei grösseren 
x-Werten.
Die Berechnung läuft in einer Schleife, der vorheriger Wert Index_n 
liesse sich problemlos zwischenspeichern.

Aktuelle Lösungen:
- Diese Kurve gleicht z.B. einer Wurzelfunktion oder einer e-Funktion. 
Letztere liesse sich durch eine Näherung abbilden. Man könnte vielleicht 
auch mir einer zweiten Tabelle arbeiten:)

- Man könnte auch eine grössere Tabelle verwenden (Problem, grosser 
Speicherbedarf)

Interessieren würde mich wie ihr so eine Berechnung durchführen würdet.

Beste Grüsse

Geri
..letzlich geht es mir darum, an Anfang die Empfindlichkeit zu erhöhen.

von Rolf Magnus (Gast)


Lesenswert?

Ein guter Kompromiss zwischen Rechenlast und Speicherverbrauch wäre eine 
Tabelle mit wenigen Stützstellen und eine lineare Interpolation 
dazwischen.

von Falk B. (falk)


Lesenswert?

@ Gerhard Burger (geri)

>Ich habe einen Wert x und möchte daraus den Index in einer Datentabelle
>berechnen.

Mann könnte die Tabelle erweitern und jweiels den zugehörigen Wert X 
abspeichern. Sind dann halt 512x4 Bytes mehr. Hmm. Daraus kann man dann 
per Teile undhersche schnell den zugehörigen Einrag finden.
Wozu soll das denn gut sein und wie oft muss die Funktion berechnet 
werden?

MFg
Falk

von Jan M. (mueschel)


Lesenswert?

Der f = log2(x) laesst sich auch recht einfach annaehern:

1. Hoechstes gesetztes Bit in x bestimmen
2. Ergebnis f = 2^a * #Bitnummer (a so waehlen, dass du den gewuenschten 
Wertebereich bekommst)
3. Je nach geforderter Genauigkeit kannst du jetzt schon linear 
approximieren: Die niedrigeren Stellen in f werden mit den 
naechstniedrigeren Bits aus x aufgefuellt.

von G. B. (geri)


Lesenswert?

Hallo Rolf

Vielen Dank für Deinen Tipp!

Diese Lösung habe ich auch schon in Erwägung gezogen.  Entschuldige 
bitte, dass sie oben nicht genannt wurde.

Danach ergäbe sich ja der Index dann ja aus (für die im Beispiel 
genannte Grafik)

Xn= x * 512/300000

mit y= k * x + d

k = (Yn+1 - Yn-1) / (Xn +1 - Xn-1);
d = (Yn-1 * xn+1 - Yn+1 * Xn-1) / (Xn+1 - Xn-1);
Index = k * Xn + d;

Dieses Verfahren habe ich ausgeschlossen weil mir der Rechenaufwand 
etwas gross erscheint.

... aber vielleicht würdest du die Berechnung viel effizieter gestalten 
wie ich ...


Die Schleife muss bei diesem Beispiel 300.000 mal durchlaufen werden

Beste Grüsse

Geri

von G. B. (geri)


Lesenswert?

Hallo Jan

Auch eine sehr interessnte Lösung, vielen Dank! Wenn ich Deine 
Überlegungen richtig interpretiere, würde die Indexberechnung dann in 
etwas so aussehen?

Schritt 1: Höchstes Bit in x bestimmen:

Mask   = 0x80000000;
Approx = 0xFFFFFFFF;
for (i=31; i>=0; i--)
{
   if (x & Mask) != 0) break;
   Mask = Mask >> 1;
   Approx = Approx >> 1; // für Schritt 3
}
in i steht nun der Index

Schritt 2: Index f berechnen

f = Faktor * i;   // Faktor = 2 ^a ??

Schtritt 3: Erhöhung der Genauigkei durch lineare Approximation

f = f | Approx; // ???


Habe ich das so bitte richtig verstanden? Wieso sollte der Bereich in 
2^a passen? Ergibt sich daduch noch eine deutliche Vereinfachung?

Beste Grüsse

Geri

von Jan M. (mueschel)


Lesenswert?

Die Multiplikation mit 2^a solltest du machen, sonst wird es schwieriger 
die lineare Approximation zu machen (bei 2^a weisst du immer genau, 
welche Bits betroffen sind, bei anderen Multiplikationen nicht)
Der Wertebereich muesste dann 2^a * log2(Bitanzahl) sein.
Ob das mit dem ODER am Ende stimmt, musst du noch schauen. Die oberen 
ceil(log2(Bitanzahl)) Bits im Ergebnis duerfen jedenfalls nicht 
geaendert werden bzw nur die unteren a Bits duerfen geaendert werden.


Vielleicht sieht man es so:
k = Nummer des hoechsten gesetzten Bits in x
x(s): Das Bit s aus x

Dann sind die einzelnen Stellen des Ergebnisses
k  (x(k-1)  x(k-2)  ...  x(k-1-a))

Wenn dir das lineare noch nicht reicht, wiederholst du den Vorgang mit 
den restlichen Bits. a muss dann natuerlich nochmal anders gewaehlt 
werden.

von G. B. (geri)


Lesenswert?

Hallo Falk

Vielen Dank für Deinen interessanten Tipp. Habe ihn erst jetzt gesehen:)

512 Byte * 4 sind etwas viel, man könnte aber vielleicht die Tabelle auf 
128 Werte reduzieren. Dementsprechende auch die Indexwerte. Die 
Anforderungen an die Genauigkeit der Kurve sind nicht hoch.

"Deine Tabelle mit den x-Werten und den zugehörenden-Tabelle" liesse 
sich vielleicht auch reduzieren, wenn man den Wert x um 16 bit schiebt, 
dann wären es für x nur mehr 512*2 Byte.

Wie würde dann aber bitte die Berechnung des Index erfolgen. Müsste man 
in einer Schleife nach dem passenden x suchen? Successive Approximation?

Die Schleife läuft wird für jedes x ein mal ausgeführt. Bei diesem 
Beispiel 300.000 mal.

Beste Grüsse

Geri

von Falk B. (falk)


Lesenswert?

@ Gerhard Burger (geri)

>"Deine Tabelle mit den x-Werten und den zugehörenden-Tabelle" liesse
>sich vielleicht auch reduzieren, wenn man den Wert x um 16 bit schiebt,
>dann wären es für x nur mehr 512*2 Byte.

Das geht nicht, weil die Kurve ziemlich nichtlinear ist. Man kann eher 
noch auf 24 Bit/Wert ausweichen, aber dann wird die Datenverwaltung ein 
wenig aufwendiger (Struct).

MfG
Falk

von Arc N. (arc)


Lesenswert?

> Wie würde dann aber bitte die Berechnung des Index erfolgen. Müsste man
> in einer Schleife nach dem passenden x suchen? Successive Approximation?

DAC wurde schon genannt. Hier in Gestalt der binären Suche.
Die Tabelle könnte dann bspw. für x < 1000 deutlich mehr Stützstellen 
enthalten als für x >= 1000.
Genauso gut könnte man auch mehrere Tabellen nehmen, bei denen man dann 
nur noch die entsprechenden High, Low oder Mid-Bytes in der Tabelle 
speichern müsste. Z.B. Tab1 0 <= x <= 255, Tab2 256 <= x <= 65535 etc. 
(falls die Genauigkeit dann noch reicht)

von G. B. (geri)


Lesenswert?

Hallo zuammen

Euch allen nochmals vielen Dank für die sehr interessanten Lösungen!


@Falk:
Ich habe Deine Lösung so interpretiert, dass man Wertepaare x und den 
dazugehörenden Index speichert. Die x-Werte werden nicht linear, aber 
aufsteigend sortiert abgelegt. Ich denke, die Indexberechnung müsste man 
dann halt durch einen Vergleich des aktuellen x-Wertes mit dem aktuellen 
x-Wert des Arrays vergleichen und falls kleiner den Index erhöhen. Also, 
eine Mischung aus Deiner Tabelle, wenigen Stützstellen nach Rolf Magnus, 
dann käme man sogar mit erträglichen Speicherbedarf.

Beste Grüsse

Geri

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
Noch kein Account? Hier anmelden.