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

Building C++ Applications

Code Organization

Numbers

Strings and Text

Dates and Times

Managing Data with Containers

Algorithms

Classes

Exceptions and Safety

Streams and Files

Science and Mathematics

Multithreading

Internationalization

XML

Miscellaneous

Index

show all menu





C++ Cookbook
Secure Programming Cookbook for C and C++: Recipes for Cryptography, Authentication, Input Validation & More
ISBN: 0596003943
EAN: 2147483647
Year: 2006
Pages: 241
Similar book on Amazon

Flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net