1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Yes. It is possible. $\endgroup$
    – TravisJ
    May 14 '15 at 10:26
2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ In exponentiation by squaring method only the component $b$ is in binary. however i want the method in which $a$ as well as $b$ both the term is in binary form. $\endgroup$
    – Aria
    May 15 '15 at 5:24
  • $\begingroup$ @Aria Only $b$ needs to be an integer, but $a$ can certainly be an integer (in binary form or not). You then just use binary multiplication to calculate $a^2 = a * a$ (and to multiply by $a$ if $b$ is odd). The fact that these numbers are in binary doesn't really matter in this case. The binary aspect is only relevant here in that it makes calculating $b/2$ and $b \% 2$ far more efficient than an arbitrary division, because they can be done with a right shift of one bit (i.e. >> 1 in most programming languages) and by taking only the lowest bit (i.e. & 1) respectively. $\endgroup$ May 15 '15 at 5:30
  • $\begingroup$ What this algorithm does is give an efficient way of computing an integer power of anything (even matrices or other groups/associative operations), using only multiplication. $\endgroup$ May 15 '15 at 5:32
  • $\begingroup$ can you please give example with binary numbers like 0010^ 0111. $\endgroup$
    – Aria
    May 15 '15 at 5:39
  • $\begingroup$ I'm not sure why you see the need to do it by hand with binary numbers; binary is mostly useful when doing things by computer, but here it goes: $\endgroup$ May 15 '15 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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