Big integer class in C++

Question

I have been trying my hand a bit at creating a big integer class in C++. This is a continuation of a homework assignment.

The class stores a big integer in a double linked list. Each slot contains 8 digits of the number. It is possible to create an instance from an integer or char array. Negative numbers are supported with a bool sign indicator.

I implemented addition, subtraction and multiplication, aswell as their operators. I didn't manage to come up with a good division algorithm though.

The code:

BigInt.h

#include <iostream>
#pragma once

struct slot;

class BigInt
{
    static const int digitsPerSlot = 8;
    static const int valuePerSlot = 100000000;
public:
    BigInt();
    BigInt(const BigInt & that);
    BigInt(int value);
    BigInt(const char string[]);
    ~BigInt();

    bool isPositive;

    BigInt & operator=(const BigInt & that);

    BigInt & operator+=(const BigInt & that);
    BigInt operator+(const BigInt & that) const;

    BigInt & operator-=(const BigInt & that);
    BigInt operator-(const BigInt & that) const;

    BigInt & operator*=(const BigInt & that);
    BigInt operator*(const BigInt & that) const;

    bool operator==(const BigInt & that) const;
    bool operator!=(const BigInt & that) const;

    bool operator<(const BigInt & that) const;
    bool operator<=(const BigInt & that) const;
    bool operator>(const BigInt & that) const;
    bool operator>=(const BigInt & that) const;

    BigInt & operator++();
    BigInt operator++(int);

    explicit operator bool() const;
    bool operator!() const;

    friend std::ostream & operator<<(std::ostream & os, const BigInt & obj);
private:
    void copy(const BigInt & that);
    void constructPointers();

    slot * start;
    slot * end;
    int numberOfSlots;

    void clear();
    void put(int value);
    void push(int value);

    void add(const BigInt & that);
    void subtract(const BigInt & that);

    void removeLeadingZeros();
};

BigInt.cpp

#include "BigInt.h"

struct slot
{
    int value;
    slot * next;
    slot * previous;
};

BigInt::BigInt()
{
    constructPointers();
}

// Shared code among all constructors: make the pointers to the start and end of the list nullpointers and initialise the slotcounter.
void BigInt::constructPointers()
{
    numberOfSlots = 0;
    start = nullptr;
    end = nullptr;
    isPositive = true;
}

// Copyconstructor
BigInt::BigInt(const BigInt & that)
{
    constructPointers();
    copy(that);
}

// Constructor from int, reads the int into the BigInt.
BigInt::BigInt(int value)
{
    constructPointers();
    if (value < 0)
    {
        isPositive = false;
        value *= -1;
    }

    if (value >= valuePerSlot)
    {
        put(value / valuePerSlot);
        value %= valuePerSlot;
    }
    put(value);
}

// Constructor from a char array, reads the array into the BigInt. Assumes only digits to be present in the array.
BigInt::BigInt(const char string[])
{
    constructPointers();

    int lengthOfString = 0;
    while (string[lengthOfString] != '\0')
    {
        lengthOfString++;
    }
    int value = 0;
    int index = 0;
    if (string[0] == '-')
    {
        isPositive = false;
        lengthOfString--;
        index++;
    }
    while (lengthOfString)
    {
        if (!(lengthOfString % digitsPerSlot))
        {
            put(value);
            value = 0;
        }
        value = value * 10 + (string[index] - '0');
        lengthOfString--;
        index++;
    }
    put(value);
}

BigInt::~BigInt()
{
    clear();
}

BigInt & BigInt::operator=(const BigInt & that)
{
    if (this != &that)
    {
        copy(that);
    }
    return *this;
}

void BigInt::copy(const BigInt & that)
{
    clear();
    isPositive = that.isPositive;
    slot * currentSlot = that.start;
    while (currentSlot != nullptr)
    {
        put(currentSlot->value);
        currentSlot = currentSlot->next;
    }
}

