Polynomial extrapolation

Question

Task

Given a list of integers a₁, a₂, …, a_k (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 a_i = P(i) where

P(x) = b_k-1 x^k-1 + b_k-2 x^k-2 + … + b₀

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 a₁, a₂, …, a_k and an integer m.

If the code is a program, input (through stdin) is given by space-separated k a₁ a₂ … a_k 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 a_i = 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) = x².

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

Output

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

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.