And now, for the sake of absurdity, here is the 7th-degree polynomial for four points which fixes x[-1], x[0], x[1], x[2], x'[0], x'[1], x''[0], and x''[1].
easy-to-read:
/*a7 = 1.25f*(b-c)+(5.f/12.f)*(d-a);*/ a7 = 1.25f*(b-c)+0.4166667f*(d-a);
a6 = 3.5f*a7; a5 = 2.1f*a7; a4 = a6; a3 = 3.1f*a7; a2 = 0.5f*(c+a)-b; a1 = 0.5f*(c-a); a0 = b;
*out++ = ((((((a7*frac-a6)*frac+a5)*frac+a4)*frac-a3)*frac+a2)*frac+a1)*frac+a0;
or somewhat optimized:
a7 = 1.25f*(b-c)+0.4166667f*(d-a); a4 = 3.5f*a7; a2 = 0.5f*(c+a)-b; a1 = 0.5f*(c-a);
*out++ = ((((((a7*frac-a4) * frac+2.1f*a7) * frac+a4) * frac-3.1*a7) * frac+a2) * frac+a1) * frac+b;
13 +'s and 14 *'s
Please test my algebra if you like, but I think it's right. It starts to get a little wobbly when there are more than two points in the same direction, which is to be expected (you can try with the 4-point table generated by the cosinesum method to an array, which makes 4 points and 3 guard points for a total of 7, to see the wobble). I worry that the oscillation will start to go nuts with the higher orders of polynomial -- I'd wonder if a six-point interpolation would gain much over a four-point, but we'd have to test... it might be worth investigating something other than the various kinds of polynomial interpolation, though.
If we find that some of these vastly outperform others for various tasks, it would be good to try to optimize the formulas as much as possible -- the formula in the current [tabread4~] in Pd is rather hard to read, but it's pretty efficient... we might be able to do something similar with these others.
Thanks,
Matt
PS -- Charles, you probably needn't spend your time analyzing this one, as it would most likely be a curiosity rather than anything usable.
On Sat, Jun 28, 2008 at 12:46 PM, Matt Barber brbrofsvl@gmail.com wrote:
On Sat, Jun 28, 2008 at 7:43 AM, cyrille henry cyrille.henry@la-kitchen.fr wrote:
Matt Barber a écrit : ...
The following bit of code might work to that end as a test, borrowing Cyrille's general notation:
cminusb = c-b; aminusd = a-d;
a0 = aminusd + 3.0 * cminusb; a1 = -2.5f * aminusd - 7.5f * cminusb; a2 = 1.5f * aminusd + 4.5f * cminusb; a3 = 0.5f * (c + a) - b; a4 = 0.5f * (c - a); a5 = b;
*out++ = ((((a0*frac+a1)*frac+a2)*frac+a3)*frac+a4)*frac+a5;
ok, i'll try that. but i don't think adjusting the 2nd derivative is the best thing to do. for me, having a 6 point interpolation would be more important.
well, we will see...
This would work, as well. Changing the coefficient order to match the previous code (sorry I bollixed that up before). a4 and a3 are simple ratios of a5, but keeping a2 as explicitly the fourth coefficient... dropping a0, aminusd, and cminusb:
a5 = a - d + 3.0f * (c - b); a2 = 0.5f * (c + a) - b; a1 = 0.5f * (c - a);
*out++ = ((((a5*frac-2.5f*a5)*frac+1.5*a5)*frac+a2)*frac+a1)*frac+b;
I count 11 adds and 10 multiplies, vs. 9 +'s and 7 *'s in the original Lagrange algorithm in Pd, and 10 +'s and 9 *'s in the "third order Hermite" example. I don't know if it's as simple as all that, though, but it would seem to be on at least a similar order of performance. BTW, the following for the C1 interpolation might be slightly more efficient (I left the original line commented out):
a1 = 0.5f * (c - a); /* a2 = a - 2.5 * b + 2.f * c - 0.5f * d; */ a3 = 0.5f * (d - a) + 1.5f * (b - c); a2 = a - b + a1 - a3;
*out++ = ((a3 * frac + a2) * frac + a1) * frac + b;
.
10 +'s 6 *'s
Matt