Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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 **/
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)
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>
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_
Definition large_number.h:24
large_number(const large_number &a)
Definition large_number.h:48
large_number()
Definition large_number.h:27
friend std::ostream & operator<<(std::ostream &out, const large_number &a)
Definition large_number.h:146
void multiply(const T n)
Definition large_number.h:258
large_number & operator++()
Definition large_number.h:175
void add_digit(unsigned int value)
Definition large_number.h:118
friend bool operator!=(large_number const &a, large_number const &b)
Definition large_number.h:168
large_number(std::vector< unsigned char > &vec)
Definition large_number.h:51
large_number & operator*=(const T n)
Definition large_number.h:238
friend bool operator==(large_number const &a, large_number const &b)
Definition large_number.h:155
unsigned char & operator[](size_t n)
Definition large_number.h:137
large_number & operator++(int)
Definition large_number.h:183
static bool test()
Definition large_number.h:65
large_number & operator+=(large_number n)
Definition large_number.h:192
large_number & operator=(const large_number &b)
Definition large_number.h:229
friend large_number & operator+(const large_number &a, const T &b)
Definition large_number.h:220
size_t num_digits() const
Definition large_number.h:130
char digit_char(size_t i) const
Definition large_number.h:248
std::vector< unsigned char > _digits
Definition large_number.h:285
large_number(int n)
Definition large_number.h:39
T endl(T... args)
T max(T... args)
T push_back(T... args)
T size(T... args)