I am exploring different algorithms to carry out exponentiation lately, and today I found another interesting one. The idea is to break the exponent into powers of 2, and then to pre-compute those powers using the base you are elevating.

For example, suppose you want to elevate 11 to the power of 130. The naive method would involve multiplying 11 by itself 129 times. What if instead we re-write it as 11^128 * 11^2. Now we just need to pre-compute 11 to the various powers of 2:

11^2 = 121
11^4 = 14641 (this is 121 * 121)
11^8 = 214358881 (this is 14641 * 14641)
…
11^128 = 1.987301225×10¹³³

Notice that we can find each number by squaring the previous one. To pre-compute those values we had to perform 7 multiplications. Now we just need to multiply 11^128 by 11^2. In the end we performed 9 multiplications in total, against 129 that the naive method would require.

It’s an interesting algorithm, but it seems to be slower than exponentiation by squaring ones. Anyway here’s the C code:

int expo(int a, int b){
    int powers[20];
    int results[20];
    int z = 0;
    int m = 1;
    int answer = 1;
    int i,partial;

    /*break the exponent into powers of 2 */
    while (b>0){
        partial = (int)pow(2,(int)log2(b));
        powers[z++] = partial;
        b -= partial;
    }

    /*pre-calculate the base elevated to powers of 2*/
    results[0] = a;
    while (m<=log2(powers[0])){
        results[m] = results[m-1] * results[m-1];
        m++;
    }

    /*compute the answer*/
    for (i=0;i<z;i++){
        answer *= results[(int)log2(powers[i])];
    }

    return answer;

}