calculation of binary power like $a^b$ where a,b are binary numbers

Question

Is it possible to calculate power of binary number like $a ^ b$where a,b both are binary numbers.

Answer 1

One of the faster and simpler methods is exponentiation by squaring. It is based on taking advantage of the fact that an integer power can be easily reduced by dividing the power by two (possibly with remainder):

$$ a^b = a^{\left \lfloor \frac{b}{2} \right \rfloor 2 + b \% 2} $$

where $\left \lfloor \frac{b}{2} \right \rfloor$ denotes the integer quotient of $b$ and $2$, and $b \% 2$ denotes the remainder (i.e. $1$ for an odd number, $0$ for and even number). We can then rewrite this as:

$$ a^b = (a^2)^{\left \lfloor \frac{b}{2} \right \rfloor} a^{b \% 2} $$

Which now reduces the problem into squaring $a$ (which is trivial), and repeating the same algorithm with power $\left \lfloor \frac{b}{2} \right \rfloor$ and base $a^2$. This will recursively reduce the exponent at each step, ensuring termination.