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

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).

• I'm not sure what you're asking for. What's wrong with powN(a,powN(w,n))? – David Richerby Feb 7 '17 at 12:53
• Your algorithm is not efficient. The repeated squaring algorithm mentioned by melchizedek does $\Theta(\log n)$ arithmetic operations rather than your $\Theta(n)$. – Yuval Filmus Feb 7 '17 at 12:59
• [a recursive procedure for] a^n was pretty easy - how did you arrive at it? What is $a²^0, a²^1, a²^2, a²^3$? – greybeard Feb 7 '17 at 17:00
• @dud3 You may want to check out this link. – Raphael Feb 7 '17 at 17:58

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

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.