6
\$\begingroup\$

I am working on a LargeInteger class to store Integers beyond the size of long long as a dynamic character array. I have overloaded most of the relevant operators to be used with the large integers.

I would like to find a way to further streamline the addition/subtraction. I think it ought to be possible to only use a single loop and manipulate the signs and order to produce the proper result, but all attempts thus far have failed.

The only things I am unwilling to change:

  • Storing the data as a dynamic char array
  • The attributes of the operators (friend, overloaded, return type, parameters)

This does not use proper C++ components such as std::vector, std::copy and others. My goals in this project were to avoid the use of the standard (or other) library aside from I/O.

Everything else is fair game, and I welcome any and all criticisms. This is one of the first C++ classes I have made, so I expect that my coding is sub-par.

LargeInt.h

#ifndef LARGEINT_H
#define LARGEINT_H

#include <iostream>

typedef unsigned int Counter;
typedef char Digit;
typedef unsigned int Index;
typedef bool Sign;

const bool kSignPositive = 0;
const bool kSignNegative = 1;
const bool kCarryTrue = 1;
const bool kCarryFalse = 0;
const bool kBorrowTrue = 1;
const bool kBorrowFalse = 0;

const Counter kDefaultCounterValue = 0;

const Digit kDefaultDigitValue = 0;
const Digit kMinDigitValue = 0;
const Digit kMaxDigitValue = 9;
const Digit kRadix = 10;

const Index kFirstIndex = 0;

const size_t kByteSize = 8;
const size_t kMinLength = 1;

namespace helper_templates
{
    // Count Digits
    template <typename T>
    Counter TCountDigits(T x);

    // Get Sign
    template <typename T>
    bool TGetSign(T x);
}

class LargeInt
{
    private:
        Sign sign_;
        size_t length_;
        Digit* data_;

    public:
        /*
         * Constructors
         */

        // Default
        LargeInt();

        // Copy
        LargeInt(const LargeInt& x);

        // Copy and Resize
        LargeInt(const Sign sign, const size_t length, const Digit* data);

        // Integer Type
        LargeInt(const long long x);

        /*
         * Destructor
         */

        ~LargeInt();

        /*
         * Operators
         */

        // Assignemnt
        LargeInt& operator=(const LargeInt& x);

        // Negation
        LargeInt operator-();

        // Addition
        friend LargeInt operator+(LargeInt x, const LargeInt& y);

        // Addition Assignment
        LargeInt& operator+=(const LargeInt& x);

        // Subtraction
        friend LargeInt operator-(LargeInt x, const LargeInt& y);

        // Subtraction Assignment
        LargeInt& operator-=(const LargeInt& x);

        // Preincrement
        LargeInt& operator++();

        // Postincrement
        LargeInt operator++(int);

        // Predecrement
        LargeInt& operator--();

        // Postdecrement
        LargeInt operator--(int);

        // Not
        bool operator!();

        // Equality
        friend bool operator==(const LargeInt& x, const LargeInt& y);

        // Inequality
        friend bool operator!=(const LargeInt& x, const LargeInt& y);

        // Greater Than
        friend bool operator>(const LargeInt& x, const LargeInt& y);

        // Greater Than or Equal To
        friend bool operator>=(const LargeInt& x, const LargeInt& y);

        // Less Than
        friend bool operator<(const LargeInt& x, const LargeInt& y);

        // Less Than or Equal To
        friend bool operator <=(const LargeInt& x, const LargeInt& y);

        // Insertion
        friend std::ostream& operator<<(std::ostream& out,
            const LargeInt& x);

        /*
         * Functions
         */

        // Absolute Value
        LargeInt Abs() const;
};

#endif

LargeInt.C

#include "LargeInt.h"

// Count Digits
template <typename T>
Counter helper_templates::TCountDigits(T x)
{
    Counter c = kDefaultCounterValue;
    while(x)
    {
        x /= kRadix;
        c++;
    }
    return c;
}

// Get Sign
template <typename T>
Sign helper_templates::TGetSign(T x)
{
    long long mask = 0;
    mask |= 1 << ((sizeof(x) * kByteSize) - 1);
    return (mask & x) >> ((sizeof(x) * kByteSize) - 1);
}

/*
 * Constructors
 */

 // Default
LargeInt::LargeInt()
    : sign_(kSignPositive), length_(kMinLength), data_(new Digit[kMinLength])
{
     data_[kFirstIndex] = kDefaultDigitValue;
}

// Copy
LargeInt::LargeInt(const LargeInt& x)
    : sign_(x.sign_), length_(x.length_), data_(new Digit[x.length_])
{
    for(Index i = kFirstIndex; i < length_; i++)
    {
        data_[i] = x.data_[i];
    }
}

