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 reduce 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$$$?