// Depending on the signs of LHS and RHS, either addition or subtraction is required.
BigInt & BigInt::operator+=(const BigInt & that)
{
    if (isPositive && that.isPositive) 
    {
        add(that);
    } 
    else if (isPositive && !that.isPositive)
    {
        BigInt placeholder(that);
        placeholder.isPositive = true;
        subtract(placeholder);
    }
    else if (!isPositive && that.isPositive)
    {
        BigInt placeholder(that);
        placeholder.subtract(*this);
        copy(placeholder);
    }
    else
    {
        add(that);
        isPositive = false;
    }

    return *this;
}

// Addition. Adds slots together, remembers any carry (either no carry (0) or a carry (1)) and adds those to the next slots.
// Keeps going until all slots of both BigInts and the carry are empty.
void BigInt::add(const BigInt & that)
{
    BigInt placeholder(*this);
    slot * currentSlotThat = that.end;
    slot * currentSlotThis = placeholder.end;

    clear();
    bool carry = false;
    while (currentSlotThis != nullptr || currentSlotThat != nullptr || carry)
    {
        int thisValue = 0;
        int thatValue = 0;
        if (currentSlotThis != nullptr)
        {
            thisValue = currentSlotThis->value;
            currentSlotThis = currentSlotThis->previous;
        }
        if (currentSlotThat != nullptr)
        {
            thatValue = currentSlotThat->value;
            currentSlotThat = currentSlotThat->previous;
        }
        int sum = thisValue + thatValue + carry;
        carry = sum >= valuePerSlot;
        push(sum % (valuePerSlot));
    }
}

void BigInt::subtract(const BigInt & that)
{
    // Check in advance whether the subtraction will cause the sign of this to flip, by checking if RHS > LHS
    // If that's the case, replace LHS - RHS with (RHS - LHS) * -1
    if (that > *this)
    {
        BigInt placeholder(that);
        placeholder.subtract(*this);
        copy(placeholder);
        isPositive = false;
    } 
    else
    {
        BigInt placeholder(*this);
        slot * currentSlotThat = that.end;
        slot * currentSlotThis = placeholder.end;

        clear();

        bool carry = false;
        while (currentSlotThis != nullptr || currentSlotThat != nullptr)
        {
            int thisValue = 0;
            int thatValue = 0;
            if (currentSlotThis != nullptr)
            {
                thisValue = currentSlotThis->value;
                currentSlotThis = currentSlotThis->previous;
            }
            if (currentSlotThat != nullptr)
            {
                thatValue = currentSlotThat->value;
                currentSlotThat = currentSlotThat->previous;
            }
            int diff = thisValue - carry - thatValue;
            if (diff < 0)
            {
                carry = true;
                diff = -1 * diff;
            }
            else
            {
                carry = false;
            }
            push(diff);
        }
        removeLeadingZeros();
    }
}

// Substraction can lead to leading zero valued slots. These need to be removed asap, since this breaks comparison.
void BigInt::removeLeadingZeros()
{
    slot * currentSlot = start;
    slot * helper;

    while (currentSlot->next != nullptr && currentSlot->value == 0)
    {
        helper = currentSlot;
        currentSlot = currentSlot->next;
        delete helper;
    }
    start = currentSlot;
    currentSlot->previous = nullptr;
}


BigInt BigInt::operator+(const BigInt & that) const
{
    return BigInt(*this) += that;
}

// subtraction operators are defined as LHS - RHS = LHS + (-1 * RHS)
BigInt & BigInt::operator-=(const BigInt & that)
{
    BigInt placeholder(that);
    placeholder.isPositive = !placeholder.isPositive;
    return *this += placeholder;
}

BigInt BigInt::operator-(const BigInt & that) const
{
    return BigInt(*this) -= that;
}

