Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



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!




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: