Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
large_number.h
Go to the documentation of this file.
1 /**
2  * @file
3  * @brief Library to perform arithmatic operations on arbitrarily large
4  * numbers.
5  * \author [Krishna Vedala](https://github.com/kvedala)
6  */
7 
8 #ifndef MATH_LARGE_NUMBER_H_
9 #define MATH_LARGE_NUMBER_H_
10 #include <algorithm>
11 #include <cassert>
12 #include <cinttypes>
13 #include <cstring>
14 #include <iostream>
15 #include <type_traits>
16 #include <vector>
17 
18 /**
19  * Store large unsigned numbers as a C++ vector
20  * The class provides convenience functions to add a
21  * digit to the number, perform multiplication of
22  * large number with long unsigned integers.
23  **/
24 class large_number {
25  public:
26  /**< initializer with value = 1 */
28 
29  // /**< initializer from an integer */
30  // explicit large_number(uint64_t n) {
31  // uint64_t carry = n;
32  // do {
33  // add_digit(carry % 10);
34  // carry /= 10;
35  // } while (carry != 0);
36  // }
37 
38  /**< initializer from an integer */
39  explicit large_number(int n) {
40  int carry = n;
41  do {
42  add_digit(carry % 10);
43  carry /= 10;
44  } while (carry != 0);
45  }
46 
47  /**< initializer from another large_number */
49 
50  /**< initializer from a vector */
52 
53  /**< initializer from a string */
54  explicit large_number(char const *number_str) {
55  for (size_t i = strlen(number_str); i > 0; i--) {
56  char a = number_str[i - 1] - '0';
57  if (a >= 0 && a <= 9)
58  _digits.push_back(a);
59  }
60  }
61 
62  /**
63  * Function to check implementation
64  **/
65  static bool test() {
66  std::cout << "------ Checking `large_number` class implementations\t"
67  << std::endl;
68  large_number a(40);
69  // 1. test multiplication
70  a *= 10;
71  if (a != large_number(400)) {
72  std::cerr << "\tFailed 1/6 (" << a << "!=400)" << std::endl;
73  return false;
74  }
75  std::cout << "\tPassed 1/6...";
76  // 2. test compound addition with integer
77  a += 120;
78  if (a != large_number(520)) {
79  std::cerr << "\tFailed 2/6 (" << a << "!=520)" << std::endl;
80  return false;
81  }
82  std::cout << "\tPassed 2/6...";
83  // 3. test compound multiplication again
84  a *= 10;
85  if (a != large_number(5200)) {
86  std::cerr << "\tFailed 3/6 (" << a << "!=5200)" << std::endl;
87  return false;
88  }
89  std::cout << "\tPassed 3/6...";
90  // 4. test increment (prefix)
91  ++a;
92  if (a != large_number(5201)) {
93  std::cerr << "\tFailed 4/6 (" << a << "!=5201)" << std::endl;
94  return false;
95  }
96  std::cout << "\tPassed 4/6...";
97  // 5. test increment (postfix)
98  a++;
99  if (a != large_number(5202)) {
100  std::cerr << "\tFailed 5/6 (" << a << "!=5202)" << std::endl;
101  return false;
102  }
103  std::cout << "\tPassed 5/6...";
104  // 6. test addition with another large number
105  a = a + large_number("7000000000000000000000000000000");
106  if (a != large_number("7000000000000000000000000005202")) {
107  std::cerr << "\tFailed 6/6 (" << a
108  << "!=7000000000000000000000000005202)" << std::endl;
109  return false;
110  }
111  std::cout << "\tPassed 6/6..." << std::endl;
112  return true;
113  }
114 
115  /**
116  * add a digit at MSB to the large number
117  **/
118  void add_digit(unsigned int value) {
119  if (value > 9) {
120  std::cerr << "digit > 9!!\n";
121  exit(EXIT_FAILURE);
122  }
123 
124  _digits.push_back(value);
125  }
126 
127  /**
128  * Get number of digits in the number
129  **/
130  size_t num_digits() const { return _digits.size(); }
131 
132  /**
133  * operator over load to access the
134  * i^th digit conveniently and also
135  * assign value to it
136  **/
137  inline unsigned char &operator[](size_t n) { return this->_digits[n]; }
138 
139  inline const unsigned char &operator[](size_t n) const {
140  return this->_digits[n];
141  }
142 
143  /**
144  * operator overload to compare two numbers
145  **/
147  for (size_t i = a.num_digits(); i > 0; i--)
148  out << static_cast<int>(a[i - 1]);
149  return out;
150  }
151 
152  /**
153  * operator overload to compare two numbers
154  **/
155  friend bool operator==(large_number const &a, large_number const &b) {
156  size_t N = a.num_digits();
157  if (N != b.num_digits())
158  return false;
159  for (size_t i = 0; i < N; i++)
160  if (a[i] != b[i])
161  return false;
162  return true;
163  }
164 
165  /**
166  * operator overload to compare two numbers
167  **/
168  friend bool operator!=(large_number const &a, large_number const &b) {
169  return !(a == b);
170  }
171 
172  /**
173  * operator overload to increment (prefix)
174  **/
176  (*this) += 1;
177  return *this;
178  }
179 
180  /**
181  * operator overload to increment (postfix)
182  **/
184  static large_number tmp(_digits);
185  ++(*this);
186  return tmp;
187  }
188 
189  /**
190  * operator overload to add
191  **/
193  // if adding with another large_number
194  large_number *b = reinterpret_cast<large_number *>(&n);
195  const size_t max_L = std::max(this->num_digits(), b->num_digits());
196  unsigned int carry = 0;
197  size_t i;
198  for (i = 0; i < max_L || carry != 0; i++) {
199  if (i < b->num_digits())
200  carry += (*b)[i];
201  if (i < this->num_digits())
202  carry += (*this)[i];
203  if (i < this->num_digits())
204  (*this)[i] = carry % 10;
205  else
206  this->add_digit(carry % 10);
207  carry /= 10;
208  }
209  return *this;
210  }
211 
212  large_number &operator+=(int n) { return (*this) += large_number(n); }
213  // large_number &operator+=(uint64_t n) { return (*this) += large_number(n);
214  // }
215 
216  /**
217  * operator overload to perform addition
218  **/
219  template <class T>
220  friend large_number &operator+(const large_number &a, const T &b) {
221  static large_number c = a;
222  c += b;
223  return c;
224  }
225 
226  /**
227  * assignment operator
228  **/
230  this->_digits = b._digits;
231  return *this;
232  }
233 
234  /**
235  * operator overload to increment
236  **/
237  template <class T>
238  large_number &operator*=(const T n) {
239  static_assert(std::is_integral<T>::value,
240  "Must be integer addition unsigned integer types.");
241  this->multiply(n);
242  return *this;
243  }
244 
245  /**
246  * returns i^th digit as an ASCII character
247  **/
248  char digit_char(size_t i) const {
249  return _digits[num_digits() - i - 1] + '0';
250  }
251 
252  private:
253  /**
254  * multiply large number with another integer and
255  * store the result in the same large number
256  **/
257  template <class T>
258  void multiply(const T n) {
259  static_assert(std::is_integral<T>::value,
260  "Can only have integer types.");
261  // assert(!(std::is_signed<T>::value)); //, "Implemented only for
262  // unsigned integer types.");
263 
264  size_t i;
265  uint64_t carry = 0, temp;
266  for (i = 0; i < this->num_digits(); i++) {
267  temp = static_cast<uint64_t>((*this)[i]) * n;
268  temp += carry;
269  if (temp < 10) {
270  carry = 0;
271  } else {
272  carry = temp / 10;
273  temp = temp % 10;
274  }
275  (*this)[i] = temp;
276  }
277 
278  while (carry != 0) {
279  this->add_digit(carry % 10);
280  carry /= 10;
281  }
282  }
283 
285  _digits; /**< where individual digits are stored */
286 };
287 
288 #endif // MATH_LARGE_NUMBER_H_
binExpo
int binExpo(int a, int b)
Definition: binary_exponent.cpp:28
large_number::add_digit
void add_digit(unsigned int value)
Definition: large_number.h:118
std::srand
T srand(T... args)
main
int main()
Definition: double_factorial.cpp:67
main
int main()
Definition: gcd_of_n_numbers.cpp:28
std::domain_error
STL class.
test1
bool test1()
Definition: large_factorial.cpp:17
std::clock_t
gcd
int gcd(int num1, int num2)
Definition: gcd_iterative_euclidean.cpp:15
Complex
Class Complex to represent complex numbers as a field.
Definition: complex_numbers.cpp:20
main
int main()
Main function.
Definition: fibonacci.cpp:62
large_number::operator<<
friend std::ostream & operator<<(std::ostream &out, const large_number &a)
Definition: large_number.h:146
large_number::large_number
large_number(std::vector< unsigned char > &vec)
Definition: large_number.h:51
std::atan2
T atan2(T... args)
update_step
void update_step(T *r, T *r0, const T2 quotient)
Definition: extended_euclid_algorithm.cpp:24
double_factorial_iterative
uint64_t double_factorial_iterative(uint64_t n)
Definition: double_factorial.cpp:17
std::cos
T cos(T... args)
std::vector< unsigned char >
std::vector::size
T size(T... args)
Complex::arg
double arg() const
Member function to give the argument of our complex number.
Definition: complex_numbers.cpp:87
Complex::operator*
Complex operator*(const Complex &other)
Operator overload of '*' on Complex class. Operator overload to be able to multiple two complex numbe...
Definition: complex_numbers.cpp:117
large_number
Definition: large_number.h:24
fib
large_number fib(uint64_t n)
Definition: fibonacci_large.cpp:24
main
int main()
Definition: fibonacci_fast.cpp:51
Complex::operator-
Complex operator-(const Complex &other)
Operator overload of '-' on Complex class. Operator overload to be able to subtract two complex numbe...
Definition: complex_numbers.cpp:106
Complex::Complex
Complex(const Complex &other)
Copy Constructor.
Definition: complex_numbers.cpp:58
Complex::Complex
Complex(double x=0.f, double y=0.f, bool is_polar=false)
Complex Constructor which initialises our complex number.
Definition: complex_numbers.cpp:43
Complex::abs
double abs() const
Member function to give the modulus of our complex number. Member function to which gives the absolut...
Definition: complex_numbers.cpp:79
main
int main(int argc, char *argv[])
Definition: large_factorial.cpp:89
gcd
int gcd(int num1, int num2)
Definition: gcd_recursive_euclidean.cpp:14
large_number.h
Library to perform arithmatic operations on arbitrarily large numbers.
get_rand
double get_rand()
Function to get random numbers to generate our complex numbers for test.
Definition: complex_numbers.cpp:201
binExpo_alt
int binExpo_alt(int a, int b)
Definition: binary_exponent.cpp:42
tests
void tests()
Definition: complex_numbers.cpp:206
Complex::operator=
const Complex & operator=(const Complex &other)
Operator overload of '=' on Complex class. Operator overload to be able to copy RHS instance of Compl...
Definition: complex_numbers.cpp:160
main
int main()
Definition: gcd_recursive_euclidean.cpp:42
large_number::num_digits
size_t num_digits() const
Definition: large_number.h:130
std::sqrt
T sqrt(T... args)
large_number::operator+=
large_number & operator+=(large_number n)
Definition: large_number.h:192
is_prime
bool is_prime(T num)
Definition: check_prime.cpp:22
fast_power_recursive
double fast_power_recursive(T a, T b)
Definition: fast_power.cpp:26
std::vector::push_back
T push_back(T... args)
test
void test(uint64_t n, uint64_t expected)
Definition: double_factorial.cpp:42
std::clock
T clock(T... args)
Complex::real
double real() const
Member function to get real value of our complex number. Member function (getter) to access the class...
Definition: complex_numbers.cpp:64
large_number::large_number
large_number(const large_number &a)
Definition: large_number.h:48
test
static void test()
Definition: fibonacci.cpp:35
large_number::operator*=
large_number & operator*=(const T n)
Definition: large_number.h:238
large_number::large_number
large_number()
Definition: large_number.h:27
main
int main()
Main function.
Definition: binary_exponent.cpp:55
Complex::operator/
Complex operator/(const Complex &other)
Operator overload of '/' on Complex class. Operator overload to be able to divide two complex numbers...
Definition: complex_numbers.cpp:142
large_number::operator++
large_number & operator++()
Definition: large_number.h:175
large_number::digit_char
char digit_char(size_t i) const
Definition: large_number.h:248
fibonacci
uint64_t fibonacci(uint64_t n)
Definition: fibonacci.cpp:19
large_number::operator[]
unsigned char & operator[](size_t n)
Definition: large_number.h:137
std::cout
phiFunction
uint64_t phiFunction(uint64_t n)
Definition: eulers_totient_function.cpp:32
main
int main()
Definition: factorial.cpp:15
large_number::multiply
void multiply(const T n)
Definition: large_number.h:258
Complex::operator~
Complex operator~() const
Operator overload of '~' on Complex class. Operator overload of the BITWISE NOT which gives us the co...
Definition: complex_numbers.cpp:130
operator<<
std::ostream & operator<<(std::ostream &os, const Complex &num)
Operator overload of '<<' of ostream for Complex class. Overloaded insersion operator to accommodate ...
Definition: complex_numbers.cpp:186
std::complex::real
T real(T... args)
large_number::operator=
large_number & operator=(const large_number &b)
Definition: large_number.h:229
main
int main()
Main function.
Definition: extended_euclid_algorithm.cpp:87
fib
uint64_t fib(uint64_t n)
Definition: fibonacci_fast.cpp:30
std::invalid_argument
STL class.
operator==
bool operator==(const Complex &a, const Complex &b)
Operator overload of '==' on Complex class. Logical Equal overload for our Complex class.
Definition: complex_numbers.cpp:175
large_number::_digits
std::vector< unsigned char > _digits
Definition: large_number.h:285
std::is_integral
main
int main()
Definition: check_prime.cpp:45
test2
bool test2()
Definition: large_factorial.cpp:54
std::rand
T rand(T... args)
std::swap
T swap(T... args)
std::sin
T sin(T... args)
sum_of_divisor
int sum_of_divisor(int num)
Definition: check_amicable_pair.cpp:21
Complex::imag
double imag() const
Member function to get imaginary value of our complex number. Member function (getter) to access the ...
Definition: complex_numbers.cpp:70
large_number::test
static bool test()
Definition: large_number.h:65
std::endl
T endl(T... args)
main
int main()
Definition: complex_numbers.cpp:268
large_number::operator==
friend bool operator==(large_number const &a, large_number const &b)
Definition: large_number.h:155
factorial
unsigned int factorial(unsigned int n)
Definition: factorial.cpp:8
tests
void tests()
Definition: double_factorial.cpp:50
std::ios_base::sync_with_stdio
T sync_with_stdio(T... args)
gcd
int gcd(int *a, int n)
Definition: gcd_of_n_numbers.cpp:15
main
int main()
Definition: fast_power.cpp:68
double_factorial_recursive
uint64_t double_factorial_recursive(uint64_t n)
Definition: double_factorial.cpp:30
std::scientific
T scientific(T... args)
std::strtoull
T strtoull(T... args)
extendedEuclid
void extendedEuclid(T A, T B, T *GCD, T2 *x, T2 *y)
Definition: extended_euclid_algorithm.cpp:70
test
void test()
Definition: check_amicable_pair.cpp:56
std::complex
STL class.
std::complex::imag
T imag(T... args)
large_number::large_number
large_number(int n)
Definition: large_number.h:39
std::time
T time(T... args)
Complex::operator+
Complex operator+(const Complex &other)
Operator overload of '+' on Complex class. Operator overload to be able to add two complex numbers.
Definition: complex_numbers.cpp:95
extendedEuclid_1
void extendedEuclid_1(T1 A, T1 B, T1 *GCD, T2 *x, T2 *y)
Definition: extended_euclid_algorithm.cpp:41
main
int main()
Definition: gcd_iterative_euclidean.cpp:47
std::max
T max(T... args)
large_number::operator!=
friend bool operator!=(large_number const &a, large_number const &b)
Definition: large_number.h:168
fast_power_linear
double fast_power_linear(T a, T b)
Definition: fast_power.cpp:50
std::cin
large_number::operator++
large_number & operator++(int)
Definition: large_number.h:183
main
int main(int argc, char *argv[])
Main function.
Definition: eulers_totient_function.cpp:48
large_number::operator+
friend large_number & operator+(const large_number &a, const T &b)
Definition: large_number.h:220
are_amicable
bool are_amicable(int x, int y)
Definition: check_amicable_pair.cpp:48
main
int main()
Definition: check_amicable_pair.cpp:68
machine_learning::sum
T sum(const std::vector< std::valarray< T >> &A)
Definition: vector_ops.hpp:232
main
int main()
Definition: graph_coloring.cpp:96
std::pow
T pow(T... args)