Diggins PDP #3 : arbitrary precision integers

[christopher diggins]

// big_int.hpp
// The Diggins PDP (Public Domain Post) #3
// Public Domain code by Christopher Diggins, May 22, 2005
//
// Description:
// A naively implemented unsigned integer type for arbitrarily large
// values. Implemented using vector<bool>

#ifndef BIG_INT_HPP
#define BIG_INT_HPP

#include <limits>
#include <vector>
#include <algorithm>
#include <functional>
#include <stdexcept>
#include <cassert>
#include <iostream>
#include "binary_arithmetic.hpp" // Diggins PDP #1.2

#include <cassert>

namespace cdiggins
{
class big_int_impl
{
typedef big_int_impl self;
public:
self() {
}
self(const big_int_impl& x) : bits(x.bits) {
}
self(const std::vector<bool>& x) : bits(x) {
bits = x;
}
self(int x) {
while (x) {
bits.push_back(x & 0x1);
x >>= 1;
}
}
self& operator=(const std::vector<bool>& x) {
bits = x;
return *this;
}
self& operator<<=(int n) {
if (n == 0) return *this;
resize(size() + n);
for (int i=size() - 1; i >= n; i--) {
bits[i] = bits[i - n];
}
for (int i=n-1; i >= 0; i--) {
bits[i] = false;
}
truncate_leading_zeros();
return *this;
}
self& operator>>=(int n) {
if (n == 0) return *this;
if (n >= size()) return *this = 0;
for (int i=0; i < size() - n; i++) {
bits[i] = bits[i + n];
}
resize(size() - n);
return *this;
}
self operator++(int) {
self i = *this;
operator+=(1);
return i;
}
self operator--(int) {
self i = *this;
operator-=(1);
return i;
}
self& operator++() {
operator+=(1);
return *this;
}
self& operator--() {
operator-=(1);
return *this;
}
self& operator+=(const self& x) {
bool carry = false;
if (x.size() > size()) resize(x.size());
for (int i = 0; i < size(); i++) {
bits[i] = full_adder(bits[i], x[i], carry);
}
if (carry) {
resize(size() + 1);
bits[size() - 1] = 1;
}
truncate_leading_zeros();
return *this;
}
self& operator-=(const self& x) {
assert(x <= *this);
if (x == 0) return *this;
bool borrow = false;
for (int i = 0; i < size(); i++) {
bits[i] = full_subtractor(bits[i], x[i], borrow);
}
assert(!borrow); // should be no borrowing
truncate_leading_zeros();
return *this;
}
self& operator*=(self x) {
std::vector<bool> v = bits;
*this = 0;
for (int i=0; i < static_cast<int>(v.size()); i++)
{
if (v[i]) {
*this += x;
}
x <<= 1;
}
return *this;
}
self& operator/=(const self& x) {
return *this = divide_quotient(*this, x);
}
self& operator%=(const self& x) {
return *this = divide_remainder(*this, x);
}
self operator~() const {
std::vector<bool> v = bits;
for (int i=0; i<static_cast<int>(v.size()); i++) {
v[i] = !v[i];
}
return v;
}
self& operator&=(self x) {
if (x.size() > size()) {
resize(x.size());
}
if (x.size() < size()) {
x.resize(size());
}
std::transform(bits.begin(), bits.end(), x.bits.begin(), bits.begin(),
std::logical_and<bool>());
truncate_leading_zeros();
return *this;
}
self& operator|=(self x) {
if (x.size() > size()) {
resize(x.size());
}
if (x.size() < size()) {
x.resize(size());
}
std::transform(bits.begin(), bits.end(), x.bits.begin(), bits.begin(),
std::logical_or<bool>());
truncate_leading_zeros();
return *this;
}
self& operator^=(self x) {
if (x.size() > size()) {
resize(x.size());
}
if (x.size() < size()) {
x.resize(size());
}
std::transform(bits.begin(), bits.end(), x.bits.begin(), bits.begin(),
&logical_xor<bool>);
truncate_leading_zeros();
return *this;
}
bool operator[](int n) const {
if (n >= size()) return false;
return bits[n];
}
int size() const {
return static_cast<int>(bits.size());
}
unsigned long to_ulong() {
int digits = std::numeric_limits<unsigned long>::digits;
if (size() >= digits) {
throw std::domain_error("out of range for unsigned long");
}
unsigned long ret = 0;
unsigned long tmp = 1;
for (int i=0; i < digits; i++) {
if (operator[](i)) {
ret |= tmp;
}
tmp <<= 1;
}
return ret;
}
// friend functions
friend self operator<<(const self& x, unsigned int n) {
return self(x) <<= n;
}
friend self operator>>(const self& x, unsigned int n) {
return self(x) >>= n;
}
friend self operator+(const self& x, const self& y) {
return self(x) += y;
}
friend self operator-(const self& x, const self& y) {
return self(x) -= y;
}
friend self operator*(const self& x, const self& y) {
return self(x) *= y;
}
friend self operator/(const self& x, const self& y) {
return self(x) /= y;
}
friend self operator%(const self& x, const self& y) {
return self(x) %= y;
}
friend self operator^(const self& x, const self& y) {
return self(x) ^= y;
}
friend self operator&(const self& x, const self& y) {
return self(x) &= y;
}
friend self operator|(const self& x, const self& y) {
return self(x) |= y;
}
// comparison operators
friend bool operator==(const self& x, const self& y) {
if (x.size() != y.size()) return false;
for (int i=0; i < x.size(); i++) {
if (x[i] != y[i]) {
return false;
}
}
return true;
}
friend bool operator!=(const self& x, const self& y) {
return !(x == y);
}
friend bool operator>(const self& x, const self& y) {
int i = x.size();
if (i > y.size()) return true;
if (i < y.size()) return false;
while (i--) {
if (x[i] > y[i]) return true;
if (x[i] < y[i]) return false;
}
return false;
}
friend bool operator<(const self& x, const self& y) {
int i = x.size();
if (i > y.size()) return false;
if (i < y.size()) return true;
while (i--) {
if (x[i] > y[i]) return false;
if (x[i] < y[i]) return true;
}
return false;
}
friend bool operator>=(const self& x, const self& y) {
return (x > y) || (x == y);
}
friend bool operator<=(const self& x, const self& y) {
return (x < y) || (x == y);
}
private:
void resize(int n) {
int old = size();
bits.resize(n);
for (int i=old; i < n; i++) {
bits[i] = false;
}
}
void truncate_leading_zeros() {
int sig_digit = -1;
for (int i=0; i<size(); i++) {
if (bits[i]) {
sig_digit = static_cast<int>(i);
}
}
resize(sig_digit + 1);
}
std::vector<bool> bits;
};

typedef big_int_impl big_int;
}