// Copy and Resize
LargeInt::LargeInt(const Sign sign, const size_t length, const Digit* data)
    : sign_(sign), length_(length), data_(new Digit[length_])
{
    for(Index i = kFirstIndex; i < length_; i++)
    {
        data_[i] = data[i];
    }
}

// Integer Type
LargeInt::LargeInt(long long x)
    : sign_(helper_templates::TGetSign(x)),
        length_(helper_templates::TCountDigits(x)),
        data_(new Digit[length_])
{
    if(sign_ == kSignNegative)
    {
        x = -x;
    }
    for(Index i = kFirstIndex; i < length_; i++)
    {
        Digit d = x % kRadix;
        data_[i] = d;
        x /= kRadix;
    }
}

/*
 * Destructor
 */

LargeInt::~LargeInt()
{
    delete [] data_;
}

/*
 * Operators
 */

// Assignment
LargeInt& LargeInt::operator=(const LargeInt& x)
{
    if(this != &x)
    {
        this->sign_ = x.sign_;
        this->length_ = x.length_;
        for(Index i = kFirstIndex; i < this->length_; i++)
        {
            this->data_[i] = x.data_[i];
        }
    }
    return *this;
}

// Negation
LargeInt LargeInt::operator-()
{
    return LargeInt(!this->sign_, this->length_, this->data_);
}

// Addition
LargeInt operator+(LargeInt x, const LargeInt& y)
{
    return x += y;
}

// Addition Assignment
LargeInt& LargeInt::operator+=(const LargeInt& x)
{
    LargeInt sum;
    Digit d;
    Digit carry = kCarryFalse;
    Index i;
    if(this->sign_ == kSignPositive && x.sign_ == kSignPositive)
    {
        if(*this >= x)
        {
            sum.length_ = this->length_ + kMinLength;
            for(i = kFirstIndex; i < x.length_; i++)
            {
                d = this->data_[i] + x.data_[i] + carry;
                if(d > kMaxDigitValue)
                {
                    d %= kRadix;
                    carry = kCarryTrue;
                }
                else
                {
                    carry = kCarryFalse;
                }
                sum.data_[i] = d;
            }
            while(i < this->length_)
            {
                d = this->data_[i] + carry;
                if(d > kMaxDigitValue)
                {
                    d %= kRadix;
                    carry = kCarryTrue;
                }
                else
                {
                    carry = kCarryFalse;
                }
                sum.data_[i] = d;
                i++;
            }
            if(!carry)
            {
                *this = LargeInt(sum.sign_, sum.length_ - kMinLength,
                    sum.data_);
            }
            else
            {
                *this = sum;
            }
        }
        else
        {
            *this = x + *this;
        }
    }
    else if(this->sign_ == kSignPositive)
    {
        *this = *this - x;
    }
    else if(x.sign_ == kSignPositive)
    {
        *this = x - *this;
    }
    else
    {
        *this = -(x.Abs() + this->Abs());
    }
    return *this;
}

// Subtraction
LargeInt operator-(LargeInt x, const LargeInt& y)
{
    return x -= y;
}

// Subtraction Assignment
LargeInt& LargeInt::operator-=(const LargeInt& x)
{
    LargeInt difference;
    Digit d;
    Digit borrow = kBorrowFalse;
    Index i;
    if(x.sign_ == kSignNegative)
    {
        *this = *this + x.Abs();
    }
    else if(this->sign_ == kSignNegative)
    {
        *this = -(this->Abs() + x);
    }
    else
    {
        if(*this > x)
        {
            difference.length_ = this->length_;
            for(i = kFirstIndex; i < x.length_; i++)
            {
                d = this->data_[i] - x.data_[i] - borrow;
                if(d < kDefaultDigitValue)
                {
                    d += kRadix;
                    borrow = kBorrowTrue;
                }
                else
                {
                    borrow = kBorrowFalse;
                }
                difference.data_[i] = d;
            }
            while(i < this->length_)
            {
                d = this->data_[i] - borrow;
                if(d < kDefaultDigitValue)
                {
                    d += kRadix;
                    borrow = kBorrowTrue;
                }
                else
                {
                    borrow = kBorrowFalse;
                }
                difference.data_[i] = d;
                i++;
            }
            for(i = difference.length_; i > kFirstIndex; i--)
            {
                if(difference.data_[i - 1] == kDefaultDigitValue)
                {
                    difference.length_--;
                }
                else
                {
                    break;
                }
            }
            *this = LargeInt(kSignPositive, difference.length_,
                difference.data_);
        }
        else if(x > *this)
        {
            *this = -(x - *this);
        }
        else
        {
            *this = LargeInt();
        }
    }
    return *this;
}

