Интерполация

Казваха ми да уча математика, ама понеже съм си твърдоглав...
Имам нужда от бърз интерполиращ алгоритъм, за следната постановка:
Имаме асоциативен масив, където индексите са цели, непоследователни числа. Всяка клетка съдържа стойност, получена по някаква неизвестна функция от индекса. Трябва ми алг. който да смята междинни стойности в зависимост от индекса. Т.е. ако в клетка с индекс 1 има стойност 1, а в съседната клетка с индекс 10 има стойност 100, то на индексът 5 ще отговаря стойност 50, на индекс 7 - 70 и т.н. Дайте някви идеи.

Хм... само да питам
От каква степен искаш да ти е функцията между възлите, колко възела ще използваш при интерполацията...

Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...

dvoichno tyrsene i sled tva lineina interpolaciq.

Той човека си каза, че от математика не разбира :)

Тъй като още казва, че функцията е неизвестна (wtf?!) и дава пример само с 2 възела - да метне там една линейна интерполация за по-лесно :)

Реконструктор:

Нещо от вида:

Ако 2-та ти възела са А[a] и А[ b] - A[c] (a < c < b) = A[a] + (c - a)*(A[ b ]-A[a]) / (b - a)

Какво ще рече "възел"? Пълен чайник съм по тия въпроси, не ме ритайте силно.
По принцип, имам нещо сътворено по метода на пробите и грешките, но е боза, която не работи добре при гранични стойности и като капак е доста бавна. Ще се опитам да я опиша, дано стане по-ясно какво се иска.
Първо смятаме абс стойност на разликата на индексите. В конкретния пример = 9. Добавяме 1, щото търсим броя на "междинните" клетки = 10. После намираме разликата и в стойностите, в конкр. случай = 99. После делим 99/10=9.9, което е стъпката. И накрая умножаваме по търсения индекс, да речем 5 - 5*9.9 = 49.5
1. Може ли да се избегне деленето.
2. Понеже индексите може да са както си искат, напр. 1, 10, 3, 2, 15 може ли да се избегнат условните преходи, които възникват.

Аха, ясно какво е възел. Горе-долу май прилича на мойто.

Начи ако двата различни индекса са ти x0 и x1 със стойности в тях y0 и y1, линейната ( нема по-бързо ) интерполация се праи така:

dy = y1-y0
dx = x1-x0

y(x) = y0 + (dy/dx) *(x-x0)

Само внимавай с тва dy/dx. Ако си с плаващи числа немаш грижи. Ако си в цели първо прасни умножението по (x-x0) и после дели на dx. Ако има опасност от препълване ша требе да го напраиш с плаващи.

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Никой няма да те рита
Хората са ти отговорили вече за линейната интерполация.
Ако ти върши работа (предполагам, че да, а и е най-бързо), давай!
Възли:
Най-често се говори за функция y на променлива x. Известни са (от някъде) стойностите yi във възлите xi (при теб индекси). Търсиш стойност на функцията в произволна точка в интервала [min{xi}, max{xi}] (интерполация).
Какво правиш зависи от конкретната реална задача, точността, която гониш, бързина и т.н.
Пиша ти ги тези неща, защото искам да се чувствам полезна
Не знам до колко ти трябват, а и вече ти отговориха.
Успех.

Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...

Да, ама не става съвсем както искам. Да погледнем отново конкретния случай, търсим стойност при индекс 9:

dx = 9
dy = 99

y(x) = 1 + (99/11) * (9-1) = 1+9*8 = 73

а трябва да е 90. При индекс 10 резултата е 82, а трябва да е 100.

Начи тия неща не съм ги правил повече от година и явно съм ги позабравил, противно на това което си мислех :-)))))

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Ама ти женско ли си?

Ай, ся. Две жени са си признали, че са жени и ти да не ги знаеш.

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Това е по-близо до истината.
1+(9-1)*(100-1)/(10-1) = 1+8*99/9 = 89
И при индекс 10 се получава точно 100.
Това ще да е формулата!

Добре, след като открихме истината за едното измерение, да преминем в двумерния свят, щото тъкмо това ми трябва...

Едната я знам бе, нали се ебавам редовно с нея. За другата ся научих, че е женска.

Мойто е 1:1 с това дето викаш, че ставало.
Написал си:

y(x) = 1 + (99/11) * (9-1) = 1+9*8 = 73

а то е

y(x) = 1 + (99/9) * (9-1) = 1+11*8 = 89


За 2D най просто хвани и направи същата сметка по другата ос и вземи средното. Става билинейна интерполация. Лошото е, че картинката придобива вид на квадратчета. Но ползата е, че може да се направи инкрементална стъпка и тогава м/у две точки ако имаш 10-тина стойности само първата ще трябва да изчисляваш сложно, а останалите само с няколко събирания.

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

А ако искаш кръгли числа трябва да хванеш по-подходящи стойности за интерполация. Не може в 1 да имаш 1 и да искаш в 2 да имаш 20 и в 7 - 70. Ясно, че за да ти е равна сметката в 1 трябва да имаш 10 по общата логика.

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

по принцип не е важно да са кръгли, а да са верни.

Ха, и ти ме учуди...
И сега какво? И с мен ли ще се ебаваш?:)

Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...

Ми ако в 1 имаш 1 и в 10 имаш 100, то вярно е в 9 да имаш 89, а не 90 както си мислиш.

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_