Blog Archives

Representing Large Fixed-Width Integers in C++

Large integers are common in many applications. In cryptography, for example, integers of 1,000 bits and larger are not uncommon. 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.

The BigInt template below uses the bitset from the header to (from my last post) allow you to represent unsigned integers using a fixed number of bits specified as a template parameter.


//big_int.hpp
#ifndef BIG_INT_HPP
#define BIG_INT_HPP
#include <bitset>
#include "bitset_arithmetic.hpp" // from my last post of bitset manipulation.
template<unsigned int N>
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<N> bits;
};

The BigInt template class could be used to represent factorials, as shown below,


//Using the big_int class
#include "big_int.hpp"
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
void outputBigInt(BigInt<1024> x) {
vector<int> 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 output is:
263130836933693530167218012160000000

 

Binary Search Tree template Class (BST)

Let’s see the code of the binary search tree (BST). This is a continuation of another article where I have explained the BST in detail. Please review that article as well. (link is below) We put the interface in the .h file. We also have the state variable in addition to the public and private methods of the class in it. In the public methods, the user of the class calls with their objects.

Here is the code of the program. BinarySearchTree.h file.

/* This file contains the declaration of binary node and the binary search tree */

#ifndef BINARY_SEARCH_TREE_H_
#define BINARY_SEARCH_TREE_H_

#include <iostream.h>     // For NULL

// Binary node and forward declaration
template <class EType> class BinarySearchTree;

template <class EType> class BinaryNode
{
EType element; BinaryNode *left; BinaryNode *right;
BinaryNode( const EType & theElement, BinaryNode *lt, BinaryNode *rt ) : element( theElement ), left( lt ), right( rt ) { }

friend class BinarySearchTree<EType>;
};

// BinarySearchTree class

CONSTRUCTION:  with  ITEM_NOT_FOUND  object  used  to signal  failed finds

// ******************PUBLIC  OPERATIONS*********************
// void insert( x )     --> Insert x
// void remove( x )     --> Remove x
// EType find( x )   --> Return item that matches x
// EType findMin( )  --> Return smallest item
// EType findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )     --> Remove all items
// void printTree( )     --> Print tree in sorted order

template <class EType> class BinarySearchTree
{
public:
BinarySearchTree( const EType & notFound ); BinarySearchTree( const BinarySearchTree & rhs );
~BinarySearchTree( );

const EType & findMin( ) const;
const EType & findMax( ) const;
const EType & find( const EType & x ) const;
bool isEmpty( ) const;
void printTree( ) const;

void makeEmpty( );
void insert( const EType & x );
void remove( const EType & x );

const BinarySearchTree & operator=( const BinarySearchTree & rhs );

private:
BinaryNode<EType> *root;
const EType ITEM_NOT_FOUND;

const EType & elementAt( BinaryNode<EType> *t ) const;

void insert( const EType & x, BinaryNode<EType> * & t ) const;
void remove( const EType & x, BinaryNode<EType> * & t ) const;
BinaryNode<EType> * findMin( BinaryNode<EType> *t ) const;
BinaryNode<EType> * findMax( BinaryNode<EType> *t ) const;
BinaryNode<EType>  *  find(  const  EType  &  x,  BinaryNode<EType>  *t  ) const;

void makeEmpty( BinaryNode<EType> * & t ) const;
void printTree( BinaryNode<EType> *t ) const; BinaryNode<EType> * clone( BinaryNode<EType> *t ) const;
};
#include "BinarySearchTree.cpp"
#endif

/*BinarySearchTree.cpp  file.*/

/* This file contains the implementation of the binary search tree */

#include <iostream.h>
#include "BinarySearchTree.h"

/**
* Construct the tree.
*/
template <class EType> BinarySearchTree<EType>::BinarySearchTree(const EType & notFound) : ITEM_NOT_FOUND( notFound), root( NULL )
{
}

/**
* Copy constructor.
*/

template<classEType>BinarySearchTree<EType>::BinarySearchTree(const BinarySearchTree<EType> & rhs )
:root( NULL ), ITEM_NOT_FOUND(rhs.ITEM_NOT_FOUND)
{
*this = rhs;
}

/**
* Destructor for the tree.
*/
template<classEType>BinarySearchTree<EType>::~BinarySearchTree ()
{
makeEmpty( );
}

/**
* Insert x into the tree; duplicates are ignored.
*/
template <class EType> void BinarySearchTree<EType>::insert( const EType & x )
{
insert( x, root );
}

/**
* Remove x from the tree. Nothing is done if x is not found.
*/
template <class EType> void BinarySearchTree<EType>::remove(  const EType & x )
{
remove( x, root );
}

/**
* Find the smallest item in the tree.
* Return smallest item or ITEM_NOT_FOUND if empty.
*/
template <class EType> const EType & BinarySearchTree<EType>::findMin() const
{
return elementAt( findMin( root ) );
}

/**
* Find the largest item in the tree.
* Return the largest item of ITEM_NOT_FOUND if empty.
*/
template <class EType> const EType & BinarySearchTree<EType>::findMax() const
{
return elementAt( findMax( root ) );
}

/**
* Find item x in the tree.
* Return the matching item or ITEM_NOT_FOUND if not found.
*/
template <class EType>const EType & BinarySearchTree<EType>::find( const EType & x ) const
{
return elementAt( find( x, root ) );
}

/**
* Make the tree logically empty.
*/
template <class EType> void BinarySearchTree<EType>::makeEmpty()
{
makeEmpty( root );
}

/**
* Test if the tree is logically empty.
* Return true if empty, false otherwise.
*/
template <class EType> bool BinarySearchTree<EType>::isEmpty( ) const
{
return root == NULL;
}

/**
* Print the tree contents in sorted order.
*/
template <class EType> void BinarySearchTree<EType>::printTree() const
{
if( isEmpty( ) )
cout << "Empty tree" << endl;
else
printTree( root );
}

/**
* Deep copy.
*/
template <class EType> const BinarySearchTree<EType> & BinarySearchTree<EType>::operator=( const BinarySearchTree<EType> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
root = clone( rhs.root );
}
return *this;
}

