I need to compute $\sum_{i=1}^n (x_i) ^ a$ for many different values of a where n is large and x is fixed.
I am in an environment where computing exponentials $(x_i) ^ a$ is effectively constant time.
Computing the sum directly takes O(n) time. Are there any alternative options that are faster?
On
This is not an answer.
This is a long-winded comment.
Questions about specific computer code are clearly off-topic to the MathSE forum. However, my personal (highly subjective) feeling is that this prohibition doesn't necessarily apply to questions about overall software design (AKA pseudocode).
Also, the nature of the question posed suggests to me that it isn't really appropriate to ask the OP (i.e. original poster) to show work.
My knowledge of optimizing software design is business-oriented, rather than Math-oriented. So, it is very plausible that a different MathSE reviewer might provide insights that make this response all but obsolete.
I am going to assume, for the sake of simplicity that each of the
many different values of a
referred by the OP is a non-negative integer.
Note that this response will be easy to adapt if negative integer values are permitted, among some of the $(a)$'s, simply by consideration of $~\dfrac{1}{x_i}~$ in place of $x_i$.
If my assumption is wrong, and the OP intends that a significant number of the $(a)$'s are not integers, then this entire response may become worthless.
First of all, any collection of associated values should be stored in a (relatively) high speed access array, rather than an (for example) some sort of (high overhead) array list.
Note that $n$ is to be a known (presumably large) positive integer. Also, the number of different values of $(a)$ is also a known positive integer.
So, you can routinely define the corresponding arrays of the desired size to hold the associated values.
Suppose that the corresponding values of the $(a)$'s are represented in strictly ascending order by
$$\text{Set} ~B = \{a_1, a_2, \cdots, a_k\}.$$
Then, you can create an array to hold set $B$.
Then, you can create a separate two dimensional array of dimensions $n \times k$. You can let each row of the two dimensional array pertain to a specific value of $a_i$ and let each column of the two dimensional array pertain to a specific value of $x_i$.
So, for a specific value $x_i$, one of the rows will contain $x_i^{a_1}, ~x_i^{a_2}, ~\cdots, x_i^{a_k}.$
To populate this row, first compute $x_i^{a_1}.$ Then, use this computed value to compute
$x_i^{a_2} = x_i^{a_1} \times x_i^{a_2 - a_1}$.
You can then routinely complete the row, with
$x_i^{a_k} = x_i^{a_{(k-1)}} \times x_i^{a_k - a_{(k-1)}}$.
Once all of the rows are populated, you can compute the summation that pertains to each value $a_i$ by summing along the corresponding column of the two dimensional array.
Edit
There is a possible refinement that may reduce the program's running time, at the expense of making the computer program significantly more complicated. This means that the program will be harder to document and maintain.
Consider the ordered $k$-tuple given by
$$\left(a_1, ~[a_2 - a_1], ~[a_3 - a_2], \cdots, ~[a_k - a_{k-1}] \right).$$
Suppose for example, that $a_2 - a_1 = a_{11} - a_{10}.$ This means that for each value $x_i$, the factor applied to $x_i^{a_1}$ to compute $x_i^{a_2}$ will be the same as the factor applied to $x_i^{a_{10}}$ to compute $x_i^{a_{11}}.$
Further, this avoidance of redundant computing will apply in each row, for each value $x_i$.
The difficult is that you have to somehow
register that (for example) $a_{11} - a_{10} = a_2 - a_1.$
For each value of $x_i$, until the entire row is completed, you have to store the factor $x_i^{a_2 - a_1}.$
Then, you have to re-apply this (already computed) factor, at the appropriate moment, to $x_i^{a_{10}}$ in order to compute $x_i^{a_{11}}.$
If you do this perfectly, this will make the code very complicated. You will then have to add a great deal of documentation to explain what you are doing. Also, you might have to re-structure the entire program to accommodate this refinement.
Edit
After completing the above long-winded comment, I glanced at the OP's answer. The use of logarithms (perhaps also with Taylor series) strikes me as very interesting. His response may well prove to be very superior to mine, even if each of $a_1, a_2, \cdots, a_k$ is an integer.
Actually, I just came up with a solution that will probably work in my setting, but might not in others.
In my particular situation, I know $\text{abs}(a \, \log(x_i))$ is quite small.
In that case, I can use the Taylor series with t terms:
$$\sum_{i=1}^n (x_i) ^ a = \sum_{i=1}^n \sum_{j=0}^t \frac{a^j \, \log^{j}(x_i)}{j!} = \sum_{j=0}^t \frac{a^j}{j!} \left(\sum_{i=1}^n \, \log^{j}(x_i) \right)$$
This will have decent convergence if and only if $\text{abs}(a \, \log(x_i))$ is small enough.
You can then precompute $\sum\limits_{i=1}^n \log^{j}(x_i)$ for every $j$ up until $t$.
Can anyone think of any improvements?