Recursive algorithm - a^(2^n) [closed]

Question

The a^n was pretty easy:

function powN(a, n) {
    if(n == 0) return 1;
    return a * powN(a, n - 1);
};

But somehow I got stuck on a^(2^n), any suggestions or even a hint?

I need a recursive algorithm that solves: a^(2^n).

Answer 1

Let's look at how many multiplications are necessary to perform $a^{16}$ by your recursive method:

$$a \xrightarrow{SQR} a^2 \xrightarrow{MUL} a^3 \xrightarrow{MUL} \ldots \xrightarrow{MUL} a^{14} \xrightarrow{MUL} a^{15} \xrightarrow{MUL} a^{16}$$

Where:

$SQR$ = Squares a number

$MUL$ = Usual Multiplication

So as Yuval pointed out in the comments, even a small power of $2$ would require $\Theta(n)$ multiplications, which means this would be too slow for practical use.

However, you can the same thing using only $SQR$ with $\Theta(\log{n})$ operations. That is:

$$a \xrightarrow{SQR} a^2 \xrightarrow{SQR} a^4 \xrightarrow{SQR} a^8 \xrightarrow{SQR} a^{16}$$

Of course, since $16$ is a power of $2$ we only need to use $SQR$. But you can alternate between $SQR$ and $MUL$. This is the principle behind Exponentiation by Squaring.

Example:Computing $a^{19}$.

$$a \xrightarrow{SQR} a^2 \xrightarrow{SQR} a^4 \xrightarrow{SQR} a^8 \xrightarrow{MUL} a^{9} \xrightarrow{SQR} a^{18} \xrightarrow{MUL} a^{19} $$

Answer 2

We have $a^{2^n}$ = $a^{2·2^{n-1}}$ = $(a^2)^{2^{n-1}}$. Therefore

function pow2powN(a, n) {
    if(n == 0) return a;
    return pow2powN(a*a, n - 1);
};

If you use floating-point arithmetic, this runs in O(n). To avoid confusion, for example n = 10 would calculate $a^{1024}$. If you use integer arithmetic, then this will overflow for many values but run in O (n). If you use multi-precision arithmetic where the time grows with the sizes of the numbers, the time is basically the time for the last squaring.