// Preincrement
LargeInt& LargeInt::operator++()
{
    *this += 1;
    return *this;
}

// Postincrement
LargeInt LargeInt::operator++(int)
{
    LargeInt temp(*this);
    ++*this;
    return temp;
}

// Predecrement
LargeInt& LargeInt::operator--()
{
    *this -= 1;
    return *this;
}

// Postdecrement
LargeInt LargeInt::operator--(int)
{
    LargeInt temp(*this);
    --*this;
    return temp;
}

// Not
bool LargeInt::operator!()
{
    bool isNot;
    if(*this == LargeInt())
    {
        isNot = true;
    }
    else
    {
        isNot = false;
    }
    return isNot;
}

// Equality
bool operator==(const LargeInt& x, const LargeInt& y)
{
    bool isEqual;
    if(x.sign_ != y.sign_)
    {
        isEqual = false;
    }
    else if(x.length_ != y.length_)
    {
        isEqual = false;
    }
    else
    {
        for(Index i = kFirstIndex; i < x.length_; i++)
        {
            if(x.data_[i] != y.data_[i])
            {
                isEqual = false;
                break;
            }
            isEqual = true;
        }
    }
    return isEqual;
}

// Inequality
bool operator!=(const LargeInt& x, const LargeInt& y)
{
    return !(x == y);
}

// Greater Than
bool operator>(const LargeInt& x, const LargeInt& y)
{
    bool isGreater;
    if(x.sign_ == kSignPositive && y.sign_ == kSignPositive)
    {
        if(x.length_ == y.length_)
        {
            for(Index i = x.length_; i > kFirstIndex; i--)
            {
                if(x.data_[i - i] > y.data_[i - 1])
                {
                    isGreater = true;
                    break;
                }
                else
                {
                    isGreater = false;
                }
            }
        }
        else if(x.length_ > y.length_)
        {
            isGreater = true;
        }
        else
        {
            isGreater = false;
        }
    }
    else if(x.sign_ == kSignPositive)
    {
        isGreater = true;
    }
    else if(y.sign_ == kSignPositive)
    {
        isGreater = false;
    }
    else
    {
        isGreater = y.Abs() > x.Abs();
    }
    return isGreater;
}

// Greater Than or Equal To
bool operator>=(const LargeInt& x, const LargeInt& y)
{
    return (x > y) || (x == y);
}

// Less Than
bool operator<(const LargeInt& x, const LargeInt& y)
{
    return y > x;
}

// Less Than or Equal To
bool operator <=(const LargeInt& x, const LargeInt& y)
{
    return (x < y) || (x == y);
}

// Insertion
std::ostream& operator<<(std::ostream& out, const LargeInt& x)
{
    if(x.sign_ == kSignNegative)
    {
        out << '-';
    }
    for(Index i = x.length_; i > kFirstIndex; i--)
    {
        out << +x.data_[i - 1];
    }
    return out;
}

/*
 * Functions
 */