// Cross-multiplication of all slots, with adding the sum of the slotcount worth of zero-slots afterwards. Accumulating all the results.
BigInt & BigInt::operator*=(const BigInt & that)
{
    BigInt placeholder(*this);
    slot * currentSlotThis = placeholder.end;

    BigInt prodPlaceholder;

    clear();

    int thisSlotCounter = 0;
    while (currentSlotThis != nullptr)
    {
        int thatSlotCounter = 0;
        slot * currentSlotThat = that.end;
        while (currentSlotThat != nullptr)
        {
            prodPlaceholder.clear();
            long long prod = (long long)currentSlotThis->value * (long long)currentSlotThat->value;
            if (prod >= valuePerSlot)
            {
                int overflow = (int)(prod / valuePerSlot);
                prodPlaceholder.put(overflow);
                prod %= valuePerSlot;
            }
            prodPlaceholder.put((int)prod);
            for (int numberOfZeroSlots = 0; numberOfZeroSlots < thisSlotCounter + thatSlotCounter; numberOfZeroSlots++)
            {
                prodPlaceholder.put(0);
            }
            *this += prodPlaceholder;
            thatSlotCounter++;
            currentSlotThat = currentSlotThat->previous;
        }
        thisSlotCounter++;
        currentSlotThis = currentSlotThis->previous;
    }
    isPositive = !(placeholder.isPositive ^ that.isPositive);

    return *this;
}

BigInt BigInt::operator*(const BigInt & that) const
{
    return BigInt(*this) *= that;
}

// Equality check, first check for same amount of slots. If that differs, numbers can't be equal. Second checks for signs, then checks if all slots themselves have equal value.
bool BigInt::operator==(const BigInt & that) const
{
    if (this->numberOfSlots != that.numberOfSlots)
    {
        return false;
    }
    if (isPositive != that.isPositive)
    {
        return false;
    }
    slot * currentSlotThis = end;
    slot * currentSlotThat = that.end;

    while (currentSlotThis != nullptr)
    {
        if (currentSlotThis->value != currentSlotThat->value)
        {
            return false;
        }
        currentSlotThat = currentSlotThat->previous;
        currentSlotThis = currentSlotThis->previous;
    }
    return true;
}

bool BigInt::operator!=(const BigInt & that) const
{

    return !(*this == that);
}

// Relational operator. First compares the number of slots, to see if there is already an answer, same for signs. Else it starts at the head of the list to test if the values are equal. 
// When they are not equal anymore, they can be compared for a result.
bool BigInt::operator<(const BigInt & that) const
{
    if (this->numberOfSlots != that.numberOfSlots || this->isPositive != that.isPositive)
    {
        return this->numberOfSlots * (this->isPositive - 0.5) < that.numberOfSlots * (that.isPositive - 0.5);
    }

    slot * currentSlotThis = start;
    slot * currentSlotThat = that.start;
    while (currentSlotThis->next != nullptr && currentSlotThis->value == currentSlotThat->value)
    {
        currentSlotThat = currentSlotThat->next;
        currentSlotThis = currentSlotThis->next;
    }
    return currentSlotThis->value < currentSlotThat->value;
}

bool BigInt::operator<=(const BigInt & that) const
{
    return !(that < *this);
}

bool BigInt::operator>(const BigInt & that) const
{
    return that < *this;
}

bool BigInt::operator>=(const BigInt & that) const
{
    return !(*this < that);
}

BigInt & BigInt::operator++()
{
    return *this += BigInt(1);
}

BigInt BigInt::operator++(int)
{
    BigInt temp(*this);
    operator++();
    return temp;
}

BigInt::operator bool() const
{
    return *this != 0;
}

bool BigInt::operator!() const
{
    return !bool(*this);
}

// Remove and delete all slots from an object.
void BigInt::clear()
{
    slot * currentSlot = start;
    slot * placeholder;
    while (currentSlot != nullptr)
    {
        placeholder = currentSlot;
        currentSlot = placeholder->next;
        delete placeholder;
    }
    start = nullptr;
    end = nullptr;
    numberOfSlots = 0;
}

// Put a slot at the end of the list.
void BigInt::put(int value)
{
    slot * newslot = new slot;
    newslot->value = value;
    newslot->next = nullptr;
    slot * endOfList = end;
    if (numberOfSlots)
    {
        endOfList->next = newslot;
    }
    else
    {
        start = newslot;
    }
    end = newslot;
    newslot->previous = endOfList;
    numberOfSlots++;
}

// Push a slot to the start of the list.
void BigInt::push(int value)
{
    slot * newslot = new slot;
    newslot->value = value;
    newslot->next = start;
    slot * startOfList = start;
    if (numberOfSlots)
    {
        startOfList->previous = newslot;
    }
    else
    {
        end = newslot;
    }
    start = newslot;
    newslot->previous = nullptr;
    numberOfSlots++;
}

