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.

So I want to ask:
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 English attempt 2019-12-10 12:48:37 1 Tiny change: 'ick reduce runtime a' -> 'ick reduces runtime a'
en1 English attempt 2019-12-10 12:47:48 1232 Initial revision (published)