Complex Numbers Exponential - Efficient Computation of Integer Powers

Efficient Computation of Integer Powers

The simplest method of computing bn requires n−1 multiplication operations, but it can be computed more efficiently than that, as illustrated by the following example. To compute 2100, note that 100 = 64 + 32 + 4. Compute the following in order:

1. 22 = 4
2. (22)2 = 24 = 16
3. (24)2 = 28 = 256
4. (28)2 = 216 = 65,536
5. (216)2 = 232 = 4,294,967,296
6. (232)2 = 264 = 18,446,744,073,709,551,616
7. 264 232 24 = 2100 = 1,267,650,600,228,229,401,496,703,205,376

This series of steps only requires 8 multiplication operations instead of 99 (since the last product above takes 2 multiplications).

In general, the number of multiplication operations required to compute bn can be reduced to Θ(log n) by using exponentiation by squaring or (more generally) addition-chain exponentiation. Finding the minimal sequence of multiplications (the minimal-length addition chain for the exponent) for bn is a difficult problem for which no efficient algorithms are currently known (see Subset sum problem), but many reasonably efficient heuristic algorithms are available.