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$

closed as unclear what you're asking by Evil, Tom van der Zanden, Gilles Feb 26 '17 at 17:33

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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