// Absolute Value
LargeInt LargeInt::Abs() const
{
    return LargeInt(kSignPositive, this->length_, this->data_);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Why is kRadix == 10 and not 256 (or 128 if you want to add digits without overflow)? You are wasting a lot of memory. \$\endgroup\$ – AShelly Mar 7 '16 at 22:46
  • 2
    \$\begingroup\$ You can certainly go more than 99. You are using an arbitrary radix, there is no reason that radix needs to be a power of 10 - a power of 2 will make much better use of the CPU's built-in capabilities. This sample needs 20 bytes to store a 64 bit int, compared to 8 bytes if your radix is 256. That may be fine for a toy example, but that 2.5x overhead will seriously affect performance if you try to do anything useful with this class. \$\endgroup\$ – AShelly Mar 8 '16 at 0:29
  • 1
    \$\begingroup\$ @AShelly: I agree. In addition, multiplying the storage by some factor K also means you'll generally multiply the time required by roughly the same factor. \$\endgroup\$ – Jerry Coffin Mar 8 '16 at 0:30
  • 2
    \$\begingroup\$ I admit that this may be premature optimization, but a large integer library generally needs to be highly performant in order to be useful. \$\endgroup\$ – AShelly Mar 8 '16 at 0:31
  • 1
    \$\begingroup\$ Storing the data as a dynamic char array.: Well there is your first problem. This breaks the principle of separation of concerns. Your class should be responsible for resource management or business logic not both. \$\endgroup\$ – Martin York Mar 8 '16 at 3:50
2
\$\begingroup\$

The only things I am unwilling to change:

  • Storing the data as a dynamic char array.
  • The attributes of the operators (friend, overloaded, return type, parameters).

Well there is not much point doing more of a review. As both of these things are done incorrectly to start with. There are some major problems here to start with.

Storing

Separation of concerns is basically about a class only doing one thing. It either does resource allocation or business logic. Your class is doing both and as a result doing it badly.

Also there is already a specific class that does exactly this std::vector<char>. This class is highly efficient highly tested and is going to beat your memory management every time (unless you are experimenting you should be using it).

You miss move semantics. Which makes your code less efficient than it could be.

You also don't have the concept of capacity so you can't preallocate and must reallocate the correct size all the time which means sizing all the time which is very inefficient.

Friendship.

Your use of friendship is inconsistent. As a result it behaves differently than you would expect from (if you expect it to work like built in types).

int x = 5;
int y = 6;
int z = 3;

y = x += z; // This should work.

// Now with your type.

int      x = 5;
LargeInt y = 6;
LargeInt z = 3;

y = x += z; // Not sure why this would not work.

Assignment operator is broken

LargeInt& LargeInt::operator=(const LargeInt& x)
{
    if(this != &x)
    {
        this->sign_ = x.sign_;

        // This is wrong.
        // This is the size of the allocated area of memory.
        // If you don't keep this accurate you are going to 
        // overwrite the end of the array if you are not careful
        // You are mixing the concept of size and capacity into a
        // single variable.
        this->length_ = x.length_;


        for(Index i = kFirstIndex; i < this->length_; i++)
        {
            this->data_[i] = x.data_[i];
        }
    }
    return *this;
}

Algorithms.

You spend way to much time re-writing the same loop.

        for(Index i = kFirstIndex; i < this->length_; i++)
        {
            this->data_[i] = x.data_[i];
        }

Much easier to use algorithms to all this kind of work.

        std::copy(x.data + kFirstIndex, x.data + length, data);

DRY

Is the += operator not basically the same as the -= operator? I am sure you can reuse about 90% of that code.

Operator !

If you have this pattern

if (x)
      return true;
else  return false;

This can be replaced with:

return x;

The test itself is very ineffecient:

if (*this == LargeInt())

Here you are creating a LargeInt() object each time you do the test. Which means memory allocation and de-allocation every time. It may be worth creating a static function object so that it is only created once.

Minus 0

Also is -0 not the same as +0 (in terms of testability). I don't think your test actually gets that correct.

LargeInt   x;        // +0
LargeInt   y = -x;   // -0

if (x == y)
{
    // I would expect this to be true.
    // If you expect this to be different then I would document
    // that fact somewhere.
}

Enum

The following could all be enum values.

const bool kSignPositive = 0;
const bool kSignNegative = 1;
const bool kCarryTrue = 1;
const bool kCarryFalse = 0;
const bool kBorrowTrue = 1;
const bool kBorrowFalse = 0;

Radix

Using a radix of 10 is very eneffecient.

const Digit kDefaultDigitValue = 0;
const Digit kMinDigitValue = 0;
const Digit kMaxDigitValue = 9;
const Digit kRadix = 10;

This not only causes extra storage but also extra operations when moving through each digit.

\$\endgroup\$
  • \$\begingroup\$ I was trying to avoid the use of std::vector, copy, etc. for this project. Yes, I realize that this is poor practice and would never be done in a non-exercise class. As for the operators, I though the correct method was to implement += and -= first, and then make + and - friend operators that used += and -=. I recognize that even if this is true, I may have done it incorrectly, and I'd appreciate corrections if needed. I will look at fixing the assignment operator. I originally tried deleting then making a new array, but this was causing double delete errors. \$\endgroup\$ – Michael Brandon Morris Mar 9 '16 at 21:46
  • 2
    \$\begingroup\$ Sure you don't have to use std::vector<> but you DO need to split the memory management into its own class. So you need two classes. One the concentrates just on memory management and one that does the maths. \$\endgroup\$ – Martin York Mar 9 '16 at 21:48
  • 1
    \$\begingroup\$ Makeing + work in terms of += is correct. BUT You can also make += a friend. \$\endgroup\$ – Martin York Mar 9 '16 at 21:49
  • \$\begingroup\$ I know the addition and subtraction ought to be able to be streamlined, but I commented in the OP that I could not get them to work and I was looking for more concrete suggestions as to how they could be fixed. I'll fix the ! operator. I'll fix the +/-0 issue. I'll work on replacing all the constants with an enum. The radix issue has already been pointed out, and I am unsure how exactly to change that to something other than a base 10 number, as I don't know how to convert a base 2/16/256 number that is too large for a primitive to a base 10 value to print. \$\endgroup\$ – Michael Brandon Morris Mar 9 '16 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.