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)
.
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)
.
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.
powN(a,powN(w,n))
? $\endgroup$ – David Richerby Feb 7 '17 at 12:53[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