Skip to content

Instantly share code, notes, and snippets.

@ddrone

ddrone/big_int.cpp

Created June 21, 2011 14:52
Show Gist options
  • Save ddrone/1038011 to your computer and use it in GitHub Desktop.
Save ddrone/1038011 to your computer and use it in GitHub Desktop.
Download ZIP
Big integer class with boost unit test
Raw
big_int.cpp
#include "big_int.h"
std::vector <int64> read_big_int(std::string s)
{
std::vector <int64> res;
for (int i = (int)s.length(); i > 0; i-=9)
if (i < 9)
{
res.push_back(atoi(s.substr (0, i).c_str()));
}
else
{
res.push_back(atoi(s.substr (i - 9, 9).c_str()));
}
return res;
}
big_int read(std::string s)//ââîä
{
big_int a;
std::string t;
if (s[0] == '-')
{
a.sign = true;
t.resize(s.length() - 1);
for (unsigned i = 1; i < s.length(); i++)
t[i - 1] = s[i];
}
else
{
a.sign = false;
t = s;
}
a.digits = read_big_int(t);
return a;
}
std::istream& operator>>(std::istream& in, big_int& big)
{
std::string s;
in >> s;
big = read(s);
return in;
}
int compare_without_sign(const std::vector <int64> &a, const std::vector <int64> &b, int shift)
{
if (a.size() > b.size() + shift)
return 1;
if (a.size() < b.size() + shift)
return -1;
for (int i = b.size() - 1; i >= 0; i--)
{
if (a[i + shift] > b[i])
return 1;
if (a[i + shift] < b[i])
return -1;
}
return 0;
}
int compare(const big_int &a, const big_int &b)//ñðàâíåíèå
{
if (a.sign && !b.sign)
return -1;
if (!a.sign && b.sign)
return 1;
if (a.sign && b.sign)
return -compare_without_sign(a.digits, b.digits, 0);
return compare_without_sign(a.digits, b.digits, 0);
}
void inc(std::vector <int64> &a, int shift, int factor)
{
if (a.size() == 0)
a.resize(shift + 1);
a[shift] += factor;
}
void delete_zeros(std::vector <int64> &a)
{
for (int i = a.size() - 1; i > -1; i--)
if (a[i] == 0)
a.resize(a.size() - 1);
else
return;
}
void substract_without_sign(std::vector <int64> &dividend, std::vector <int64> divider, int shift)
{
for (int i = divider.size() - 1; i > -1; i--)
{
if (dividend[i + shift] >= divider[i])
dividend[i + shift] -= divider[i];
else
{
for (unsigned j = i + shift + 1; j < dividend.size(); j++)
{
if (dividend[j] > 0)
{
dividend[j] -= 1;
for (unsigned z = i + shift + 1; z < j; z ++)
dividend[z] = base - 1;
dividend[i + shift] += base - divider[i];
break;
}
}
}
}
delete_zeros(dividend);
}
void normalize(std::vector <int64> &a)
{
unsigned numb = 0;
while (numb < a.size())
{
if (a[numb] >= base)
{
if(numb == a.size() - 1)
a.resize(a.size() + 1);
a[numb + 1] += a[numb] / base;
a[numb] %= base;
}
numb++;
}
}
std::vector <int64> sum_without_sign(std::vector <int64> a, std::vector <int64> b)
{
if (a.size() >= b.size())
{
for (unsigned i = 0; i < a.size(); i++)
a[i] += b[i];
normalize(a);
return a;
}
else
{
for (unsigned i = 0; i < b.size(); i++)
b[i] += a[i];
normalize(b);
return b;
}
}
big_int substract(big_int a, big_int b)//âû÷èòàíèå
{
big_int c;
if (a.sign == b.sign)
{
if (compare_without_sign(a.digits, b.digits, 0) >= 0)
{
c.sign = a.sign;
substract_without_sign(a.digits, b.digits, 0);
c.digits = a.digits;
}
else
{
c.sign = !a.sign;
substract_without_sign(b.digits, a.digits, 0);
c.digits = b.digits;
}
}
else
{
c.sign = a.sign;
c.digits = sum_without_sign(a.digits, b.digits);
}
return c;
}
big_int sum(big_int a, big_int b)//ñëîæåíèå
{
big_int c;
if (a.sign == b.sign)
{
c.sign = a.sign;
c.digits = sum_without_sign(a.digits, b.digits);
}
else
{
if (compare_without_sign(a.digits, b.digits, 0) >= 0)
{
c.sign = a.sign;
substract_without_sign(a.digits, b.digits, 0);
c.digits = a.digits;
}
else
{
c.sign = !a.sign;
substract_without_sign(b.digits, a.digits, 0);
c.digits = b.digits;
}
}
return c;
}
std::vector <int64> multiply_without_sign(std::vector <int64> a, std::vector <int64> b)
{
std::vector <int64> c;
c.resize(a.size() + b.size());
for (unsigned i = 0; i < a.size() + b.size(); i++)
c[i] = 0;
for (unsigned i = 0; i < a.size(); i++)
for (unsigned j = 0; j < b.size(); j++)
c[j + i] += b[j] * a[i];
normalize(c);
delete_zeros(c);
return c;
}
big_int multiply(big_int a, big_int b)//óìíîæåíèå
{
big_int c;
if (a.sign == b.sign)
c.sign = false;
else
c.sign = true;
c.digits = multiply_without_sign(a.digits, b.digits);
return c;
}
std::vector <int64> make_vector(std::vector <int64> a, int mid)
{
for (unsigned i = 0; i < a.size(); i++)
a[i] *= mid;
normalize(a);
return a;
}
void binsearch(std::vector <int64> &dividend, std::vector <int64> divider, std::vector <int64> &result, int shift)
{
int left = 0;
int right = base;
while (left < right - 1)
{
int mid = (left + right) / 2;
std::vector <int64> x = make_vector(divider, mid);
if (compare_without_sign(dividend, x, shift) >= 0)
left = mid;
else
right = mid;
}
std::vector <int64> x = make_vector(divider, left);
if (left > 0)
{
substract_without_sign(dividend, x, shift);
inc(result, shift, left);
}
}
std::string big_int_to_str(big_int a)
{
std::ostringstream help;
if (a.digits.size() == 0)
{
a.digits.resize(1);
a.digits[0] = 0;
a.sign = false;
}
if (a.sign)
help << "-";
for (int i = a.digits.size() - 1; i > -1; i--)
{
if (i != a.digits.size() - 1)
{
long long t = a.digits[i];
int k = 0;
while (t > 0)
{
t /= 10;
k++;
}
if (a.digits[i] == 0)
k = 1;
for (int j = 1; j <= base_length - k; j++)
help << "0";
}
help << a.digits[i];
}
return help.str();
}
void divide_without_sign(std::vector <int64> &dividend, std::vector <int64> divider, std::vector <int64> &result, std::vector <int64> &remind)
{
remind = dividend;
int shift = dividend.size()-divider.size();
while (shift > -1)
{
binsearch(remind, divider, result, shift);
shift--;
}
}
big_int remind(big_int a, big_int b)//îñòàòîê
{
big_int c, x;
c.sign = a.sign;
divide_without_sign(a.digits, b.digits, x.digits, c.digits);
return c;
}
big_int quotient(big_int a, big_int b)//÷àñòíîå
{
big_int c, x;
if (a.sign == b.sign)
c.sign = false;
else
c.sign = true;
divide_without_sign(a.digits, b.digits, c.digits, x.digits);
return c;
}
bool big_int::operator==(const big_int& b) const
{
return compare(*this, b) == 0;
}
bool big_int::operator<(const big_int& b) const
{
return compare(*this, b) < 0;
}
bool big_int::operator>(const big_int& b) const
{
return compare(*this, b) > 0;
}
bool big_int::operator<=(const big_int& b) const
{
return compare(*this, b) <= 0;
}
bool big_int::operator>=(const big_int& b) const
{
return compare(*this, b) >= 0;
}
bool big_int::operator!=(const big_int& b) const
{
return compare(*this, b) != 0;
}
void big_int::swap(big_int& other)
{
std::swap(sign, other.sign);
std::swap(digits, other.digits);
}
big_int::big_int(const big_int& other) : digits(other.digits), sign(other.sign)
{ }
big_int& big_int::operator=(const big_int& other)
{
digits = other.digits;
sign = other.sign;
return *this;
}
big_int::big_int(int64 data)
{
std::ostringstream help;
help << data;
*this = read(help.str());
}
big_int big_int::operator-() const
{
return substract(big_int(), *this);
}
big_int& big_int::operator+=(const big_int& other)
{
*this = sum(*this, big_int(other));
return *this;
}
big_int& big_int::operator-=(const big_int& other)
{
*this = substract(*this, big_int(other));
return *this;
}
big_int& big_int::operator%=(const big_int& other)
{
*this = remind(*this, big_int(other));
return *this;
}
big_int& big_int::operator/=(const big_int& other)
{
*this = remind(*this, big_int(other));
return *this;
}
big_int& big_int::operator*=(const big_int& other)
{
*this = multiply(*this, big_int(other));
return *this;
}
big_int big_int::operator+(const big_int& other) const
{
return sum(big_int(*this), big_int(other));
}
big_int big_int::operator-(const big_int& other) const
{
return substract(big_int(*this), big_int(other));
}
big_int big_int::operator*(const big_int& other) const
{
return multiply(big_int(*this), big_int(other));
}
big_int big_int::operator/(const big_int& other) const
{
return quotient(big_int(*this), big_int(other));
}
big_int big_int::operator%(const big_int& other) const
{
return remind(big_int(*this), big_int(other));
}
big_int abs(const big_int& arg)
{
if (arg < 0)
{
return -arg;
}
return arg;
}
std::ostream& operator<<(std::ostream& out, const big_int& big)
{
std::string str = big_int_to_str(big_int(big));
return out << str;
}
Raw
big_int.h
#pragma once
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
namespace
{
typedef long long int64;
const int64 base = 1000000000;
const int base_length = 9;
};
struct big_int
{
big_int(int64 data = 0);
big_int(const big_int&);
friend std::istream& operator>>(std::istream& in, big_int&);
friend std::ostream& operator<<(std::ostream& out, const big_int&);
bool operator==(const big_int&) const;
bool operator<=(const big_int&) const;
bool operator>=(const big_int&) const;
bool operator!=(const big_int&) const;
bool operator<(const big_int&) const;
bool operator>(const big_int&) const;
big_int& operator=(const big_int&);
void swap(big_int&);
big_int operator-() const;
big_int& operator+=(const big_int&);
big_int& operator-=(const big_int&);
big_int& operator*=(const big_int&);
big_int& operator/=(const big_int&);
big_int& operator%=(const big_int&);
big_int operator+(const big_int&) const;
big_int operator-(const big_int&) const;
big_int operator*(const big_int&) const;
big_int operator/(const big_int&) const;
big_int operator%(const big_int&) const;
friend big_int abs(const big_int&);
friend big_int read(std::string);
friend int compare(const big_int&, const big_int&);
friend big_int substract(big_int, big_int);
friend big_int sum(big_int, big_int);
friend big_int multiply(big_int, big_int);
friend std::string big_int_to_str(big_int);
friend big_int remind(big_int, big_int);
friend big_int quotient(big_int, big_int);
private:
bool sign;
std::vector<int64> digits;
};
Raw
big_int_test.cpp
#define BOOST_TEST_MODULE big_int test
#define BOOST_TEST_DYN_LINK
#define BOOST_TEST_MAIN
#include <boost/test/unit_test.hpp>
#include "big_int.h"
#include "big_int.h"
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/geometric_distribution.hpp>
#include <boost/random/bernoulli_distribution.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/foreach.hpp>
#include <string>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
using namespace boost;
#define foreach BOOST_FOREACH
const int TESTS_SIZE = 10;
namespace
{
mt19937 gen;
bool implies(bool a, bool b)
{
return !a || b;
}
big_int next_random_big_int(int length)
{
variate_generator<mt19937&, uniform_int<> > digit_generator(
gen,
uniform_int<>(0, 9));
big_int res;
for (int i = 0; i < length; ++i) {
res *= big_int(10);
res += big_int(digit_generator());
}
variate_generator<mt19937&, bernoulli_distribution<> > sign_generator(
gen,
bernoulli_distribution<>());
if (sign_generator())
return -res;
return res;
}
big_int next_random_big_int()
{
variate_generator<mt19937&, geometric_distribution<> > length_generator(
gen,
geometric_distribution<>(0.98));
int length = length_generator() - 1;
return next_random_big_int(length);
}
vector<big_int> get_numbers()
{
vector<big_int> numbers;
numbers.push_back(big_int());
numbers.push_back(big_int(1));
numbers.push_back(lexical_cast<big_int>("00000000000000000000312321"));
numbers.push_back(lexical_cast<big_int>("-0000000000000000000000312"));
generate_n(back_inserter(numbers), TESTS_SIZE - numbers.size(),
static_cast<big_int (*) ()>(next_random_big_int));
return numbers;
}
}
BOOST_AUTO_TEST_CASE( construction_test )
{
big_int a;
big_int b(42);
big_int c(-1);
big_int d(numeric_limits<int>::max());
big_int e(numeric_limits<int>::min());
big_int f(a);
big_int h(d);
}
BOOST_AUTO_TEST_CASE( arithmetic_test )
{
for (int i = -TESTS_SIZE; i <= TESTS_SIZE; ++i)
{
for (int j = -TESTS_SIZE; j <= TESTS_SIZE; ++j)
{
BOOST_CHECK_EQUAL(big_int(i) + big_int(j), big_int(i + j));
BOOST_CHECK_EQUAL(big_int(i) - big_int(j), big_int(i - j));
BOOST_CHECK_EQUAL(big_int(i) * big_int(j), big_int(i * j));
if (j != 0)
{
BOOST_CHECK_EQUAL(big_int(i) / big_int(j), big_int(i / j));
BOOST_CHECK_EQUAL(big_int(i) % big_int(j), big_int(i % j));
}
}
BOOST_CHECK_EQUAL(abs(big_int(i)), big_int(abs(i)));
}
const big_int ZERO;
const big_int ONE(1);
vector<big_int> numbers = get_numbers();
size_t size = numbers.size();
for (size_t i = 0; i < size; ++i)
{
for (size_t j = 0; j < size; ++j)
{
for (size_t k = 0; k < size; ++k)
{
// properties of integers from Wikipedia
big_int a(numbers[i]);
big_int b(numbers[j]);
big_int c(numbers[k]);
BOOST_CHECK_EQUAL(a + b, b + a);
BOOST_CHECK_EQUAL(a + (b + c), (a + b) + c);
BOOST_CHECK_EQUAL(a + ZERO, a);
BOOST_CHECK_EQUAL(ZERO + a, a);
BOOST_CHECK_EQUAL(a + (-a), ZERO);
BOOST_CHECK_EQUAL(a * b, b * a);
BOOST_CHECK_EQUAL(a * (b * c), (a * b) * c);
BOOST_CHECK_EQUAL(a * ONE, a);
BOOST_CHECK_EQUAL(a * (b + c), (a * b) + (a * c));
BOOST_CHECK_EQUAL((a + b) * c, (a * c) + (b * c));
if (a * b == ZERO)
{
BOOST_CHECK((a == ZERO) || (b == ZERO));
}
if (b != ZERO)
{
big_int q = a / b;
big_int r = a % b;
BOOST_CHECK_EQUAL(a, q * b + r);
if (a < ZERO)
{
BOOST_CHECK(r <= ZERO);
BOOST_CHECK(r > -abs(b));
}
else
{
BOOST_CHECK(r >= ZERO);
BOOST_CHECK(r < abs(b));
}
}
big_int a1(a);
(a1 += b) += c;
BOOST_CHECK_EQUAL(a1, a + b + c);
big_int a2(a);
(a2 -= b) -= c;
BOOST_CHECK_EQUAL(a2, a - b - c);
big_int a3(a);
(a3 *= b) *= c;
BOOST_CHECK_EQUAL(a3, a * b * c);
if (b != ZERO)
{
big_int a4(a);
(a4 /= b) += c;
BOOST_CHECK_EQUAL(a4, a / b + c);
big_int a5(a);
(a5 %= b) += c;
BOOST_CHECK_EQUAL(a5, a % b + c);
}
BOOST_CHECK(a <= abs(a));
BOOST_CHECK(-a <= abs(a));
BOOST_CHECK((abs(a) == a) || (abs(a) == -a));
}
}
}
}
BOOST_AUTO_TEST_CASE( comparison_test )
{
BOOST_CHECK(big_int() == big_int());
BOOST_CHECK(big_int() == big_int(0));
for (int i = -TESTS_SIZE; i <= TESTS_SIZE; ++i)
{
for (int j = -TESTS_SIZE; j <= TESTS_SIZE; ++j)
{
BOOST_CHECK_EQUAL(big_int(i) == big_int(j), i == j);
BOOST_CHECK_EQUAL(big_int(i) != big_int(j), i != j);
BOOST_CHECK_EQUAL(big_int(i) < big_int(j), i < j);
BOOST_CHECK_EQUAL(big_int(i) <= big_int(j), i <= j);
BOOST_CHECK_EQUAL(big_int(i) > big_int(j), i > j);
BOOST_CHECK_EQUAL(big_int(i) >= big_int(j), i >= j);
}
}
const big_int ZERO;
const big_int ONE(1);
vector<big_int> numbers = get_numbers();
size_t size = numbers.size();
for (size_t i = 0; i < size; ++i)
{
for (size_t j = 0; j < size; ++j)
{
for (size_t k = 0; k < size; ++k)
{
big_int a(numbers[i]);
big_int b(numbers[j]);
big_int c(numbers[k]);
big_int a1(a);
big_int a2;
a2 = a;
BOOST_CHECK_EQUAL(a, a1);
BOOST_CHECK_EQUAL(a, a2);
BOOST_CHECK(implies((a < b) && (b < c), a < c));
BOOST_CHECK(implies((a <= b) && (b <= c), a <= c));
BOOST_CHECK(implies((a > b) && (b > c), a > c));
BOOST_CHECK(implies((a >= b) && (b >= c), a >= c));
BOOST_CHECK(implies(a != b, (a < b) || (a > b)));
BOOST_CHECK(implies(a == b, (a <= b) && (a >= b)));
BOOST_CHECK_EQUAL(a < b, b > a);
BOOST_CHECK_EQUAL(a <= b, b >= a);
BOOST_CHECK_EQUAL(a < b, b > a);
BOOST_CHECK_EQUAL(a <= b, b >= a);
BOOST_CHECK_EQUAL(a == b, b == a);
BOOST_CHECK_EQUAL(a != b, b != a);
BOOST_CHECK((a < b) ^ (a >= b));
BOOST_CHECK((a > b) ^ (a <= b));
BOOST_CHECK((a == b) ^ (a != b));
BOOST_CHECK(implies(a < b, a + ONE <= b));
BOOST_CHECK(implies(a > b, a - ONE >= b));
BOOST_CHECK(implies(a == b, a + ONE > b));
BOOST_CHECK(implies(a == b, a - ONE < b));
}
}
}
}
BOOST_AUTO_TEST_CASE( swap_test )
{
big_int a(42);
big_int b(39);
big_int c(next_random_big_int());
big_int d(next_random_big_int());
big_int a1(a);
big_int b1(b);
big_int c1(c);
big_int d1(d);
a1.swap(b1);
BOOST_CHECK_EQUAL(a1, b);
BOOST_CHECK_EQUAL(b1, a);
c1.swap(d1);
BOOST_CHECK_EQUAL(c1, d);
BOOST_CHECK_EQUAL(d1, c);
a1.swap(c1);
BOOST_CHECK_EQUAL(a1, d);
BOOST_CHECK_EQUAL(c1, b);
b1.swap(d1);
BOOST_CHECK_EQUAL(b1, c);
BOOST_CHECK_EQUAL(d1, a);
big_int e(next_random_big_int());
big_int f(e);
e.swap(e);
BOOST_CHECK_EQUAL(f, e);
e = e;
BOOST_CHECK_EQUAL(f, e);
const int L = 100;
big_int long_int1 = next_random_big_int(L);
big_int long_int2 = next_random_big_int(L);
for (int i = 0; i < 1e7; ++i)
{
long_int1.swap(long_int2);
}
}
BOOST_AUTO_TEST_CASE( io_test )
{
big_int const ZERO;
BOOST_CHECK_EQUAL(lexical_cast<string>(ZERO), "0");
variate_generator<mt19937&, geometric_distribution<> > length_generator(
gen,
geometric_distribution<>(0.98));
variate_generator<mt19937&, uniform_int<> > digit_generator(
gen,
uniform_int<>(0, 9));
for (int i = 0; i < TESTS_SIZE; ++i)
{
int length = length_generator();
big_int test_int;
string string_representation;
for (int i = 0; i < length; ++i) {
test_int *= big_int(10);
int digit;
do {
digit = digit_generator();
}
while ((i == 0) && (digit == 0));
test_int += big_int(digit);
string_representation += static_cast<char>(digit + '0');
BOOST_CHECK_EQUAL(lexical_cast<string>(test_int), string_representation);
}
test_int = -test_int;
string_representation = "-" + string_representation;
BOOST_CHECK_EQUAL(lexical_cast<string>(test_int), string_representation);
}
vector<big_int> numbers = get_numbers();
size_t size = numbers.size();
for (size_t i = 0; i < size; ++i)
{
for (size_t j = 0; j < size; ++j)
{
big_int a = numbers[i];
big_int b = numbers[j];
string as = lexical_cast<string>(a);
string bs = lexical_cast<string>(b);
BOOST_CHECK_EQUAL(a == b, as == bs);
BOOST_CHECK_EQUAL(a != b, as != bs);
big_int a1 = lexical_cast<big_int>(as);
big_int b1 = lexical_cast<big_int>(bs);
BOOST_CHECK_EQUAL(a, a1);
BOOST_CHECK_EQUAL(b, b1);
}
}
vector<string> bad_strings;
bad_strings.push_back("");
bad_strings.push_back(" ");
bad_strings.push_back(" +");
bad_strings.push_back(" -");
bad_strings.push_back(" + ");
bad_strings.push_back(" - ");
bad_strings.push_back(" -z");
foreach(string const & bad_string, bad_strings)
{
istringstream iss1(bad_string);
big_int x1;
iss1 >> x1;
istringstream iss2(bad_string);
int x2;
iss2 >> x2;
std::cerr << "'" << bad_string << "'\n";
BOOST_CHECK_EQUAL(iss1.good(), iss2.good());
BOOST_CHECK_EQUAL(iss1.eof(), iss2.eof());
BOOST_CHECK_EQUAL(iss1.fail(), iss2.fail());
}
vector<string> ok_strings;
ok_strings.push_back("42");
ok_strings.push_back(" 42");
ok_strings.push_back(" 42 ");
ok_strings.push_back("\n42 ");
ok_strings.push_back("\t42 ");
ok_strings.push_back("\n\t 42 ");
ok_strings.push_back(" 42.da");
ok_strings.push_back("42 asdf");
foreach(string const & ok_string, ok_strings)
{
istringstream iss1(ok_string);
big_int x1;
string s1;
iss1 >> x1 >> s1;
istringstream iss2(ok_string);
int x2;
string s2;
iss2 >> x2 >> s2;
BOOST_CHECK_EQUAL(x1, big_int(x2));
BOOST_CHECK_EQUAL(s1, s2);
BOOST_CHECK_EQUAL(iss1.good(), iss2.good());
BOOST_CHECK_EQUAL(iss1.eof(), iss2.eof());
BOOST_CHECK_EQUAL(iss1.fail(), iss2.fail());
}
big_int test_number = lexical_cast<big_int>("87612319782231237389123382");
big_int test_number_copy(test_number);
// int test_number = 11;
// int test_number_copy(test_number);
istringstream iss("42");
iss.setstate(ios::failbit);
iss >> test_number;
BOOST_CHECK_EQUAL(test_number, test_number_copy);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment