Is there any way to compute these sums quickly? I have a sum of the following form (all numbers are positive integers):
$$F(p) = \sum_{x=1}^{N} a_x x^p $$
Where $N$ and all $a_x$ terms are known/fixed constants.
However I need to be able to query the sum $F(p)$ quickly based on the input $p$. Is there any way I can do this quickly without needing to recompute the entire sum?
For example, when $N=6$ and we try $p=3$ and $p=4$ and $p=5$:
$$F(3) = a_1(1^3) + a_2(2^3) + a_3(3^3) + a_4(4^3) + a_5(5^3) + a_6(6^3)$$
$$F(4) = a_1(1^4) + a_2(2^4) + a_3(3^4) + a_4(4^4) + a_5(5^4) + a_6(6^4)$$
$$F(5) = a_1(1^5) + a_2(2^5) + a_3(3^5) + a_4(4^5) + a_5(5^5) + a_6(6^5)$$
 A: Remarks:
Computing a single sum requires $N-1$ additions, $N$ multiplications and $N$ powers. If the values of $p$ are bounded, you can precompute the powers; otherwise they will take $\lceil \text{Lg}(p)\rceil$ multiplies each. For a single sum, you can't do better.
For multiple sums with incremental values of $p$, you can compute all terms by recurrence and store them, reducing to $N-1$ adds and $N$ multiplies per evaluation, but this is not really significant.
If you had the $N$-th roots of the unit instead of integers, the formula would describe a Discrete Fourier Transform, for which a fast algorithm is known, taking $O(N\log(N))$ operations instead of $O(N^2)$. There is a modular arithmetic extension of it, but it doesn't match your problem either.
The problem can also be recast as that of the multiplication of a constant Vandermonde matrix with the vector of $a_x$. It will be hard to beat the $O(N^2)$ barrier. The matrix has the additional property that its entries form the sequence of integers. The $LU$ factorization of such matrices is known analytically, but this won't reduce the complexity.
If the coefficients $a_x$ are polynomials in $x$ of degree $d$, then $F(p)$ is a polynomial in $N$ of degree $d+p+1$ that you can precompute independently of $N$.
A: The best way to compute polynomials with random coefficients for different values is Horner's rule:
$$
a_n x^n + a_{n - 1} x^{n - 1} + \dotsb + a_0
  = (\dotsm(a_n x + a_{n - 1}) x + \dotsb) x + a_0
$$
Note that having the powers of $x$ precomputed doesn't do better than this.
If the coefficients are known beforehand, you might find a more efficient way to compute it (e.g. factor it, evaluate the factors and multiply, or take advantage of some special form).
