attempt's blog

Optimal number of multiplications in calculating p^k
By attempt, history, 4 years ago, In English

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

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

If you know that k>=1, you can set t = p; and decrease k by 1 instead of strange if

→ Reply
»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

From wiki:

In general, finding the optimal addition chain for a given exponent is a hard problem, for which no efficient algorithms are known, so optimal chains are typically only used for small exponents (e.g. in compilers where the chains for small powers have been pre-tabulated). However, there are a number of heuristic algorithms that, while not being optimal, have fewer multiplications than exponentiation by squaring at the cost of additional bookkeeping work and memory usage. Regardless, the number of multiplications never grows more slowly than Θ(log n), so these algorithms only improve asymptotically upon exponentiation by squaring by a constant factor at best.

→ Reply