std::ostream & operator<<(std::ostream & os, const BigInt & obj)
{
    if (!obj.isPositive)
    {
        os.put('-');
    }

    slot * currentSlot = obj.start;
    while (currentSlot != nullptr)
    {
        int value = currentSlot->value;
        int fullValue = value;
        int numberOfPaddingZeros = 1;
        int digit = 10000000;
        if (currentSlot == obj.start && (fullValue == 0))
        {
            os.put('0');
        }
        else
        {
            while (digit)
            {
                // Pad the value in the slot with leading zeros to fill the entire slot, except when it is the first slot.
                if (currentSlot != obj.start || (fullValue >= digit))
                {
                    os.put((value / digit) + '0');
                }

                value %= digit;
                digit /= 10;
            }
        }
        currentSlot = currentSlot->next;
    }
    return os;
}

Main.cpp

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

BigInt fibonacci(int n)
{
    BigInt a = 1;
    BigInt b = 1;
    BigInt placeholder;
    for (int index = 2; index < n; index++)
    {
        placeholder = a;
        a += b;
        b = placeholder;
    }
    return a;
}

int main()
{
    BigInt a = "123456789";
    BigInt b = "-123456789";
    BigInt c = a + b;
    a *= b;
    std::cout << a << std::endl;
    std::cout << b << std::endl;
    std::cout << c << std::endl;
    b = fibonacci(500);
    std::cout << b;
}

Specific questions

• I am pretty new to C++, so any stylistic or convention based advice is welcome.
• I tried my best to use good library practices, so any pointers there would be appreciated as well.
• I am pretty happy with my addition and multiplication algorithms, but not so sure about my subtraction.

Answer 1

There are a couple of improvements over your current approach that can be performed. I will try to also give you the reasoning behind the recommendations already made by others in the comments:

Datastructure

Prefer standard containers

While it is good for practice to try your hand at implementing fundamental datastructures, in production code it would be preferred to use standard datastructures whenever applicable. So if you need a linked list, use std::list, if you need a resizeable array, use std::vector, if you need a (compile time) fixed size array use std::array, etc.

There are several reasons for this:

• Other programmers know the standard datastructures and can see at a glance what they do.
• The standard datastructures are widely used and better tested than your own implementation will ever be. So when debugging your code you can rely on them to perform as defined in the standard, and you or your colleagues can focus on your remaining code.
• Unless you are very, very good, your implementation will not outperform the standard implementation. If it does, you can probably present it at cppcon or a similar conference.

Choice of Container - When in doubt use std::vector

When you need a container in C++ the default choice is always std::vector. Other containers are only used, if their advantages are needed in the algorithm to be implemented. The only exception is std::array which is slightly more efficient, but only usable if you know the size at compile time.

A linked list has the following advantages:

• you can insert elements at any point with O(1) cost
• iterators and references to elements are not invalidated on insertion, on deletion only iterators pointing at the deleted element are invalidated.

However you pay a significant cost compared to vector:

• You need an additional two pointers per element, increasing memory use significantly
• Since nodes may be allocated separately, the elements may not appear in order in memory. This reduces locality of reference when traversing the list
• Many operations (iteration etc.) are slightly more expensive because they involve more indirection
• Random access takes a number of steps equal to the index

In your case, inserting digits into the middle of the integer will probably not be needed very often, if at all. You are hopefully also never going to expose references or iterators into the integer representation or hold onto them longer than needed. So using a std::vector would be the best choice for your big integer class.

Choice of "digit"

I would recommend using the largest unsigned integer type that still allows efficient arithmetic on your computer, since you already store the sign separately. Implementing multiplication and obtaining carry can be simplified if there is still a larger type available.

In order to improve memory efficiency it makes sense to use the full range provided by the integer type. Your current approach also needs quite expensive modulo and division operations on every step that would be much faster if valuePerSlot were a power of two, because the compiler would replace modulo with a mask and division by a shift.

General style

If you are using C++11 or later, you should define compile time constants as constexpr values.

Bugs

