Find an approximating polynomial of known degree for a given data.

Example:
For input data:

x = {0,  1,  2,  3,  4,  5,  6,   7,   8,   9,   10};
y = {1,  6,  17, 34, 57, 86, 121, 162, 209, 262, 321};

The approximating polynomial is:

3 x2 + 2 x + 1

Here, the polynomial's coefficients are (3, 2, 1).

This task is intended as a subtask for Measure relative performance of sorting algorithms implementations.

-- demo\rosetta\Polynomial_regression.exw
with javascript_semantics
constant x = {0,1,2,3,4,5,6,7,8,9,10},
         y = {1,6,17,34,57,86,121,162,209,262,321},
         n = length(x)
 
function regression()
    atom xm = 0, ym = 0, x2m = 0, x3m = 0, x4m = 0, xym = 0, x2ym = 0
    for i=1 to n do
        atom xi = x[i],
             yi = y[i]
        xm += xi
        ym += yi
        x2m += power(xi,2)
        x3m += power(xi,3)
        x4m += power(xi,4)
        xym += xi*yi
        x2ym += power(xi,2)*yi
    end for
    xm /= n
    ym /= n
    x2m /= n
    x3m /= n
    x4m /= n
    xym /= n
    x2ym /= n
    atom Sxx = x2m-power(xm,2),
         Sxy = xym-xm*ym,
         Sxx2 = x3m-xm*x2m,
         Sx2x2 = x4m-power(x2m,2),
         Sx2y = x2ym-x2m*ym,
         B = (Sxy*Sx2x2-Sx2y*Sxx2)/(Sxx*Sx2x2-power(Sxx2,2)),
         C = (Sx2y*Sxx-Sxy*Sxx2)/(Sxx*Sx2x2-power(Sxx2,2)),
         A = ym-B*xm-C*x2m
    return {C,B,A}
end function
 
atom {a,b,c} = regression()
 
function f(atom x)
    return a*x*x+b*x+c
end function
 
printf(1,"y=%gx^2+%gx+%g\n",{a,b,c})
printf(1,"\n  x   y  f(x)\n")
for i=1 to n do
    printf(1," %2d %3d   %3g\n",{x[i],y[i],f(x[i])})
end for

-- And a simple plot (re-using x,y from above)

include pGUI.e
include IupGraph.e
 
function get_data(Ihandle graph)
    integer {w,h} = IupGetIntInt(graph,"DRAWSIZE")
    IupSetInt(graph,"YTICK",iff(h<240?iff(h<150?80:40):20))
    return {{x,y,CD_RED}}
end function

IupOpen()
Ihandle graph = IupGraph(get_data,"RASTERSIZE=640x440")
IupSetAttributes(graph,"XTICK=1,XMIN=0,XMAX=10")
IupSetAttributes(graph,"YTICK=20,YMIN=0,YMAX=320")
Ihandle dlg = IupDialog(graph,`TITLE="simple plot"`)
IupSetAttributes(dlg,"MINSIZE=245x150")
IupShow(dlg)
if platform()!=JS then 
     IupMainLoop()
     IupClose()
end if
