Is there any way to compute these sums quickly?

Question

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)$$

Answer 1

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$.

Answer 2

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).