Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/de/dcf/binary__exponent_8cpp.html below:

TheAlgorithms/C++: math/binary_exponent.cpp File Reference

Loading...

Searching...

No Matches

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

#include <iostream>

Go to the source code of this file.

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.

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

Definition at line 28 of file binary_exponent.cpp.

28 {

29 if (b == 0) {

30 return 1;

31 }

33 if (b % 2) {

34 return res * res * a;

35 } else {

36 return res * res;

37 }

38}

int binExpo(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.

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

55 {

56 int 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 {

resRecurse =

(a, b);

66

68 std::cout << resRecurse << std::endl;

70 }

71}

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4