I was recently wondering if there is some quicker way to compute $x_1^k+x_2^k+\dots+x_n^k$ for any natural $k$ than just exponentiation and adding one-by-one? Thanks in advance.
Asked
Active
Viewed 103 times
3
-
4Newton's identities! – Ghartal Jun 19 '16 at 16:00
-
1@Ghartal is that really quicker, though? exponentiation can be pretty quick, and there's a lot of cross-product work in the elementary symmetric polynomials. – Joffan Jun 19 '16 at 16:08
-
Where $x_1,\ldots,x_n$ are? – Jack D'Aurizio Jun 19 '16 at 16:20
-
@Joffan It's not bad! – Ghartal Jun 19 '16 at 16:22
-
Thanks for quick responses. I'll try to implement both and see which method works quicker - I think that one-by-one method can be faster for small $k$. @JackD'Aurizio In my particular application $x_1,\dots,x_n$ are natural numbers smaller than $7$. – Mateusz Duchalski Jun 19 '16 at 16:34
-
@MateuszDuchalski: then you may also exploit the Chinese remainder theorem together with the techniques based on the companion matrix/symmetric polynomials. – Jack D'Aurizio Jun 19 '16 at 16:36
1 Answers
0
I can't think of a universal algorithm for any $x_1,\ldots ,x_n,k$, but you could use the exponentiation by squaring for fast exponentiation.
pajonk
- 185