Polynomial extrapolation

Given a list of integers a1, a2, …, ak (k ≥ 2) and a positive integer m, write a function or a complete program that calculates the next m numbers of the list. Assume that ai = P(i) where

P(x) = bk-1 xk-1 + bk-2 xk-2 + … + b0

is the unique polynomial of minimum order which fits the points.

Description

Input

If the code is a function, input is given by an integer k, an array a1, a2, …, ak and an integer m.

If the code is a program, input (through stdin) is given by space-separated k a1 a2 … ak m.

You can assume that k ≥ 2 and m > 0.

Calculation

(Of course, the code can calculate the result in different way, but the result should be same.)

Find the polynomial P(x) which satisfies ai = P(i) for all 1 ≤ i ≤ k and has a degree of (no more than) k - 1. For example, if a list is 1,2,3,4,5, then P(x) = x. If a list is 1,4,9,16,25, then P(x) = x2.

Then, calculate ak+1 = P(k+1), ak+2 = P(k+2), …, ak+m = P(k+m). These are the results.

Output

If the code is a function, return an array [ak+1, ak+2, …, ak+m].

If the code is a full program, print those numbers to stdout, separated by an any character you want.

• I think you should require some separator for the output: 1 4 9 16 25 is much less ambiguous than 1491625. – Ilmari Karonen Dec 10 '11 at 2:32
• @IlmariKaronen OK then. – JiminP Dec 10 '11 at 2:34
• NB This is almost a duplicate of codegolf.stackexchange.com/questions/1230/… . The differences are that it's over a field of characteristic 0; that the x-coords are implicit; and that it asks for extrapolation to k+1, ... k+m rather than to 0. – Peter Taylor Dec 11 '11 at 7:36

Golfscript, 46 42 40 38 chars

~])\({[{.@-\}*])\}*;]-1%){0\{+.}/p]}*;


This uses a simple difference table approach, which is described in more detail on my GolfScript blog.

• +100: You beat Ilmari's 40 char-or-less challenge :) – mellamokb Dec 12 '11 at 16:05
• Bounty awarded. Congratulations! Now I just need to learn enough GolfScript to be able to understand your code. :) – Ilmari Karonen Dec 13 '11 at 16:22
• @IlmariKaronen, I might write it up for my GolfScript blog in a few days. The -2% is quite interesting in that it's something I didn't really see much point to before. – Peter Taylor Dec 13 '11 at 16:55
• @IlmariKaronen, code dissection posted to my blog. – Peter Taylor Dec 14 '11 at 23:42

Maple, 41 chars

c:=(k,a,m)->interp([$1-k..0],a,x)$x=1..m;


For example, c(3, [1, 2, 4], 4) returns 7, 11, 16, 22.

This function interprets the spec literally, taking both k and a as separate arguments. If the list a does not have exactly k elements, an error occurs. For convenience, here's a 45-char version that omits k from the argument list:

c:=(a,m)->interp([$1-nops(a)..0],a,x)$x=1..m;


I was first thinking of trying this in Perl, but hell, let's use the right tool for the job.

• BTW, since this is code golf, 'the right tool' is golfscript. :P – JiminP Dec 10 '11 at 9:47
• @JiminP: OK, challenge accepted. The first person to solve this task in 40 or fewer chars in GolfScript gets a 100 rep bounty from me. – Ilmari Karonen Dec 10 '11 at 16:20
• @PeterTaylor When inputs are integers, outputs might always be integers (there's a way to calculate outputs by using only integers), even though I don't have any proofs. – JiminP Dec 11 '11 at 7:51
• Challenge met. Don't feel obliged to give me the bounty, though; I'm doing ok for rep already. – Peter Taylor Dec 12 '11 at 0:16
• @PeterTaylor: I'll give it to you anyway, it's not like I'm starved for rep either. And I did promise. (I assume I have to wait until the question is old enough, though, since I don't see any "start a bounty" link yet.) – Ilmari Karonen Dec 12 '11 at 0:42

Jelly, 18 bytes, language postdates challenge

Iß;@Ḣ+\øṁ⁹µL?
çUḣU


Try it online!

Jelly's functions only support up to two arguments, so I don't take in k (which is redundant) as an argument. I hope that's acceptable. The program defines a function 2ŀ that obeys the specification in the question.

Explanation

Helper function 1ŀ (takes input λ, ρ, and expands λ by ρ elements):

Iß;@Ḣ+\øṁ⁹µL?
ø  µ ? If
L    {λ} is nonempty,
then:
I               take differences of consecutive elements of {λ};
ß              call 1ŀ recursively on this value and {ρ};
;@            prepend
Ḣ           the first element of {λ};
+\         and take the cumulative sum {and return it}.
Otherwise:
ṁ⁹      {return} {0} repeated ρ times.


This is fairly magical in the way in which Jelly happens to pick out the exactly values I need it to operate on at every stage. Some of it is the result of me manipulating things; in particular, the unusual choice ø for the separator (rather than the more usual µ) means that all implicit arguments are set to 0, which is fairly handy in this case. However, I have no idea why ;@Ḣ parses the way it does, but it seems to work…

Main function 2ŀ (takes input λ, ρ, and returns the next ρ elements of λ):

çUḣU
ç             Call 1ŀ on {λ} and {ρ};
U            reverse it;
ḣ           take the first {ρ} elements;
U          and reverse it {and return that value}.


This is just massaging the output into the form requested (if we were allowed to return the terms we were already given, that would remove a whole 5 bytes). Jelly doesn't have a "last n elements" function; of the various ways to synthesize it out of other functions, UḣU is convenient here because it happens to pick up ρ as a default argument.

Golfscript, 51 characters

Similar approach to Peter's one.

~])\-1%[{(.@{.@\-}%\;.,}do;]-1%\[0]\*\{\{+.}%\;}%;p


When run on input

2 3 12 35 78
4


it yields the result

[147 248 387 570]


There are still possible places where the solution might be golfable further.