DEV Community

Cover image for Binary Exponentiation
Farhan Yahya
Farhan Yahya

Posted on • Edited on

4 1

Binary Exponentiation

Binary exponentiation is a simple technique used to find the value for an in O(logn) multiplications instead of the naive way which is O(n) multiplications. First, let's have a look at the naive way then this way.

The naive way

From mathematics, an is expressed as a multiplying itself n times. Hence a naive function for solving this will be like below.

int pow(int a, int n){
  int ans = 1;
  while(n--){
    ans *= a;
  } 
  return ans;
}

This is quite simple but we will want to reduce the complexity of this function and that is where binary exponentiation comes in.

This way(Binary Exponentiation)

In this method, the work is split into the binary representation of the exponent which reduces the computation to O(logn).

Example

Naive: 313 = 3 * 3 ... 3
This way: 313 = 31101 = 38 * 34 * 31
Implementing an algorithm for this is very simple. intead of looping n times we rather loop through the bits which is logn times. To get our solution, we then find the powers at which a bit is set just like the example above. Because we are using the binary presentation of n the power at a set bit will be the square of the previous set bit.
That is:
31 = 3
32 = (31)2
34 = (32)2
38 = (34)2 ...

So with this, we just find the product of the powers set in n.

Code for this way

int pow(int a,int n){
  int res = 1;
  while(b){
    if(b&1){
      res *= a;
    }
    a *= a;
    b >>= 1;
  }
  return res;
}

The above code computes in O(logn) which is better than the naive way which computes in O(n)

Image of Datadog

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (2)

Collapse
 
smartyansh profile image
Anshul Bansal • Edited

There seems to be a small mistake in the example:
This way: 313 = 31101 = 38 * 34 * 32 should be 38 * 34 * 31

Collapse
 
dochan profile image
Farhan Yahya

Thanks for the correction

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more