Representing Large Fixed-Width Integers

Problem

You need to perform arithmetic of numbers larger than can be represented by a long int.

Solution

The BigInt template in Example 11-38 uses the bitset from the header to allow you to represent unsigned integers using a fixed number of bits specified as a template parameter.

Example 11-38. big_int.hpp

#ifndef BIG_INT_HPP
#define BIG_INT_HPP

#include 

#include "bitset_arithmetic.hpp" // Recipe 11.20

template
class BigInt
{
 typedef BigInt self;
public:
 BigInt( ) : bits( ) { }
 BigInt(const self& x) : bits(x.bits) { }
 BigInt(unsigned long x) {
 int n = 0;
 while (x) {
 bits[n++] = x & 0x1;
 x >>= 1;
 }
 }
 explicit BigInt(const std::bitset& x) : bits(x) { }

 // public functions
 bool operator[](int n) const { return bits[n]; }
 unsigned long toUlong( ) const { return bits.to_ulong( ); }

 // operators
 self& operator<<=(unsigned int n) {
 bits <<= n;
 return *this;
 }
 self& operator>>=(unsigned int n) {
 bits >>= n;
 return *this;
 }
 self operator++(int) {
 self i = *this;
 operator++( );
 return i;
 }
 self operator--(int) {
 self i = *this;
 operator--( );
 return i;
 }
 self& operator++( ) {
 bool carry = false;
 bits[0] = fullAdder(bits[0], 1, carry);
 for (int i = 1; i < N; i++) {
 bits[i] = fullAdder(bits[i], 0, carry);
 }
 return *this;
 }
 self& operator--( ) {
 bool borrow = false;
 bits[0] = fullSubtractor(bits[0], 1, borrow);
 for (int i = 1; i < N; i++) {
 bits[i] = fullSubtractor(bits[i], 0, borrow);
 }
 return *this;
 }
 self& operator+=(const self& x) {
 bitsetAdd(bits, x.bits);
 return *this;
 }
 self& operator-=(const self& x) {
 bitsetSubtract(bits, x.bits);
 return *this;
 }
 self& operator*=(const self& x) {
 bitsetMultiply(bits, x.bits);
 return *this;
 }
 self& operator/=(const self& x) {
 std::bitset tmp;
 bitsetDivide(bits, x.bits, bits, tmp);
 return *this;
 }
 self& operator%=(const self& x) {
 std::bitset tmp;
 bitsetDivide(bits, x.bits, tmp, bits);
 return *this;
 }
 self operator~( ) const { return ~bits; }
 self& operator&=(self x) { bits &= x.bits; return *this; }
 self& operator|=(self x) { bits |= x.bits; return *this; }
 self& operator^=(self x) { bits ^= x.bits; return *this; }

 // friend functions
 friend self operator<<(self x, unsigned int n) { return x <<= n; }
 friend self operator>>(self x, unsigned int n) { return x >>= n; }
 friend self operator+(self x, const self& y) { return x += y; }
 friend self operator-(self x, const self& y) { return x -= y; }
 friend self operator*(self x, const self& y) { return x *= y; }
 friend self operator/(self x, const self& y) { return x /= y; }
 friend self operator%(self x, const self& y) { return x %= y; }
 friend self operator^(self x, const self& y) { return x ^= y; }
 friend self operator&(self x, const self& y) { return x &= y; }
 friend self operator|(self x, const self& y) { return x |= y; }

 // comparison operators
 friend bool operator==(const self& x, const self& y) {
 return x.bits == y.bits;
 }
 friend bool operator!=(const self& x, const self& y) {
 return x.bits != y.bits;
 }
 friend bool operator>(const self& x, const self& y) {
 return bitsetGt(x.bits, y.bits);
 }
 friend bool operator<(const self& x, const self& y) {
 return bitsetLt(x.bits, y.bits);
 }
 friend bool operator>=(const self& x, const self& y) {
 return bitsetGtEq(x.bits, y.bits);
 }
 friend bool operator<=(const self& x, const self& y) {
 return bitsetLtEq(x.bits, y.bits);
 }
private:
 std::bitset bits;
};

#endif

The BigInt template class could be used to represent factorials, as shown in Example 11-39.

Example 11-39. Using the big_int class

#include "big_int.hpp"

#include 
#include 
#include 
#include 

using namespace std;

void outputBigInt(BigInt<1024> x) {
 vector v;
 if (x == 0) {
 cout << 0;
 return;
 }
 while (x > 0) {
 v.push_back((x % 10).to_ulong( ));
 x /= 10;
 }
 copy(v.rbegin( ), v.rend( ), ostream_iterator(cout, ""));
 cout << endl;
}

int main( ) {
 BigInt<1024> n(1);
 // compute 32 factorial
 for (int i=1; i <= 32; ++i) {
 n *= i;
 }
 outputBigInt(n);
}

The program in Example 11-39 outputs:

263130836933693530167218012160000000

 

Discussion

Large integers are common in many applications. In cryptography, for example, integers of 1,000 bits and larger are not uncommon. However, the current C++ standard provides integers only as large as a long int.

The number of bits in a long int is implementation specific, but is guaranteed to be at least 32. And t probably won't ever be as large as 1,000. Remember that one of those bits is reserved for the sign.

The next version of the standard (C++ 0x) is expected to follow the C99 standard and provide a long long type that will be defined as being at least as large as a long int, and possibly bigger. Despite this there will always be occasions where an integer type larger than the largest primitive is needed.

The implementation I presented here is based on a binary representation of numbers using a bitset, at a cost of some performance. What I lost in performance I more than made up for in simplicity. A more efficient implementation of arbitrary precision numbers could easily fill the book.

See Also

Recipe 11.19