biguint - Simple Optimized Big Unsigned Integer Library

biguint.h

/*
Big Unsigned Integer Library (biguint).
Written by Tien La.

User can do anything with this library, since there, I don't have any responsibility about any damage that may occur.
For any question or suggestion, please email me at [email protected] or via Facebook: fb.com/cariyaputta
This library is mainly for demonstration but still quite optimized and pretty fast.

All functions in this library don't return value (except 'GMP' function), instead, they use references to speed things up.
The rule of these function is almost the same: first argument is the result of the function, except 'cmp' and 'wl'.
*/
#pragma once // '#pragma once' is non-standard but useful and cross-platform, this make sure the following headers are only include once across multiple files
#include <vector>
#include <string>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

namespace lvtbi {

	typedef vector<int> biguint; // big unsigned integer implement in base 10,000 (10^4)

	/* The runtime (in second) of all core functions when no. digits (count in base 10) = 1,000,000: */
	// add : 0.001                                      (implement optimized standard addition algorithm)
	// sub : 0.001                                      (implement optimized standard subtraction algorithm)
	// stablemul : too long / 5.800 with 100,000 digits (implement optimized standard multiplication algorithm)
	// mul : 26.400         / 0.700 with 100,000 digits (implement optimized Karatsuba multiplication algorithm)
	/* Tested on Intel Core i5 5500 2.2 GHz */

	// Utility functions

	void rl(biguint& res) {
		// read a line from stdin then convert to biguint
		string s;
		getline(cin, s);
		int n = s.size();
		int t = n % 4;
		n = t == 0 ? n : n + 4 - t;
		res.resize(n / 4);
		t = n - s.size();
		s.insert(0, t, '0');
		t = n / 4;
		int j = 0;
		for (int i = 0; i < t; ++i) {
			int num = s[j++] - 48;
			num = num * 10 + s[j++] - 48;
			num = num * 10 + s[j++] - 48;
			num = num * 10 + s[j++] - 48;
			res[i] = num;
		}
	}
	void rl(biguint& res, ifstream& fi) {
		// read a line of text from file then convert to biguint
		string s;
		getline(fi, s);
		int n = s.size();
		int t = n % 4;
		n = t == 0 ? n : n + 4 - t;
		res.resize(n / 4);
		t = n - s.size();
		s.insert(0, t, '0');
		t = n / 4;
		int j = 0;
		for (int i = 0; i < t; ++i) {
			int num = s[j++] - 48;
			num = num * 10 + s[j++] - 48;
			num = num * 10 + s[j++] - 48;
			num = num * 10 + s[j++] - 48;
			res[i] = num;
		}
	}
	void wl(const biguint& x) {
		// write a line of biguint to stdout
		int n = x.size();
		if (n == 0) {
			return;
		}
		cout << x[0];
		for (int i = 1; i < n; ++i) {
			if (x[i] / 1000 == 0) {
				cout << '0';
			}
			if (x[i] / 100 == 0) {
				cout << '0';
			}
			if (x[i] / 10 == 0) {
				cout << '0';
			}
			cout << x[i];
		}
		cout << '\n';
	}
	void wl(const biguint& x, ofstream& fo) {
		// write a line of biguint to a file
		int n = x.size();
		if (n == 0) {
			return;
		}
		fo << x[0];
		for (int i = 1; i < n; ++i) {
			if (x[i] / 1000 == 0) {
				fo << '0';
			}
			if (x[i] / 100 == 0) {
				fo << '0';
			}
			if (x[i] / 10 == 0) {
				fo << '0';
			}
			fo << x[i];
		}
		fo << '\n';
	}
	void initrd() {
		// initialize randomization
		srand(time(nullptr));
	}
	void rd(biguint& res, int n) {
		// random a biguint with 'n' digits (count in base 10)
		if (n < 1) {
			n = 4;
		}
		n = n % 4 == 0 ? n / 4 : n / 4 + 1;
		res.resize(n);
		res[0] = 1 + rand() % 9999;
		for (int i = 1; i < n; ++i) {
			res[i] = rand() % 10000;
		}
	}
	void del0(biguint& res) {
		// delete trailing zeros at the beginning of biguint
		int n = res.size() - 1;
		int i = 0;
		for (; i < n; ++i) {
			if (res[i] != 0) {
				break;
			}
		}
		res.erase(res.begin(), res.begin() + i);
	}
	void fromint(biguint& res, int n) {
		// convert a int to biguint
		if (n < 1) {
			res.clear();
			res.push_back(0);
			return;
		}
		int tn = n;
		int t = 0;
		while (tn != 0) {
			tn /= 10000;
			++t;
		}
		res.resize(t);
		int i = 0;
		while (n != 0) {
			res[t - 1 - i++] = n % 10000;
			n /= 10000;
		}
	}
	void fromnum(biguint& res, long long n) {
		// convert a long long int to biguint
		if (n < 1) {
			res.clear();
			res.push_back(0);
			return;
		}
		long long tn = n;
		int t = 0;
		while (tn != 0) {
			tn /= 10000;
			++t;
		}
		res.resize(t);
		int i = 0;
		while (n != 0) {
			res[t - 1 - i++] = n % 10000;
			n /= 10000;
		}
	}
	void ncopy_unsafe(biguint& res, const biguint& source, const int l, const int r) {
		// copy 'source' to 'res', start at position l and end at position r of 'source'
		// because it does not perform any bounce checking so user is advised not to use this function
		res.clear();
		for (int i = l; i <= r; ++i) {
			res.push_back(source[i]);
		}
	}

