Finding a polynomial's constant from its points Let's say I was given a set of $d+1$ distinct points known to be from a polynomial $P$ of degree $d$.
So:
$$P = a_dx^d + a_{d-1}x^{d-1} + ... a_1x + c$$
And I have pairs $(x_i, y_i)$ such that:
$$P(x_1) = y_1$$
$$...$$
$$P(x_{d+1}) = y_{d+1}$$
My question is: what's the quickest way to find $c$?
The only option I've seen so far is building the Lagrange Polynomial and then evaluating $P(0)$, but it seems wasteful because it reconstructs all $a_i$ coefficients, resulting in $O(d^2)$ operations. Is there anything faster?
Note there are enough points to reconstruct the unique polynomial, and they all lie perfectly on the curve.
 A: Given are the points
$$
\Big(x_d, y_d\Big),\ \textrm{for} : 1 \le d \le m.
$$
and we try to fit them on
$$
f(x) = \sum_{k=0}^n a_k x^k.
$$
The quality factor is defined as
$$
Q = \sum_{\ell=1}^m \Big( \sum_{k=0}^n a_k x_\ell^k - y_\ell\Big)^2.
$$
Perfect fit means $Q = 0$, best fit means
$$
\frac{\partial Q}{\partial a_\jmath} = 0,
$$,
whence
$$
\sum_{k=0}^n \left(
  a_k \sum_{\ell=1}^m x_\ell^\jmath x_\ell^k -n \sum_{\ell=1}^m x_\ell^\jmath y_\ell
\right) = 0,
$$
therefore
$$
\boxed{
a_k = n \frac{ \displaystyle \sum_{\ell=1}^m x_\ell^\jmath y_\ell }
{ \displaystyle \sum_{\ell=1}^m x_\ell^\jmath x_\ell^k }.}
$$
So the best fit is given by
$$
\boxed{
f(x) = \sum_{k=0}^n \left\{ n \frac{ \displaystyle \sum_{\ell=1}^m x_\ell^\jmath y_\ell }
{ \displaystyle \sum_{\ell=1}^m x_\ell^\jmath x_\ell^k } \right\} x^k.
}
$$
As for your $c$:
$$
\boxed{
c = n \frac{ \displaystyle \sum_{\ell=1}^m x_\ell^\jmath y_\ell }
{ \displaystyle \sum_{\ell=1}^m x_\ell^\jmath x_\ell^0 }.
}
$$
A: I'd use Cramer's Rule.  Set up the system of matrix equations $Ac=y$. Let $A$ be the matrix whose rows are $x^n, x^{n-1}, ...x, 1$ (where $n$ is the degree of the polynomial), where each row's x is one of the given x coordinates. Let $y$ be the column vector whose rows are $y_n$, which each correspond to the x coordinate in the same row. Then $c$ will be a column vector, and it's bottommost entry will be the constant term of the polynomial. Finally, let $A_c$ be the vector formed by replacing the column of ones in $A$ by $y$, then $$c= \frac{\det(A_c)}{\det(A)} $$
