Interpolation in C

Dein erstes Ziel muss es sein, die beiden
Tabellenindizes zu finden, zwischen denen
der gesuchte Index liegt.

Bei einem Eingabewert von 10, sind für dich
die Tabellenindizes 1 und 2 interessant.

   low  = ( 10 / 4 ) - 1  -> 1
   high = ( 10 / 4 )      -> 2

Etwas Vorsicht musst du am Anfang und am Ende
der Tabelle walten lassen.

D.h. dein gesuchter Wert liegt irgendwo zwischen
Suchfeld[1] und Suchfeld[2].
Nur wo genau.
10 / 4 -> 2.5
Die 2 haben wir schon berücksichtigt. Bleiben noch die
0.5. Dein gesuchter Wert liegt also genau in der Mitte
zwischen Suchfeld[1] und Suchfeld[2]

Mit Kommazahlen wollen wir nicht rechnen, also
holen wir uns mal den Rest der Division:

   t = 10 % 4       -> 2

und interpolieren

  Wert = Suchfeld[low] + ( Suchfeld[high] - Suchfeld[low] ) * t / 4;

in Zahlen

   Suchfeld[1]  -> 2
   Suchfeld[2]  -> 6

   2 + ( 6 - 2 ) * 2 / 4

   2 + 4 * 2 / 4

   2 + 2

   4


Bis auf den Fall, dass die erste Division eine 0 für high
ergibt und es daher keinen low Index gibt, brauchst du kein
einziges if.

Bei der Interpoleration ist die gewichtung ziemlich wichtig, daher 
sollte man mit kommazahlen arbeiten,..
pseudo:
double i2= (double) input
double ret= i2/N (N anzahl der tabelleneinträge
double i3=floor(ret)

fkt void* d2i(int i) return i
int i4 =d2i(i3)

lineare gewichtung:
double m=(table[i4]-table[i4+1])/(i3-(i3+1))
double n=table[i4]-m*i3
return (m*ret+n)

>edit:
>grüüße

Mark Toellner wrote:
> Danke für die schnelle Antwort!
>
> Ich denke ich habe meinen Denkfehler erkannt!
> Der Modulooperator war der Schlüssel!
>
> Ich denke es muß so richtig sein:
> Da Integer immer Abgerundet werden!?
>
>    low  = ( 10 / 4 )      -> 1
>    high = ( 10 / 4 ) +1   -> 2
>

Hätte ich auch gedacht.
Aber dann stimmen deine in der Fragestellung
genannten Zahlen nicht mehr:

const unsigned int SuchFeld[265] = {
1            // Index 1
2            // Index 2
6            // Index 3

Und du sagst dass der Wert für 10 bisher bei dir 6
war.

Was jetzt richtig ist, kannst nur du sagen.

Wenn ich, für mich einfach mal die Ausgangswerte zu den
Arrayelementen dazuschreibe

const unsigned int SuchFeld[265] = {
1,   // 0, 1, 2, 3
2,   // 4, 5, 6, 7
6,   // 8, 9, 10, 11
11,  // 12, 13, 14, 15

dann ist der korrekte Wert für 10 irgendwo zwischen
6 und 11, nämlich ( 6 + 11 ) / 2 = 8. Du sagtest aber in deiner 
Fragestellung, dass 4 richtig wäre


:-)

Kai Scheddin wrote:
> Bei der Interpoleration ist die gewichtung ziemlich wichtig, daher
> sollte man mit kommazahlen arbeiten,..

Nicht wenn man es richtig macht und das Ergebnis wieder
im Ganzzahl-Bereich liegen soll/muss.

Mark Toellner wrote:
> Da Integer immer Abgerundet werden!?

Da muss ich noch nachhaken.

Sie werden nicht abgerundet. Die Nachkommastellen
werden abgeschnitten.

Bei positiven Zahlen macht das keinen Unterschied.
Bei negativen schon.

-3.6   abgerundet         -4
       kommastellen weg   -3

Dirk wrote:
> Auf einem 8Bit Controller so eine Lappalie mit double rechnen...
> Verrückte Welt heutzutage, tzzzz

:-)

Noch dazu beinhart alles in double.
Wenn er wenigstens nur die letzte Division in double
gemacht hätte, hätte ich ja noch Verständnis dafür.

Möglich ist es schon.
Nur vermeidet man das wenn es nicht absolut notwendig ist.

Über den Daumen gepeilt würde ich mal sagen, dass floating
point auf einem 8 Bit Mikro mindestens um einen Faktor 10
langsamer ist.

Karl heinz Buchegger wrote:
>Nicht wenn man es richtig macht und das Ergebnis wieder
>im Ganzzahl-Bereich liegen soll/muss.
ja gut, je nach aufgabenstellung, und aus welchen Körper die werte 
sind,..

zu dem double, habe ja extra pseudo darüber geschrieben,
man kann ja auch mit 8bit fließkomma arbeiten
entweder rund 0.00->255.99 oder rund +-128.99 (oder so ähnlich)

grüüße