If value == INT_MIN this will overflow, resulting in undefined behaviour, probably it will become 0:

  if (value < 0)
    {
        isPositive = false;
        value *= -1;
    }

Answer 2

Biginteger representation

It is, I believe, the right choice not to make your implementation overly complex, at least in the beginning. So, what would be easy to grasp, yet reasonably powerful? My guess is that you want to retain the possibility to think in decimal base, and to avoid most overflowing problems.

So, given a numeric type T, you want to know the number n of decimal digits it can express, and retain as max value for your block 10^n-1. All of this can be known at compile-time, with the standard "function" std::numeric_limits<T>::digits10 and an easy to write constexpr power function, for instance (C++11 compatible):

template <typename T>
constexpr T power_of_10(T n) {
    return (n == T{1} ? T{10} : T{10}*power_of_10(n-T{1}));
}

So that your maximal block value is:

template <typename T>
constexpr T max_value = power_of_10<T>(std::numeric_limits<T>::digits10)-1;

I also believe it's good practice to leave the concrete type to be decided depending on which machine you compile to, because it could realistically vary. Hence the template.

Of course, as pretty much every comment pointed out, you need to store those blocks in a std::vector, who'll manage memory and access for you. The only thing I should add is that storing your blocks with the less significant to the left makes algorithms a lot simpler to write.

Reasoning in terms of representable decimal-base digits also eases initializing from a string, for instance:

template <typename T>
bigint<T>::bigint(const std::string& str) {
    constexpr T stride = std::numeric_limits<T>::digits10;
    auto b = str.begin();
    auto m = b; std::advance(m, str.size() % stride);
    if (b == m) std::advance(m, stride);
    while (true) {
        value.push_back(std::stoi(std::string(b, m)));
        if (m == str.end()) break;
        b = m; std::advance(m, stride);
    }
    std::reverse(value.begin(), value.end());
}

Algorithms

You won't lose any expressiveness and your algorithm will go faster because the building blocks of your BigInteger are in contiguous memory locations. Here's what the addition would look like, which is almost as clear as your current implementation -and that part of your code is crystal-clear, very nice:

template <typename T>
bigint<T>& bigint<T>::operator+=(const bigint& other) {
    T carry{0};
    if (value.size() < other.value.size()) value.resize(other.value.size(), T{0});
    for (int i = 0; i < value.size(); ++i) {
        value[i] += carry;
        if (i < other.value.size()) value[i] += other.value[i];
        if (value[i] > max_value<T>) {
            carry = T{1};
            value[i] -= max_value<T>+1;
        }
        else carry = T{0};
    }
    if (carry) value.push_back(T{1});
    return *this;
}

Multiplication is another beast. I haven't looked precisely at your algorithm, but I believe that you can do a lot better. There is this "russian peasant" algorithm that particularly suits computer arithmetics because it relies on simple addition (that we already implemented) and division by 2, which is a one-bit shift. There is a good discussion on this algorithm, and the best way to implement it in the book "From mathematics to generic programming" (not sure if I remember the title correctly. Alexander Stepanov wrote it, of this I'm certain). Here's a very basic implementation:

// russian peasant algorithm
template <typename T>
bigint<T>& bigint<T>::operator*=(bigint other) {
    bigint<T> init{"0"s};
    std::swap(*this, init);
    while (true) {
        if (other.value[0]%2==1) { // alternatively other.value[0]&1 but I'm sure the compiler does best on its own
            *this += init;
            if (other.value.size() == 1 && other.value[0] == 1) return *this;
        }
        init = init+init;
        other.div_by_2();
    }
}

div_by_2 is easy enough to write, and even if I haven't given a lot of thought to its optimization, you'll notice that there aren't any time-consuming operations, only additions and shifts:

template <typename T>
bigint<T>& bigint<T>::div_by_2() {
    auto carry = 0;
    constexpr T carry_value = (max_value<T>+1)/2; // <=> >> 1
    std::for_each(value.rbegin(), value.rend(), [&carry](auto&& t) { // reverse iterator
        auto next_carry = t&1;
        t >>= 1;
        if (carry) t += carry_value;
        carry = next_carry;
    });
    if (!value.back()) value.pop_back();
    return *this;
}