Exponentiation

Naïve method

Given a number $a$ and a positive integer $n$, suppose we want to compute $a^n$. The standard naïve method is a simple for loop that performs $n − 1$ multiplications by $a$:

$\underline{SlowPower(a, n):} \\ \hspace{0.4cm} x←a \\ \hspace{0.4cm} for\space i ← 2 \space to\space n \\ \hspace{1cm} x←x·a \\ \hspace{0.4cm} return \space x$

Explanation

• Lines 1–5: We compute the value of a positive integer $a$ raised to the power of another positive integer n using a simple for loop that performs n-1 multiplications. The function iteratively multiplies x by $a$ n-1 times. Finally, the function returns the value of x. However, this method has a time complexity of $O(n)$, which can be very slow for large values of n.

• Line 8: We print the result on the console.

Fast exponentiation algorithm

This iterative algorithm requires $n$ multiplications. The input parameter $a$ could be an integer, a rational, or a floating point number. In fact, it doesn’t need to be a number at all as long as it’s something that we know how to multiply. For example, the same algorithm can be used to compute powers modulo some finite number (an operation commonly used in cryptography algorithms) or to compute powers of matrices (an operation used to evaluate recurrences and to compute shortest paths in graphs). Because we don’t know what kind of object we’re multiplying, we can’t know how much time a single multiplication requires, so we’re forced to analyze the running time in terms of the number of multiplications.

There is a much faster divide-and-conquer method, originally proposed by the Indian prosodist $Pi\overset{.}{n}gala$ in the 2nd century BCE, which uses the following simple recursive formula:

$$a^n = \begin{cases} 1& \text{ if } n=0 \\ (a^{n/2})^2& \text{ if n > 0 and n is even} \\ (a^{[n/2]})^2.a& \text{ otherwise } \end{cases}$$ ...