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

Faster computation for \(a^b\). More...

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <ctime>
#include <iostream>
Include dependency graph for fast_power.cpp:

Functions

template<typename T >
double fast_power_recursive (T a, T b)
 
template<typename T >
double fast_power_linear (T a, T b)
 
int main ()
 

Detailed Description

Faster computation for \(a^b\).

Program that computes \(a^b\) in \(O(logN)\) time. It is based on formula that:

  1. if \(b\) is even: \(a^b = a^\frac{b}{2} \cdot a^\frac{b}{2} = {a^\frac{b}{2}}^2\)
  2. if \(b\) is odd: \(a^b = a^\frac{b-1}{2} \cdot a^\frac{b-1}{2} \cdot a = {a^\frac{b-1}{2}}^2 \cdot a\)

We can compute \(a^b\) recursively using above algorithm.

Function Documentation

◆ fast_power_linear()

template<typename T >
double fast_power_linear ( a,
b 
)

Same algorithm with little different formula. It still calculates in \(O(\log N)\)

50  {
51  // negative power. a^b = 1 / (a^-b)
52  if (b < 0)
53  return 1.0 / fast_power_linear(a, -b);
54 
55  double result = 1;
56  while (b) {
57  if (b & 1)
58  result = result * a;
59  a = a * a;
60  b = b >> 1;
61  }
62  return result;
63 }

◆ fast_power_recursive()

template<typename T >
double fast_power_recursive ( a,
b 
)

algorithm implementation for \(a^b\)

26  {
27  // negative power. a^b = 1 / (a^-b)
28  if (b < 0)
29  return 1.0 / fast_power_recursive(a, -b);
30 
31  if (b == 0)
32  return 1;
33  T bottom = fast_power_recursive(a, b >> 1);
34  // Since it is integer division b/2 = (b-1)/2 where b is odd.
35  // Therefore, case2 is easily solved by integer division.
36 
37  double result;
38  if ((b & 1) == 0) // case1
39  result = bottom * bottom;
40  else // case2
41  result = bottom * bottom * a;
42  return result;
43 }

◆ main()

int main ( void  )

Main function

68  {
69  std::srand(std::time(nullptr));
71 
72  std::cout << "Testing..." << std::endl;
73  for (int i = 0; i < 20; i++) {
74  int a = std::rand() % 20 - 10;
75  int b = std::rand() % 20 - 10;
76  std::cout << std::endl << "Calculating " << a << "^" << b << std::endl;
77  assert(fast_power_recursive(a, b) == std::pow(a, b));
78  assert(fast_power_linear(a, b) == std::pow(a, b));
79 
80  std::cout << "------ " << a << "^" << b << " = "
81  << fast_power_recursive(a, b) << std::endl;
82  }
83 
84  int64_t a, b;
85  std::cin >> a >> b;
86 
87  std::cout << a << "^" << b << " = " << fast_power_recursive(a, b)
88  << std::endl;
89 
90  std::cout << a << "^" << b << " = " << fast_power_linear(a, b) << std::endl;
91 
92  return 0;
93 }
Here is the call graph for this function:
std::srand
T srand(T... args)
fast_power_recursive
double fast_power_recursive(T a, T b)
Definition: fast_power.cpp:26
std::cout
std::rand
T rand(T... args)
std::endl
T endl(T... args)
std::ios_base::sync_with_stdio
T sync_with_stdio(T... args)
std::time
T time(T... args)
fast_power_linear
double fast_power_linear(T a, T b)
Definition: fast_power.cpp:50
std::cin
std::pow
T pow(T... args)