1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I'm not sure what you're asking for. What's wrong with powN(a,powN(w,n))? $\endgroup$ – David Richerby Feb 7 '17 at 12:53
  • 1
    $\begingroup$ Your algorithm is not efficient. The repeated squaring algorithm mentioned by melchizedek does $\Theta(\log n)$ arithmetic operations rather than your $\Theta(n)$. $\endgroup$ – Yuval Filmus Feb 7 '17 at 12:59
  • $\begingroup$ [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$? $\endgroup$ – greybeard Feb 7 '17 at 17:00
  • $\begingroup$ @dud3 You may want to check out this link. $\endgroup$ – Raphael Feb 7 '17 at 17:58
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.