Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
binary_exponent.cpp File Reference

C++ Program to find Binary Exponent Iteratively and Recursively. More...

#include <iostream>
Include dependency graph for binary_exponent.cpp:

Functions

int binExpo (int a, int b)
 
int binExpo_alt (int a, int b)
 
int main ()
 Main function. More...
 

Detailed Description

C++ Program to find Binary Exponent Iteratively and Recursively.

Calculate \(a^b\) in \(O(\log(b))\) by converting \(b\) to a binary number. Binary exponentiation is also known as exponentiation by squaring.

Note
This is a far better approach compared to naive method which provide \(O(b)\) operations.

Example: 10 in base 2 is 1010.

\begin{eqnarray*} 2^{10_d} &=& 2^{1010_b} = 2^8 * 2^2\\ 2^1 &=& 2\\ 2^2 &=& (2^1)^2 = 2^2 = 4\\ 2^4 &=& (2^2)^2 = 4^2 = 16\\ 2^8 &=& (2^4)^2 = 16^2 = 256\\ \end{eqnarray*}

Hence to calculate 2^10 we only need to multiply \(2^8\) and \(2^2\) skipping \(2^1\) and \(2^4\).

Function Documentation

◆ binExpo()

int binExpo ( int  a,
int  b 
)

Recursive function to calculate exponent in \(O(\log(n))\) using binary exponent.

28  {
29  if (b == 0) {
30  return 1;
31  }
32  int res = binExpo(a, b / 2);
33  if (b % 2) {
34  return res * res * a;
35  } else {
36  return res * res;
37  }
38 }

◆ binExpo_alt()

int binExpo_alt ( int  a,
int  b 
)

Iterative function to calculate exponent in \(O(\log(n))\) using binary exponent.

42  {
43  int res = 1;
44  while (b > 0) {
45  if (b % 2) {
46  res = res * a;
47  }
48  a = a * a;
49  b /= 2;
50  }
51  return res;
52 }

◆ main()

int main ( void  )

Main function.

Give two numbers a, b

int resIterate = binExpo_alt(a, b);

Result of a^b (where '^' denotes exponentiation)

std::cout << resIterate << std::endl;

55  {
56  int a, b;
57  /// Give two numbers a, b
58  std::cin >> a >> b;
59  if (a == 0 && b == 0) {
60  std::cout << "Math error" << std::endl;
61  } else if (b < 0) {
62  std::cout << "Exponent must be positive !!" << std::endl;
63  } else {
64  int resRecurse = binExpo(a, b);
65  /// int resIterate = binExpo_alt(a, b);
66 
67  /// Result of a^b (where '^' denotes exponentiation)
68  std::cout << resRecurse << std::endl;
69  /// std::cout << resIterate << std::endl;
70  }
71 }
Here is the call graph for this function:
binExpo
int binExpo(int a, int b)
Definition: binary_exponent.cpp:28
std::cout
std::endl
T endl(T... args)
std::cin