Archived

This topic is now archived and is closed to further replies.

sofsenint

Polynomial Prediction

Recommended Posts

I''m in the Game Mathematics course of GameInstitute, and recently went back to a class our instructer wrote to predict a number based on previous numbers with the intention of writing my own. However, looking at his code, I simply cannot for the life of me figure out why it works. If someone could explain it to me I''d be very grateful. First, he checks to see how many previous numbers the class has been given. If it is only one, obviously, it returns the same number(the graph would be a horizontal line). If it has been given two numbers, he uses the equation c = -a + (2* b), where a and b are the two known numbers and c is the number being predicted. If the class knows three numbers, he uses the equation d = a - 3*b + 3*c, where a, b, and c are the previous numbers and d is the number being predicted. Why does this algorithm work?

Share this post


Link to post
Share on other sites
It''s an application of discrete/difference mathematics. At school most of us study differential mathematics, where the fundamental operation is taking the derivative of a continuous function. But if you don''t have a continuous function but only have a discrete set of values you can''t do this. One option is to use discrete mathematics.

The basic operation here is the ''difference'' of a set of data, e.g. if you have this data (the squares of the natural numbers)

0, 1, 4, 9, 16, 25, 36

the first difference, calculated by subtracting adjacent numbers, is

1, 3, 5, 7, 9, 11

The second difference is obtained from this new set in the same way, and it is

2, 2, 2, 2, 2

Writing these together (using zeros to line up th columns the pattern is now obvious.

0, 1, 4, 9, 16, 25, 36
01, 3, 5, 07, 09, 11
0002, 2, 2, 02, 02

And this can be continued by adding on the differences to extend the rows, to generate thr square numbers without multiplication. This is not especially useful here but for some series it''s the easiest way to generate them - the Fibbonachi sequence is the best example of this.

How does this relate to your question. Simply because the algorithm is this: write down the numbers and all the differences below them until there''s just one number 1 number in the row of differences, then extend the sequence so the last row of differences is constant. E.g. if you have the numbers 1, 4, 8 you write out the differences

1, 4, 8
03, 4
001

The last row is the 1, so extending that and then using addition to extend the next two rows gives

1, 4, 8, 13
03, 4, 5
001, 1

If all the additions and subtractions in this are combined the formula d = a - 3b + 3c results. The more numbers you have the more rows you get, so the formulae get more and more complex.

This can be graphed as a quadratic, and the same answer can be derived from working out the quadratic and using that to predict the third number. I prefer the difference method, as it requires the minimum amount of work and is easily extended to longer sequences.

Share this post


Link to post
Share on other sites
> BTW- Are you a teacher?

I used to be, but now program for a living. More usefully I did maths to an advanced level, which is useful for obscure stuff like this and finding alternative ways fo doing things. In my experience you can never know too much maths, and if your work involves maths you find that almost everything you learn turns out to be useful at some time.

Share this post


Link to post
Share on other sites