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

Compute powers of large numbers. More...

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

Macros

#define MAX   100000
 

Functions

int multiply (int x, int res[], int res_size)
 
void power (int x, int n)
 
int main ()
 

Detailed Description

Compute powers of large numbers.

Macro Definition Documentation

◆ MAX

#define MAX   100000

Maximum number of digits in output \(x^n\) where \(1 <= x,\; n <= 10000\) and overflow may happen

Function Documentation

◆ main()

int main ( void  )

Main function

82  {
83  int exponent, base;
84  std::cout << "Enter base ";
85  std::cin >> base;
86  std::cout << "Enter exponent ";
87  std::cin >> exponent;
88  power(base, exponent);
89  return 0;
90 }
Here is the call graph for this function:

◆ multiply()

int multiply ( int  x,
int  res[],
int  res_size 
)

This function multiplies x with the number represented by res[]. res_size is size of res[] or number of digits in the number represented by res[]. This function uses simple school mathematics for multiplication. This function may value of res_size and returns the new value of res_size

Parameters
xmultiplicand
reslarge number representation using array
res_sizenumber of digits in res
25  {
26  // Initialize carry
27  int carry = 0;
28 
29  // One by one multiply n with
30  // individual digits of res[]
31  for (int i = 0; i < res_size; i++) {
32  int prod = res[i] * x + carry;
33 
34  // Store last digit of
35  // 'prod' in res[]
36  res[i] = prod % 10;
37 
38  // Put rest in carry
39  carry = prod / 10;
40  }
41 
42  // Put carry in res and
43  // increase result size
44  while (carry) {
45  res[res_size] = carry % 10;
46  carry = carry / 10;
47  res_size++;
48  }
49  return res_size;
50 }

◆ power()

void power ( int  x,
int  n 
)

This function finds power of a number x and print \(x^n\)

Parameters
xbase
nexponent
56  {
57  // printing value "1" for power = 0
58  if (n == 0) {
59  std::cout << "1";
60  return;
61  }
62 
63  int res[MAX];
64  int res_size = 0;
65  int temp = x;
66 
67  // Initialize result
68  while (temp != 0) {
69  res[res_size++] = temp % 10;
70  temp = temp / 10;
71  }
72 
73  // Multiply x n times
74  // (x^n = x*x*x....n times)
75  for (int i = 2; i <= n; i++) res_size = multiply(x, res, res_size);
76 
77  std::cout << x << "^" << n << " = ";
78  for (int i = res_size - 1; i >= 0; i--) std::cout << res[i];
79 }
Here is the call graph for this function:
multiply
int multiply(int x, int res[], int res_size)
Definition: power_for_huge_numbers.cpp:25
power
void power(int x, int n)
Definition: power_for_huge_numbers.cpp:56
std::cout
std::cin
MAX
#define MAX
Definition: power_for_huge_numbers.cpp:10