Diggins PDP #3 : arbitrary precision integers

Discussion in 'C++' started by christopher diggins, May 24, 2005.

  1. // 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 = bits[i - n];
    }
    for (int i=n-1; i >= 0; i--) {
    bits = 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 = 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 = full_adder(bits, x, 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 = full_subtractor(bits, x, 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) {
    *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 = !v;
    }
    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 != y) {
    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 > y) return true;
    if (x < y) 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 > y) 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::eek:stream& operator<<(std::eek:stream& 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::eek:stream_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[/i][/i][/i][/i]
    christopher diggins, May 24, 2005
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. christopher diggins
    Replies:
    4
    Views:
    641
    christopher diggins
    May 22, 2005
  2. christopher diggins
    Replies:
    1
    Views:
    381
    Rapscallion
    May 23, 2005
  3. christopher diggins
    Replies:
    0
    Views:
    438
    christopher diggins
    May 24, 2005
  4. christopher diggins

    Diggins PDP #4 : FFT (Fast Fourier Transform)

    christopher diggins, Jun 2, 2005, in forum: C++
    Replies:
    0
    Views:
    498
    christopher diggins
    Jun 2, 2005
  5. christopher diggins
    Replies:
    1
    Views:
    340
    christopher diggins
    Jun 3, 2005
Loading...

Share This Page