Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Optimal number of multiplications in calculating p^k

Revision en2, by attempt, 2019-12-10 12:48:37

Note: I couldn't find exact terminology for this question. It is something like "Russian Peasant multiplication" for calculating exponent.

There's a well-known way of calculating $p^k$ as follow:

template<typename T> T pow(T p, int k) {
T t = 1;
while (k > 0) {
if (k % 2 == 1) t = t * p;
p = p * p;
k /= 2;
}
return t;
}


We can reduce one multiplication ($1 * p$) from above implementation with a variable named first_mul:

template<typename T> T pow(T p, int k) {
T t;
bool first_mul = false;
while (k > 0) {
if (k % 2 == 1) {
if (!first_mul) t = p, first_mul = true;
else t = t * p;
}
p = p * p;
k /= 2;
}
return t;
}


I found that when operator $*$ is very heavy, like matrix or polynomial multiplication, this trick reduces runtime a lot.

1. Is there a simple algorithm that is better than above algorithm for $k \leq 10^9, k \leq 10^{18}$, $k \leq 10^{100}$?
2. Is there any way to find the optimal number of multiplications in calculating $p^k$?

#### History

Revisions Rev. Lang. By When Δ Comment
en2 attempt 2019-12-10 12:48:37 1 Tiny change: 'ick reduce runtime a' -> 'ick reduces runtime a'
en1 attempt 2019-12-10 12:47:48 1232 Initial revision (published)