[PD] better tabread4~

[Matt Barber]

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 at gmail.com> wrote:
> On Sat, Jun 28, 2008 at 7:43 AM, cyrille henry
> <cyrille.henry at 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
>