C++ Integer Class

The author no longer maintains this project.

• Download demo project - 48 Kb

Introduction

This is a class which encapsulates very large integers, using a fixed array of double words. It is coded in C++ and uses some inline assembly.

Background

The biggest problem implementing class Integer was figuring out how to represent the data. The actual data would be stored in a member array: Unit Data[MaxSize], where Unit is a typedef of unsigned __int32, and MaxSize is a static const of value 32 (which can be changed). I decided that Data would not be a pointer to a heap array because the code runs three times faster without calling new or realloc for every function. UnitLen is an unsigned which keeps track of how many members of array Data are used.

The biggest problem was deciding if an integer is positive, negative, or zero, because it would be inefficient to scan Data from 0 to UnitLen-1 to discern between a positive number and zero. int SigBit keeps track of both the sign of the Integer and the most significant bit of data. If SigBit is equal to zero, then the Integer is zero. If SigBit is positive, then it equals the index of the most significant bit plus one. If SigBit is negative, then it equals the negation of the index of the most significant bit minus 2. For example, for 0x00000002, SigBit = 2, and for 0xFFFFFFFE, SigBit = -2.

I implemented some of the arithmetic functions using inline assembly in order to cut down the time. In other places, I used regular C++ arithmetic (instead of bit-manipulation, as in the non-assembly half of Integer::Div()) to speed up a few parts of the code. For example, the algorithms for Integer::Mul() or Integer::Div() are simpler and faster if one of the parameters is small enough to take up only one Unit of Data.

Using the Code

class Integer takes up quite a bit of stack space if it is allocated there because operations are much faster. Arithmetic functions are almost all static functions, although overloaded operators would be easy to implement. (I don't use overloaded operators for a big object like class Integer because I don't like hidden temporary variables). The addresses of parameters are checked to handle "in" parameters that are also "out" parameters. This is the declaration of class Integer:

// class Integer v.90
// Copyright Cap'n Code (C) 2004 
// "Use this without giving me credit and I'll sue!"
#pragma once
#include <iostream>

class Integer
{
public:
    typedef unsigned    __int32 Unit;
    static const unsigned MaxSize = 32;

protected:
    // Number of units that store data
    unsigned    UnitLen;

    // If > 0, (SigBit - 1) is the offset of the highest set bit
    // If < 0, (-SigBit - 2) is the offset of the highest set bit,
    // or is -1 for Integer(-1)
    // Otherwise, Integer(0)
    signed    SigBit;

    // Actual data
    Unit Data[MaxSize];

public:
    Integer(void);
    Integer(const Integer &);
    Integer(const Unit *, unsigned Count);
    Integer(const char *, unsigned Radix);
    Integer(const __wchar_t *, unsigned Radix);
    explicit Integer(signed long);

    void Not();    // 1's completement
    void Neg(); // 2's completement
    bool ShiftLeft();
    bool ShiftRight();

    long GetLong() const;
    void Copy(const Unit *, unsigned Count);
    void FromString(const char *, unsigned Radix);
    void FromString(const __wchar_t *, unsigned Radix);
    void MoveTo(Integer &);    // Moves data and clears this
    void ToString(char *, unsigned Radix) const;
    void ToString(__wchar_t *, unsigned Radix) const;

    unsigned GetUnitLength() const;
    unsigned GetSigUnitLen() const;
    Unit GetUnit(unsigned) const;
    bool GetBit(unsigned) const;

    bool IsZero() const;
    bool IsNegative() const;
    bool IsPositive() const;
    bool IsEven() const;

    Integer & operator = (signed long);
    Integer & operator = (const Integer &);

    bool operator == (const Integer &) const;
    bool operator != (const Integer &) const;
    bool operator <  (const Integer &) const;
    bool operator >  (const Integer &) const;
    bool operator <= (const Integer &) const;
    bool operator >= (const Integer &) const;

    static int Compare(const Integer &, const Integer &);
    static void Add(const Integer &, const Integer &, Integer &);
    static void Sub(const Integer &, const Integer &, Integer &);
    static void Mul(const Integer &, const Integer &, Integer &); 
    static void Div(const Integer &, const Integer &, 
                                   Integer & Quo, Integer & Rem);
    static void Mod(const Integer &, const Integer &, Integer &);
    static void Exp(const Integer &, const Integer &, Integer &);
    // Computes A ^ B mod C
    static void ExpMod(const Integer &, const Integer &, 
                                     const Integer &, Integer &);

protected:
    void _Alloc(unsigned);
    void _ReAlloc(unsigned);
    void _DataShiftLeft(unsigned);
    bool _IsMax() const;
    bool _IsMin() const;
    void _FixSigBit();

    friend std::ostream & operator << (std::ostream & Str, 
                                            const Integer & Int);
};

Points of Interest

If you read the source code, the implementation of multiplication is strange and recursive, which is faster than the typical O(n^2) implementation of big multiplication of two integers of size n. In order to speed things up, I used some fancy formulas to replace a big multiplication into a few smaller multiplications, a few additions, and some fast bit shifts. For example, let's multiply 981 and 1234.

where,

981 * 1234 = (10^2*w + x) * (10^2*y+z),
p = w * y = 09 * 12,
q = x * z = 81 * 34,
r = (w * x) * (y + z) = 90 * 46 = 4140,

so that,

981 * 1234 = 10^4*p + 10^2(r - p - q) 
              + q = 10800000 + 127800 + 2754 = 1210554

Instead of separating parameters by decimal place, I separate them by half the number of double words they take up.

(The idea is from Fundamentals of Algorithmetrics, by Gilles Brassard and Paul Bratley.)

History

• v.90:

  First submission, waiting for the slings and arrows from other members so I can improve the class.