1

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

Aria
  • 291

1 Answers1

2

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.

John Colanduoni
  • 1,901
  • 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. – Aria May 15 '15 at 05:24
  • @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. – John Colanduoni May 15 '15 at 05:30
  • 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. – John Colanduoni May 15 '15 at 05:32
  • can you please give example with binary numbers like 0010^ 0111. – Aria May 15 '15 at 05:39
  • 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: – John Colanduoni May 15 '15 at 05:40
  • $0010^{0111} = (00100010)^{0011} 0010 = 0100^{0011} * 0010 = (01000100)^{0001} 0100 * 0010 = 10000 * 0100 * 0010 = 1000000 = 128_{10}$. If you found that hard to follow, that is because binary is not a good way to do calculations by hand; its much easier to just compute $2^7$. – John Colanduoni May 15 '15 at 05:46
  • in my coding everything is in terms of binary, so for raising power i have to convert it in decimal. that's why i need it. – Aria May 15 '15 at 05:48
  • Let us continue this discussion in chat. – John Colanduoni May 15 '15 at 05:48