/**
* Internal method to get element field in node t.
* Return the element field or ITEM_NOT_FOUND if t is NULL.
*/
template <class EType> const EType & BinarySearchTree<EType>::elementAt(BinaryNode<EType>*t) const
{
if( t == NULL )
return ITEM_NOT_FOUND;
else
return t->element;
}

/**
* Internal method to insert into a subtree.
* x is the item to insert.
* t is the node that roots the tree.

* Set the new root.
*/
template <class EType> void BinarySearchTree<EType>::insert( const EType & x, BinaryNode<EType> * & t ) const
{
if( t == NULL )
t = new BinaryNode<EType>( x, NULL, NULL );
else if( x < t->element )
insert( x, t->left ); else if( t->element < x ) insert( x, t->right );
else
;  // Duplicate; do nothing
}

/**
* Internal method to remove from a subtree.
* x is the item to remove.
* t is the node that roots the tree.
* Set the new root.
*/
template <class EType> void BinarySearchTree<EType>::remove(const EType & x, BinaryNode<EType>
* & t ) const
{
if( t == NULL )
return;   // Item not found; do nothing
if( x < t->element )
remove( x, t->left );
else if( t->element < x )
remove( x, t->right );
else if( t->left != NULL && t->right != NULL ) // Two children
{
t->element = findMin( t->right )->element;
remove( t->element, t->right );
}
else
{
BinaryNode<EType> *nodeToDelete = t;
t = ( t->left!= NULL ) ? t->left : t->right;
delete nodeToDelete;
}
}

/**
* Internal method to find the smallest item in a subtree t.
* Return node containing the smallest item.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::findMin( BinaryNode<EType>*t) const
{
if( t == NULL )
return NULL;
if( t->left == NULL )
return t;
return findMin( t->left );
}

/**
* Internal method to find the largest item in a subtree t.
* Return node containing the largest item.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::findMax( BinaryNode<EType> *t ) const
{
if( t != NULL )
while( t->right != NULL )
{
t = t->right;
}
return t;
}

/**
* Internal method to find an item in a subtree.
* x is item to search for.
* t is the node that roots the tree.
* Return node containing the matched item.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::
find( const EType & x, BinaryNode<EType> *t ) const
{
if( t == NULL )
return NULL;
else if( x < t->element )
return find( x, t->left );
else if( t->element < x )
return find( x, t->right );
else
return t;     // Match
}
/****** NONRECURSIVE VERSION*************************
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::find( const EType & x, BinaryNode<EType> *t ) const
{
while( t != NULL )
if( x < t->element )
t = t->left;
else if( t->element < x )
t = t->right;
else
return t;     // Match

return NULL;   // No match
}
*****************************************************/

/**
* Internal method to make subtree empty.
*/
template <class EType> void BinarySearchTree<EType>::makeEmpty( BinaryNode<EType> * & t ) const
{
if( t != NULL )
{
makeEmpty( t->left ); makeEmpty( t->right ); delete t;
}
t = NULL;
}

/**
* Internal method to print a subtree rooted at t in sorted order.
*/
template <class EType> void BinarySearchTree<EType>::printTree( BinaryNode<EType> *t ) const
{
if( t != NULL )
{
printTree( t->left );
cout << t->element << endl;
printTree( t->right );
}
}

/**
* Internal method to clone subtree.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::clone(  BinaryNode<EType> * t ) const
{
if( t == NULL )
return NULL;
else
return  new  BinaryNode<EType>(  t->element,  clone(  t->left  ),  clone(  t->right ) );
}