News for hackers. Stuff that matters.
Re:9,73,241,561,1081,1849,_?_ by JoeAltmaier on Thursday November 05, 2009 @11:33AM (#924096)
I discovered difference tables as a kid, didn't know they were used much, I was modelling motion on a 2D display (an oscilloscope hooked to a P2P11!). Was a lifesaver for quick polynomial evolution - uses only addition, execution time scales linearly with the order of the polynomial. So, how do you go from the difference table "coefficients" to the polynomial?
Re:9,73,241,561,1081,1849,_?_ by jonsen on Thursday November 05, 2009 @01:57PM (#924461)
Integrate the constant 48 back to the series level:

  48 -> 48x -> 24x^2 -> 8x^3
Subtract 8x^3 from the series

  9 - 8•1^3, 73 - 8•2^3, 241 - 8•3^3
and repeat the whole process on this series for the coefficient of x^2, etc...
Re:9,73,241,561,1081,1849,_?_ by SandB0x on Friday November 06, 2009 @12:42PM (#926462)
Exactly. The other perspective: When you see 'difference', think 'derivative' .

Approximately, what the difference table is doing is differentiating until the leading term is constant. If we end up with a constant k levels down, we must have had a.x^k in the polynomial, as the derivative of a.x^k = ak.x^(k-1). Repeating this k times gives constant = a.k!

So the leading coefficient of the polynomial, a = constant/k!

I guess the next step is to subtract the values generated by this term from the sequence, then repeat to find the next term in the polynomial...

Re:9,73,241,561,1081,1849,_?_ by eru on Thursday November 05, 2009 @11:35AM (#924098)
It's a bit non-trivial, but mechanically solvable. Polynomial coefficients are for normal powers. Difference table coefficients have more to do with falling powers (x * (x-1) * (x-2) * ...). Look up "Finite Calculus" or "Difference Equations" if you are interested.
Re:9,73,241,561,1081,1849,_?_ by roundsquare on Thursday November 05, 2009 @03:24PM (#924685)
Other people have given calculus answers... here is one that doesn't require calculus. Its very tedious, but fairly simple to understand.

Give your DT "coefficients" work your way back to the solution.

I.e. in this case: you start with

48

48

48

From which you can get

104 <-- Note: this needs to be given!

152

200

248

And work your way back to

9

73

241

561

1081

1849

So you know you want a polynomial P(x)such that P(1) = 9

p(2) = 73

...

p(3) = 1849

So now you know you need at most a 5th degree polynomial.

So, you have y = a_0 + a_1 * x + a_2 * x^2 + ... + a_5 * x^5

Plug in each value of x and you get 6 equations with 6 unknowns. Solve for a_0, ..., a_5.

Bunch of the a's might well be 0, but thats ok.

Edit: This only works if your difference table eventually reduces to a set of differences which are all the same (e.g here 48, 48, 48). Otherwise, the answer is not a polynomial.

Re:9,73,241,561,1081,1849,_?_ by JoeAltmaier on Thursday November 05, 2009 @03:45PM (#924721)
The order of the polynomial is equal to the number of difference steps until a constant is reached. It MAY be as long as the number of samples in the series. So difference tables are also a handy way to determine the order of a series!
Re:9,73,241,561,1081,1849,_?_ by tudorachim on Thursday November 05, 2009 @12:31PM (#924232)
I'm not sure if this is your question, but divided differences are a way to do polynomial interpolation, with efficient updating to account for new data points: http://en.wikipedia.org/wiki/Newton_polynomial