[hefympwg] fitting a polynomial through points

the following Perl script feeding GP uses Lagrange polynomials to interpolate a polynomial between given points.  input is stdin (or a file or files specified on the command line after the script), one point per line, X and Y coordinates separated by whitespace.  Pari/GP does the heavy lifting of (automatically) multiplying out and simplifying the polynomial.  if inputs are integers or rational numbers, Pari/GP automatically does arbitrary precision arithmetic.  (if the inputs are floating point, be careful, as this method is not numerically stable.  you may wish to increase Pari/GP's floating point precision.)

perl -nlwae 'push @x,$F[0]; push @y,$F[1]; END{ for $i(0..$#x){ $l=1; for $j(0..$#x){ next if $i==$j; $l.="*((x-($x[$j]))/($x[$i]-($x[$j])))";} $_.="+" if defined$_; $_.="($y[$i])*($l)";} print;}' | gp -q

Because perl is only manipulating strings (no BigInt needed), the inputs may be any expressions that Pari/GP can evaluate.  all the extra parentheses in the script support this.  (the parentheses were originally needed to support negative inputs.)  here we demonstrate the script recovering a general quadratic when given input of algebraic expressions.

$ echo -e 'x1 a*x1^2+b*x1+c\nx2 a*x2^2+b*x2+c\nx3 a*x3^2+b*x3+c' | perl lagrangepolynomial.pl | gp -q
a*x^2 + b*x + c

this was inspired by a "guess the next word" puzzle, so input expressions such as 27*(27*(27*(27*(8)+5)+12)+12)+15 (the word "hello" encoded in big-endian base 27) also work.  it is always possible to guess a next value (or word) of a sequence by interpolating a polynomial to the previous values.  (the answer might not be what the puzzle poser is looking for.  unclear what to do with a negative predicted next value when values are encoded words.)  it is also possible to justify any next value by adding it to the interpolation.

runtimes with exact arithmetic:

( echo "allocatemem(10^9)" ; for i in `seq 1 100` ; do echo $i $RANDOM ; done | perl lagrangepolynomial.pl ) | nice time gp -q > /dev/null

100 points: 1.4 seconds
150 points: 7 s
200 points: 22 s
250 points: 56 s
300 points: 120 s
400 points: 400 s
450 points: 655 s
500 points: 1016 s

can runtime be improved?