Guest User

Untitled

a guest
Apr 19th, 2019
89
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "big_integer.h"
  2. #include <string>
  3. #include <vector>
  4.  
  5. big_integer::big_integer() {
  6. data.push_back(0);
  7. sign = false;
  8. }
  9.  
  10. big_integer::big_integer(big_integer const &other) {
  11. sign = other.sign;
  12. data = other.data;
  13. normalize();
  14. }
  15.  
  16. big_integer::big_integer(unsigned a) {
  17. sign = 0;
  18. data.push_back(a);
  19. }
  20.  
  21. big_integer::big_integer(int a) {
  22. sign = a < 0;
  23. data.push_back(a);
  24. }
  25.  
  26. big_integer::big_integer(std::string const &str) {
  27. bool start_index = !(str.empty()) && str[0] == '-';
  28. data.push_back(0);
  29. sign = false;
  30. for (size_t i = start_index; i < str.size(); ++i) {
  31. (*this) *= 10;
  32. (*this) += (str[i] - '0');
  33. }
  34. if (start_index) *this = -*this;
  35. normalize();
  36. }
  37.  
  38. big_integer::~big_integer() {
  39. data.clear();
  40. }
  41.  
  42. big_integer &big_integer::operator=(big_integer const &other) {
  43. data = other.data;
  44. sign = other.sign;
  45. return *this;
  46. }
  47.  
  48. bool big_integer::operator==(big_integer const &other) const {
  49. return data == other.data && sign == other.sign;
  50. }
  51.  
  52. bool big_integer::operator!=(big_integer const &other) const {
  53. return !(*this == other);
  54. }
  55.  
  56. bool big_integer::operator<=(big_integer const &other) const {
  57. if (sign != other.sign) return sign;
  58. if (data.size() != other.data.size()) {
  59. return sign ^ (data.size() < other.data.size());
  60. }
  61. for (size_t i = data.size() - 1; i < data.size(); --i) {
  62. if (data[i] != other.data[i]) {
  63. return sign ^ (data[i] < other.data[i]);
  64. }
  65. }
  66. return true;
  67. }
  68.  
  69. bool big_integer::operator>(big_integer const &other) const {
  70. return !(*this <= other);
  71. }
  72.  
  73. bool big_integer::operator<(big_integer const &other) const {
  74. return (*this <= other) && (*this != other);
  75. }
  76.  
  77. bool big_integer::operator>=(big_integer const &other) const {
  78. return !(*this < other);
  79. }
  80.  
  81. big_integer &big_integer::operator+=(big_integer const &other) {
  82. ull carry = 0;
  83. std::vector<unsigned> res(std::max(other.data.size(), data.size()) + 1);
  84. for (size_t i = 0; i < res.size(); ++i) {
  85. ull sum = carry + get_digit(i) + other.get_digit(i);
  86. res[i] = static_cast<unsigned>(sum);
  87. carry = sum / BASE;
  88. }
  89. data = res;
  90. sign = data.back() & (1 << (BASE_SIZE - 1));
  91. normalize();
  92. return *this;
  93. }
  94.  
  95. big_integer &big_integer::operator-=(big_integer const &other) {
  96. return *this += (-other);
  97. }
  98.  
  99.  
  100. big_integer &big_integer::operator*=(big_integer const &other) {
  101. big_integer a(abs());
  102. big_integer b(other.abs());
  103. if (a == 0 || b == 0) {
  104. *this = 0;
  105. return *this;
  106. }
  107. big_integer res(0);
  108. res.data.resize(a.length() + b.length() + 1, 0);
  109. for (size_t i = 0; i < a.length(); ++i) {
  110. unsigned carry = 0;
  111. for (size_t j = 0; j < b.length(); ++j) {
  112. ull sum = res.data[i + j] + static_cast<ull>(a.data[i]) * b.data[j] + carry;
  113. res.data[i + j] = sum;
  114. carry = sum / BASE;
  115. }
  116. size_t x = b.length();
  117. while (carry != 0) {
  118. ull sum = static_cast<ull>(res.data[i + x]) + carry;
  119. res.data[i + x] = sum;
  120. carry = sum / BASE;
  121. x++;
  122. }
  123. }
  124. if (sign ^ other.sign) {
  125. *this = -res;
  126. } else {
  127. *this = res;
  128. }
  129. normalize();
  130. return *this;
  131. }
  132.  
  133. big_integer &big_integer::operator/=(big_integer const &other) {
  134. if (other == 0) {
  135. throw std::runtime_error("Division by zero");
  136. }
  137. big_integer a = abs();
  138. big_integer b = other.abs();
  139. if (a < b) {
  140. *this = 0;
  141. return *this;
  142. }
  143. if (a == b) {
  144. *this = 1;
  145. return *this;
  146. }
  147. big_integer res(0), mod(0);
  148. unsigned f = (BASE / (b.data.back() + 1ll));
  149. a *= f;
  150. b *= f;
  151. size_t n = a.data.size(), m = b.data.size();
  152. data.resize(n, 0);
  153. std::vector<unsigned> data(n - m + 1);
  154. mod = a >> ((n - m + 1) * BASE_SIZE);
  155. ull top = b.data.back();
  156. for (size_t i = 0; i <= n - m; ++i) {
  157. size_t idx = n - m - i;
  158. mod <<= BASE_SIZE;
  159. mod.data[0] = a.data[idx];
  160. ull mod_top = mod.data.back();
  161. if (mod.data.size() > m) {
  162. mod_top <<= BASE_SIZE;
  163. mod_top += mod.data[mod.data.size() - 2];
  164. }
  165. unsigned guess = std::min(mod_top / top, BASE - 1);
  166. big_integer res_guess = guess * b;
  167. while (mod < res_guess) {
  168. guess--;
  169. res_guess -= b;
  170. }
  171. data[idx] = guess;
  172. mod -= res_guess;
  173. }
  174. big_integer tmp(false, data);
  175. tmp.normalize();
  176. sign ^= other.sign;
  177. if (sign) {
  178. tmp = -tmp;
  179. }
  180. *this = tmp;
  181. normalize();
  182. return *this;
  183. }
  184.  
  185. big_integer &big_integer::operator&=(big_integer const &other) {
  186. for (size_t i = 0; i < data.size(); ++i) {
  187. data[i] &= other.get_digit(i);
  188. }
  189. sign &= other.sign;
  190. normalize();
  191. return *this;
  192. }
  193.  
  194. big_integer &big_integer::operator^=(big_integer const &other) {
  195. for (size_t i = 0; i < std::max(data.size(), other.data.size()); ++i) {
  196. if (i < data.size()) data[i] ^= other.get_digit(i);
  197. else data.push_back(other.data[i]);
  198. }
  199. sign ^= other.sign;
  200. normalize();
  201. return *this;
  202. }
  203.  
  204. big_integer &big_integer::operator|=(big_integer const &other) {
  205. for (size_t i = 0; i < std::max(data.size(), other.data.size()); ++i) {
  206. if (i < data.size()) data[i] |= other.get_digit(i);
  207. else data.push_back(other.data[i]);
  208. }
  209. sign |= other.sign;
  210. normalize();
  211. return *this;
  212. }
  213.  
  214. big_integer &big_integer::operator<<=(int a) {
  215. if (a < 0) {
  216. return (*this) >>= a;
  217. }
  218. size_t div = a >> 5;
  219. size_t mod = a & (BASE_SIZE - 1);
  220. size_t new_size = length() + div + 1;
  221. std::vector<unsigned> temp(new_size);
  222. temp[div] = static_cast<unsigned >(static_cast<ull>(get_digit(0)) << mod);
  223. for (size_t i = div + 1; i < new_size; i++) {
  224. unsigned x = static_cast<ull >(get_digit(i - div)) << mod;
  225. unsigned y = static_cast<ull>(data[i - div - 1]) >> (BASE_SIZE - mod);
  226. temp[i] = x | y;
  227. }
  228. data = temp;
  229. normalize();
  230. return *this;
  231. }
  232.  
  233. big_integer &big_integer::operator>>=(int a) {
  234. if (a < 0) {
  235. return (*this) <<= a;
  236. }
  237. size_t div = a >> 5;
  238. unsigned mod = a & (BASE_SIZE - 1);
  239. size_t new_size = 0;
  240. if (div < (*this).length()) {
  241. new_size = (*this).length() - div;
  242. }
  243. std::vector<unsigned> temp(new_size);
  244. for (size_t i = 0; i < new_size; i++) {
  245. unsigned x = static_cast<ull>(data[i + div]) >> mod;
  246. unsigned y = static_cast<ull>(get_digit(i + div + 1)) << (BASE_SIZE - mod);
  247. temp[i] = x | y;
  248. }
  249. data = temp;
  250. normalize();
  251. return *this;
  252. }
  253.  
  254.  
  255. big_integer &big_integer::operator%=(big_integer const &other) {
  256. normalize();
  257. big_integer a = (*this / other) * other;
  258. return *this -= a;
  259. }
  260.  
  261. big_integer big_integer::operator-() const {
  262. if (*this == 0) {
  263. return *this;
  264. }
  265. big_integer tmp(*this);
  266. tmp = ~tmp;
  267. ++tmp;
  268. tmp.sign = !sign;
  269. return tmp;
  270. }
  271.  
  272. big_integer big_integer::operator+() const {
  273. big_integer tmp(*this);
  274. return tmp;
  275. }
  276.  
  277. big_integer &big_integer::operator++() {
  278. normalize();
  279. return *this += 1;
  280. }
  281.  
  282. big_integer big_integer::operator++(int) {
  283. normalize();
  284. big_integer tmp = *this;
  285. ++(*this);
  286. return tmp;
  287. }
  288.  
  289. big_integer &big_integer::operator--() {
  290. normalize();
  291. return *this -= 1;
  292. }
  293.  
  294. big_integer big_integer::operator--(int) {
  295. normalize();
  296. big_integer tmp(*this);
  297. --(*this);
  298. return tmp;
  299. }
  300.  
  301. big_integer big_integer::operator~() const {
  302. big_integer tmp(*this);
  303. for (size_t i = 0; i < tmp.data.size(); ++i) {
  304. tmp.data[i] = ~data[i];
  305. }
  306. tmp.sign = !tmp.sign;
  307. return tmp;
  308. }
  309.  
  310. big_integer big_integer::abs() const {
  311. if (sign) return -(*this);
  312. return *this;
  313. }
  314.  
  315. void big_integer::swap(big_integer &b) {
  316. big_integer temp(*this);
  317. sign = b.sign;
  318. data = b.data;
  319. b.sign = temp.sign;
  320. b.data = temp.data;
  321. normalize();
  322. }
  323.  
  324. const unsigned big_integer::get_digit(size_t i) const {
  325. if (i < data.size()) return data[i];
  326. if (sign) return MAX_VALUE;
  327. return 0;
  328. }
  329.  
  330. bool big_integer::below_zero() const {
  331. return sign;
  332. }
  333.  
  334. big_integer::big_integer(bool negate, std::vector<unsigned> const &data) {
  335. this->data = data;
  336. sign = negate;
  337. normalize();
  338. }
  339.  
  340. void big_integer::normalize() {
  341. while (data.size() > 1 && ((data.back() == 0 && !sign) || (data.back() == MAX_VALUE && sign))) {
  342. data.pop_back();
  343. }
  344. }
  345.  
  346. size_t big_integer::length() const {
  347. return data.size();
  348. }
  349.  
  350. big_integer operator+(big_integer a, big_integer const &b) {
  351. return a += b;
  352. }
  353.  
  354. big_integer operator-(big_integer a, big_integer const &b) {
  355. return a -= b;
  356. }
  357.  
  358. big_integer operator*(big_integer a, big_integer const &b) {
  359. return a *= b;
  360. }
  361.  
  362. big_integer operator/(big_integer a, big_integer const &b) {
  363. return a /= b;
  364. }
  365.  
  366. big_integer operator%(big_integer a, big_integer const &b) {
  367. return a %= b;
  368. }
  369.  
  370. big_integer operator&(big_integer a, big_integer const &b) {
  371. return a &= b;
  372. }
  373.  
  374. big_integer operator^(big_integer a, big_integer const &b) {
  375. return a ^= b;
  376. }
  377.  
  378. big_integer operator|(big_integer a, big_integer const &b) {
  379. return a |= b;
  380. }
  381.  
  382. big_integer operator<<(big_integer a, int b) {
  383. return a <<= b;
  384. }
  385.  
  386. big_integer operator>>(big_integer a, int b) {
  387. return a >>= b;
  388. }
  389.  
  390. std::string to_string(big_integer const &value) {
  391. big_integer a = value.abs();
  392. if (value == 0) {
  393. return "0";
  394. }
  395. std::string s;
  396. while (a != 0) {
  397. unsigned val = (a % 10).get_digit(0);
  398. s.push_back(val + '0');
  399. a /= 10;
  400. }
  401. if (value.below_zero()) {
  402. s.push_back('-');
  403. }
  404. std::reverse(s.begin(), s.end());
  405. return s;
  406. }
RAW Paste Data