Problem D
Don't Be Such a Square
Let’s say you have a number x and want to write a program to find out the value of $x^ n$ (and that you can’t use any math functions available in your programming language of choice). By definition, $x^ n$ is $x$ multiplied by itself $n$ times, so this program would actually be fairly simple:
a = 1
i = 0
while i < n do
a = a * x
i = i + 1
end while
However, like most simple algorithms, this one is very inefficient. We have to perform a multiplication operation $n$ times! And who has time for that? Certainly not the students of the Masters Program in Computer Science.
Fortunately, there is a slightly-more-complicated-but-still-pretty-simple method called exponentiation-by-squaring that requires far fewer arithmetic operations. For example, imagine we wanted to find the value of $3^16$. Instead of multiplying 3 times itself 16 times, we could express this operation like this:
\[ ((((3^2)^2)^2)^2) \]That’s just four multiplications instead of sixteen! Of course, in this case the exponent was conveniently a power of two. However, this trick also works for other exponents. For example, for $3^17$ we would just have to add an extra multiplication:
\[ ((((3^2)^2)^2)^2) \cdot 3 \]As it turns out, we can define exponentiation-by-squaring recursively (for all $x$ and $n$) like so:
\[ \exp (x, n) = \left\lbrace \begin{array}{l l} 1 & \text {if }n=0 \\ x & \text {if }n=1 \\ \exp (x \cdot x, \frac{n}{2}) & \text {if }n>1\text { and }n\text { is even} \\ \exp (x \cdot x, \frac{n-1}{2})\cdot x & \text {if }n>1\text { and }n\text { is odd} \end{array}\right. \]Your solution must use a RECURSIVE function, using the definition presented above.
On the exam, any other type of solution will receive zero points!
EVEN IF KATTIS JUDGES IT AS CORRECT!
Input
The input contains two positive integers: $x$ and $n$, separated by a single space.
Output
A single integer: $x^ n$, computed using the definition described above. You can assume $x^ n$ will fit in a 32-bit integer.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 16 |
43046721 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 17 |
129140163 |
| Sample Input 3 | Sample Output 3 |
|---|---|
100 0 |
1 |
| Sample Input 4 | Sample Output 4 |
|---|---|
100 1 |
100 |
