binary_exponent.cpp File Reference

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

#include <iostream>

Include dependency graph for binary_exponent.cpp:

Go to the source code of this file.

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

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\).

Definition in file binary_exponent.cpp.

Function Documentation

binExpo()

int binExpo	(	int	a,
		int	b )

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

Definition at line 28 of file binary_exponent.cpp.

                          {
    if (b == 0) {
        return 1;
    }
    int res = binExpo(a, b / 2);
    if (b % 2) {
        return res * res * a;
    } else {
        return res * res;
    }
}

binExpo_alt()

int binExpo_alt	(	int	a,
		int	b )

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

Definition at line 42 of file binary_exponent.cpp.

                              {
    int res = 1;
    while (b > 0) {
        if (b % 2) {
            res = res * a;
        }
        a = a * a;
        b /= 2;
    }
    return res;
}

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;

Definition at line 55 of file binary_exponent.cpp.

           {
    int a, b;
    std::cin >> a >> b;
    if (a == 0 && b == 0) {
        std::cout << "Math error" << std::endl;
    } else if (b < 0) {
        std::cout << "Exponent must be positive !!" << std::endl;
    } else {
        int resRecurse = binExpo(a, b);
 
        std::cout << resRecurse << std::endl;
    }
}