Skip to main content
Mathematics

Return to Answer

added 40 characters in body
Source Link
sperners lemma
sperners lemma
  • 2.2k
  • 1
  • 16
  • 31

If $x$ is small compared to $n$ and/or $m$ there are some good optimizations you can do:

  • Edit: This is wrong, don't do this: Replace $n$ with its remainder on division by $\varphi(x)$. this only works for the bases coprime to n, which is a good proportion so it may still be worth it to do that.. for ones that aren't coprime...

  • Use binary exponentiation.

  • Split the sum into blocks $[1^n + 2^n + ... + x^n] + [(x+1)^n + (x+2)^n + \ldots] + \ldots$ which are all equal, so you only need to compute the sum of $x$ terms rather than $m$.

If $x$ is large compared to $n$ then (as already mentioned in comments) it will be more efficient to compute the sum using a closed form polynomial (which you may need to compute before use).

If $x$ is small compared to $n$ and/or $m$ there are some good optimizations you can do:

  • Replace $n$ with its remainder on division by $\varphi(x)$.

  • Split the sum into blocks $[1^n + 2^n + ... + x^n] + [(x+1)^n + (x+2)^n + \ldots] + \ldots$ which are all equal, so you only need to compute the sum of $x$ terms rather than $m$.

If $x$ is large compared to $n$ then (as already mentioned in comments) it will be more efficient to compute the sum using a closed form polynomial (which you may need to compute before use).

If $x$ is small compared to $n$ and/or $m$ there are some good optimizations you can do:

  • Edit: This is wrong, don't do this: Replace $n$ with its remainder on division by $\varphi(x)$. this only works for the bases coprime to n, which is a good proportion so it may still be worth it to do that.. for ones that aren't coprime...

  • Use binary exponentiation.

  • Split the sum into blocks $[1^n + 2^n + ... + x^n] + [(x+1)^n + (x+2)^n + \ldots] + \ldots$ which are all equal, so you only need to compute the sum of $x$ terms rather than $m$.

If $x$ is large compared to $n$ then (as already mentioned in comments) it will be more efficient to compute the sum using a closed form polynomial (which you may need to compute before use).

Source Link
sperners lemma
sperners lemma
  • 2.2k
  • 1
  • 16
  • 31

If $x$ is small compared to $n$ and/or $m$ there are some good optimizations you can do:

  • Replace $n$ with its remainder on division by $\varphi(x)$.

  • Split the sum into blocks $[1^n + 2^n + ... + x^n] + [(x+1)^n + (x+2)^n + \ldots] + \ldots$ which are all equal, so you only need to compute the sum of $x$ terms rather than $m$.

If $x$ is large compared to $n$ then (as already mentioned in comments) it will be more efficient to compute the sum using a closed form polynomial (which you may need to compute before use).