///////////////////////////////////////////////////
// test code

#include <iostream>
#include <iterator>

void test_failure(const char* x) {
std::cerr << "TEST failed " << x << std::endl;
}
#define TEST(TKN) if (!(TKN)) { test_failure(#TKN); } /* */

namespace big_int_test
{
using namespace cdiggins;

std::ostream& operator<<(std::ostream& o, big_int x)
{
std::vector<int> v;
if (x == 0) {
o << 0;
return o;
}
while (x > 0) {
v.push_back((x % 10).to_ulong());
x /= 10;
}
std::copy(v.rbegin(), v.rend(), std::ostream_iterator<int>(o));
return o;
}

// makes a big int as a power of base to the power
big_int make_big_int(int base, int power) {
big_int ret = 1;
for (int i=0; i < power; i++) {
ret *= base;
}
return ret;
}

void simple_test(big_int n)
{
big_int original = n;
std::cout << n << std::endl;

TEST(n == n);
TEST(n >= n);
TEST(n <= n);
TEST(!(n < n));
TEST(!(n > n));
TEST(n != 0);
TEST(!(n == 0));
TEST(n > 0);
TEST(n >= 0);
TEST(!(n < 0));
TEST(!(n <= 0));

TEST((n >> 1) <= n);
TEST((n << 1) >= n);

TEST(0 + n == n);
TEST(n + 0 == n);
TEST(n - 0 == n);
TEST(n - n == 0);
TEST(n * 1 == n);
TEST(n * 0 == 0);
TEST(n / 1 == n);
TEST(n / n == 1);
TEST(n % n == 0);
TEST(n % 1 == 0);

TEST((n += 0) == n);
TEST(n == original);
TEST((n -= 0) == n);
TEST(n == original);
TEST((n *= 1) == n);
TEST(n == original);
TEST((n /= 1) == n);
TEST(n == original);

TEST(n != n + 1);
TEST(n < n + 1);
TEST(n < n * 2);
TEST(n <= n * n);
TEST(n != (n - 1));
TEST(n > (n - 1));
TEST(n == original);

TEST((n & 1) == n[0]);
TEST((n & 1) == n % 2);
TEST((n & ~n) == 0);
TEST((n | n) == n);
TEST(((n ^ n) ^ n) == n);
TEST(n == original);

TEST(n * 2 == n << 1);
TEST(n * 2 == n + n);
TEST(n + n + n == n * 2 + n);
TEST(n + n + n == n * 3);
TEST(n / 2 == n >> 1);
TEST((n * 3) / 3 == n);
TEST(n == original);
TEST(n * 2 == n * 3 - n);
TEST(n == (n / 2) * 2 + (n % 2));
TEST(n == (n / 3) * 3 + (n % 3));
TEST(n == original);

big_int m = n;
for (int i=0; i<16; i++) {
TEST(m++ == n + i);
}
while (--m > n) { }

TEST(m == n);
TEST(m++ == n);
TEST(m == n + 1);
TEST(++m == n + 2);
TEST(m-- == n + 2);
TEST(--m == n);
TEST(m == n);
TEST(--m == n - 1);
TEST(n == original);
}

void test_main()
{
// check out all the small numbers
int i=1;
for (; i<64; i++) {
std::cout << "testing " << i << std::endl;
simple_test(i);
}
// check out some bigger numbers
for (; i<640; i += 13) {
std::cout << "testing " << i << std::endl;
simple_test(i);
}
// check out some even bigger numbers
for (; i<6400; i += 151) {
std::cout << "testing " << i << std::endl;
simple_test(i);
}
// check out various powers of two
for (int i=4; i < 64; i++) {
std::cout << "testing 2 raised to the power of " << i << std::endl;
simple_test(make_big_int(2, i));
}
// check out various powers of three
for (int i=2; i < 32; i++) {
std::cout << "testing 3 raised to the power of " << i << std::endl;
simple_test(make_big_int(3, i));
}
// check out various powers of five
for (int i=2; i < 20; i++) {
std::cout << "testing 5 raised to the power of " << i << std::endl;
simple_test(make_big_int(5, i));
}
// check out various powers of eleven
for (int i=2; i < 10; i++) {
std::cout << "testing 11 raised to the power of " << i << std::endl;
simple_test(make_big_int(11, i));
}
}
}

#endif