	// Core functions

	int cmp(const biguint& x, const biguint& y) {
		// compare two bigints
		int nx = x.size();
		int ny = y.size();
		int i = 0, j = 0;
		for (; i < nx - 1; ++i) {
			if (x[i] != 0) {
				break;
			}
		}
		for (; j < ny - 1; ++j) {
			if (y[j] != 0) {
				break;
			}
		}
		nx -= i;
		ny -= j;
		if (nx != ny) {
			return nx > ny ? 1 : -1;
		}
		for (int k = 0; k < nx; ++k) {
			if (x[i + k] != y[j + k]) {
				return x[i + k] > y[j + k] ? 1 : -1;
			}
		}
		return 0;
	}
	void exp(biguint& res, const int n) {
		// exp(res, n) = res * 10 ^ n
		if (res.size() == 1 && res[0] == 0) {
			return;
		}
		for (int i = 0; i < n; ++i) {
			res.push_back(0);
		}
	}
	void add(biguint& res, const biguint& x, const biguint& y) {
		// add two biguint
		int nx = x.size();
		int ny = y.size();
		int n = nx > ny ? nx : ny;
		res.resize(n);
		int r = 0;
		if (nx >= ny) {
			int k = nx - ny;
			for (int i = n - 1; i >= k; --i) {
				int t = x[i] + y[i - k] + r;
				res[i] = t % 10000;
				r = t / 10000;
			}
			for (int i = k - 1; i >= 0; --i) {
				int t = x[i] + r;
				res[i] = t % 10000;
				r = t / 10000;
			}
		}
		else {
			int k = ny - nx;
			for (int i = n - 1; i >= k; --i) {
				int t = y[i] + x[i - k] + r;
				res[i] = t % 10000;
				r = t / 10000;
			}
			for (int i = k - 1; i >= 0; --i) {
				int t = y[i] + r;
				res[i] = t % 10000;
				r = t / 10000;
			}
		}
		if (r != 0) {
			res.insert(res.begin(), r);
		}
	}
	void sub(biguint& res, const biguint& x, const biguint& y) {
		// subtract two bigints, return to 'res' the absolute value of the result (avoid negative value)
		int nx = x.size();
		int ny = y.size();
		int c = cmp(x, y);
		if (c == 0) {
			res.clear();
			res.push_back(0);
			return;
		}
		int n = nx > ny ? nx : ny;
		res.resize(n);
		int r = 0;
		if (c == 1) {
			int k = nx - ny;
			for (int i = n - 1; i >= k; --i) {
				int t = x[i] + 10000 - y[i - k] - r;
				res[i] = t % 10000;
				r = x[i] < y[i - k] + r ? 1 : 0;
			}
			for (int i = k - 1; i >= 0; --i) {
				int t = x[i] + 10000 - r;
				res[i] = t % 10000;
				r = x[i] < r ? 1 : 0;
			}
		}
		else {
			int k = ny - nx;
			for (int i = n - 1; i >= k; --i) {
				int t = y[i] + 10000 - x[i - k] - r;
				res[i] = t % 10000;
				r = y[i] < x[i - k] + r ? 1 : 0;
			}
			for (int i = k - 1; i >= 0; --i) {
				int t = y[i] + 10000 - r;
				res[i] = t % 10000;
				r = y[i] < r ? 1 : 0;
			}
		}
		del0(res);
	}
	void stablemul(biguint& res, const biguint& x, const biguint& y) {
		// multiply two bigints, space: O(1); time: O(n^2); become slow when the no. digits highly rise
		int nx = x.size();
		int ny = y.size();
		res.clear();
		res.push_back(0);
		for (int i = nx - 1; i >= 0; --i) {
			if (x[i] == 0) {
				continue;
			}
			biguint temp(ny);
			int r = 0;
			for (int j = ny - 1; j >= 0; --j) {
				int t = x[i] * y[j] + r;
				temp[j] = t % 10000;
				r = t / 10000;
			}
			if (r != 0) {
				temp.insert(temp.begin(), r);
			}
			exp(temp, nx - i - 1);
			add(res, res, temp);
		}
		del0(res);
	}
	void mulrun_unsafe(biguint& res, biguint& x, biguint& y); // prototype for the use of 'mul' function
	void mul(biguint& res, const biguint& x, const biguint& y) {
		// multiply two bigints, space: O(nlgn); time: O(n^lg3) so pretty fast as the no. digits rising
		biguint tx = x;
		biguint ty = y;
		mulrun_unsafe(res, tx, ty);
	}
	void mulrun_unsafe(biguint& res, biguint& x, biguint& y) {
		// this is the run function of 'mul'
		// because it modify the arguments so user is advised not to use this function
		int nx = x.size();
		int ny = y.size();
		int n = nx > ny ? nx : ny;
		if (n < 100) {
			stablemul(res, x, y);
			return;
		} // if length of both number less than 100, switch to 'stablemul', this is how the optimization performs
		x.insert(x.begin(), n - nx, 0);
		y.insert(y.begin(), n - ny, 0);
		if (n % 2 != 0) {
			x.insert(x.begin(), 0);
			y.insert(y.begin(), 0);
			++n;
		} // make both bignums equal in length and have an even length
		int hn = n / 2;
		biguint a, b, c, d, u, v, w, t1, t2, t3, t4, t5;
		ncopy_unsafe(a, x, 0, hn - 1);
		ncopy_unsafe(b, x, hn, n - 1);
		ncopy_unsafe(c, y, 0, hn - 1);
		ncopy_unsafe(d, y, hn, n - 1);
		mulrun_unsafe(u, a, c); // u = a * c
		mulrun_unsafe(v, b, d); // v = b * d
		add(t1, a, b); // t1 = a + b
		add(t2, c, d); // t2 = c + d
		mulrun_unsafe(t3, t1, t2); // t3 = t1 * t2 = (a + b) * (c + d)
		sub(t4, t3, u); // t4 = t3 - u = (a + b) * (c + d) - u
		sub(w, t4, v); // w = t4 - v = (a + b) * (c + d) - u - v
		exp(u, n); // u = u * B ^ n (B is base, with is 10,000)
		exp(w, hn); // w = w * B ^ (n / 2)
		add(t5, u, w); // t5 = u + w
		add(res, t5, v); // res = t5 + v = u + w + v
	}

	// Experimental functions



	// Advanced functions

	void fbn(biguint& res, const int n) {
		// calculate the n_th Fibonacci number
		if (n < 1) {
			res.clear();
			res.push_back(0);
			return;
		}
		if (n < 3) {
			res.clear();
			res.push_back(1);
			return;
		}
		biguint a(1, 1);
		biguint b(1, 1);
		for (int i = 3; i <= n; ++i) {
			add(res, a, b);
			a = b;
			b = res;
		}
	}
	void ftr(biguint& res, const int n) {
		// calculate the factorial of 'n' (n!)
		res.clear();
		res.push_back(1);
		if (n < 2) {
			return;
		}
		biguint t;
		for (int i = 2; i <= n; ++i) {
			fromint(t, i);
			mul(res, res, t);
		}
	}

}