2
\$\begingroup\$

My second little project. I would like to hear all the critics possible. This is a C++ Long Int library. It is self-education project, however I would like to make it better.

For me possible things to change are:

  1. Fix enormous re-copying, where it shouldn't be.
  2. Add move-semantics where possible.
  3. * Create an internal copy function, which works kinda like vector copy (begin, which_object_from). This will be used in multiplication/division, again, to lower amount of useless re-copying and re-sizing.
  4. Make a SCIENTIFIC Karatsuba so it useful (Base must be 2 instead of 10 to use bitwise >> instead of multiplication by base x)
  5. Add sqrt function
  6. Fix overflowing in possible loops variables (int's to auto's or everything to Long Long)

IMPORTANT Project works with standard OLDER then C++17 at the header line of inline "nested" struct.
For older standards we can create constexpr pow function to calculate MODULO (and set other in the CPP), however inner struct looks fancier to me.

BigInt.h

#pragma once
#include <cstddef>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;

struct Big_Int
{
    size_t SIZE;
    unsigned long long* number;
    bool negative = false;

    Big_Int(size_t, unsigned long long); 
    Big_Int(string);
    Big_Int(unsigned long long);
    ~Big_Int();
    Big_Int(const Big_Int&);

    Big_Int operator=(const Big_Int&);
    bool operator<(const Big_Int&) const;
    bool operator==(const Big_Int&) const;
    bool operator<=(const Big_Int&) const;
    friend ostream& operator<<(ostream& os, const Big_Int&);

    Big_Int operator+(const Big_Int&) const;
    Big_Int operator-(const Big_Int&) const;
    Big_Int operator*(const Big_Int&); // smart multiplication - chooses between Karatsuba & naive on itself;
    static Big_Int naive_multiplication(const Big_Int&,const Big_Int&);
    static Big_Int Karatsuba_multiplication(Big_Int, Big_Int);
    static const Big_Int _pow(const Big_Int&, const Big_Int&);
    Big_Int operator/(const Big_Int&);

    //Helper functions; unintended for manual usage
    void _squeeze();
    static void _to_equal_size(Big_Int&, Big_Int&);
    void _increaseByModulo();
    
    struct nested
    {
        size_t BASE = 10;
        size_t BASE_POWER = 3; // can't be more than 9
        size_t MODULO = pow(BASE,BASE_POWER);
        int Karatsuba_Power = 256;
    };
    inline static const nested insides; // C++17 or OLDER;
};

BigInt.cpp

#include "BigInt.h"

const Big_Int MIN_FOR_KARATSUBA = Big_Int::_pow(10, Big_Int::insides.Karatsuba_Power);

Big_Int::Big_Int(size_t SIZE, unsigned long long fill_with)
{
    this->SIZE = SIZE;
    number = new unsigned long long[this->SIZE];
    for (int i = 0; i < this->SIZE; ++i)
        number[i] = fill_with;
}

Big_Int::Big_Int(string str)
{
    if (str[0] == '-')
    {
        negative = true;
        str.erase(0, 1);
    };
    if (str.size()< insides.BASE_POWER)
    {
        SIZE = 1;
        number = new unsigned long long[SIZE];
        number[0] = stoi(str);
    }
    else
    {
            size_t position = str.size();
            SIZE = str.size() / insides.BASE_POWER;
            if(str.size() % insides.BASE_POWER != 0) SIZE++;
            number = new unsigned long long[SIZE];
            string substring;
            for (int g = 0; g < SIZE-1; ++g)
            {
                position -= insides.BASE_POWER;
                substring = str.substr(position, insides.BASE_POWER);
                number[g] = stoi(substring);
            }
            substring = str.substr(0, position);
            number[SIZE - 1] = stoi(substring);
    }
}
Big_Int::Big_Int(unsigned long long other)
{
    SIZE = 1;
    if (other == 0)
    {
        number = new unsigned long long[SIZE];
        number[0] = 0;
    }
    else
    {
        int digits = log10(other) + 1;
        while (digits > insides.BASE_POWER)
        {
            digits -= insides.BASE_POWER;
            SIZE++;
        }
        number = new unsigned long long[SIZE];
        int i = 0;
        for (i; i < SIZE - 1; ++i)
        {
            number[i] = other % int(pow(insides.MODULO, (i + 1))); //cmath pow returns double ; explicit int cast required
            other /= int(pow(insides.MODULO, (i + 1)));
        }
        number[i] = other;
    };
};

Big_Int::~Big_Int()
{
    delete[] number;
}

Big_Int::Big_Int(const Big_Int& other)
{
    this->SIZE = other.SIZE;
    this->negative = other.negative;
    this->number = new unsigned long long[SIZE];
    for (auto i = 0; i < this->SIZE; i++)
    {
        this->number[i] = other.number[i];
    };
}

Big_Int Big_Int::operator=(const Big_Int& other)
{
    delete[] this->number;

    this->SIZE = other.SIZE;
    this->negative = other.negative;
    this->number = new unsigned long long[SIZE];
    for (auto i = 0; i < this->SIZE; i++)
    {
        this->number[i] = other.number[i];
    };

    return *this;
}

Big_Int Big_Int::operator+(const Big_Int& other) const
{
    if (this->negative && !(other.negative))
    {
        Big_Int tmp = *this;
        tmp.negative = false;
        Big_Int result = other - tmp;
        result._squeeze();
        return result;
    }
    else if (!(this->negative) && other.negative)
    {
        Big_Int tmp = other;
        tmp.negative = false;
        Big_Int result = *this - tmp;
        result._squeeze();
        return result;
    }

    Big_Int result(max(this->SIZE, other.SIZE) + 1, 0);
    if (this -> negative && other.negative) result.negative=true;

    int carry = 0;

    int i = 0;

    for (i; i < min(this->SIZE, other.SIZE); ++i)
    {
        int tmp = this->number[i] + other.number[i] + carry;
        carry = tmp / insides.MODULO;
        tmp %= insides.MODULO;
        result.number[i] = tmp;
    }
    if (this->SIZE == other.SIZE) result.number[i] = carry;
    else if (i == this->SIZE) for (i; i < other.SIZE;++i)
    {
        result.number[i] = other.number[i] + carry;
        carry = 0;
    }
    else for (i; i < this->SIZE;++i)
    {
        result.number[i] = this->number[i] + carry;
        carry = 0;
    }
    result._squeeze();
    return result;
}

Big_Int Big_Int::operator-(const Big_Int& other) const
{
    if ((* this) == other) return 0;
    if (other.negative)
    {
        Big_Int tmp = other;
        tmp.negative = false;
        Big_Int result = *this + tmp;
        result._squeeze();
        return result;
    }
    if (this->negative)
    {
        Big_Int tmp = *this;
        tmp.negative = false;
        tmp = tmp + other;
        tmp.negative = true;
        tmp._squeeze();
        return tmp;
    }
    if ((* this) < other)
    {
        Big_Int tmp = other - (*this);
        tmp.negative = true;
        tmp._squeeze();
        return tmp;
    }
    Big_Int result((this->SIZE) +1, 0);

    int carry = 0;

    int i = 0;

    for (i; i < other.SIZE; ++i)
    {
        size_t tmp = this->number[i] - other.number[i] - carry + insides.MODULO;
        if (tmp >= insides.MODULO)
        {
            tmp -= insides.MODULO;
            carry = 0;
        }
        else
        {
            carry = 1;
        }
        result.number[i] = tmp;
    }
    if (i < this->SIZE)
    {
        for (i; i < this->SIZE; ++i)
        {
            result.number[i] = this->number[i] - carry;
            carry = 0;
        }
    }
    result._squeeze();
    return result;


}

Big_Int Big_Int::operator*(const Big_Int& other)
{

    if (((*this) < MIN_FOR_KARATSUBA) || (other < MIN_FOR_KARATSUBA))
    {
        return naive_multiplication(*this, other);
    }
    else 
        return Karatsuba_multiplication(*this, other);

}
Big_Int Big_Int::naive_multiplication(const Big_Int& first,const Big_Int& other)
{
    if (first == 0 || other == 0)
        return 0;
    Big_Int result(first.SIZE + other.SIZE, 0);
    if (first.negative ^ other.negative) result.negative = true;
    {
        for (int i = 0; i < other.SIZE; ++i)
        {
            int carry = 0;
            for (int j = 0; j < first.SIZE; ++j)
            {
                result.number[i + j] += carry + first.number[j] * other.number[i];
                carry = result.number[i + j] / insides.MODULO;
                result.number[i + j] %= insides.MODULO;
            }
            result.number[i + first.SIZE] += carry;
        }
        result._squeeze();
        return result;
    }
}
Big_Int Big_Int::Karatsuba_multiplication(Big_Int first, Big_Int second)
{
    Big_Int result(first.SIZE + second.SIZE, 0);
    if (first.negative ^ second.negative) result.negative = true;
    _to_equal_size(first, second);
    int k = first.SIZE / 2;
    Big_Int x = _pow(10, insides.BASE_POWER*k);
    Big_Int x2 = _pow(x,2);

    Big_Int b(k, 0);
    for (int i = 0; i < k; ++i)
        b.number[i] = first.number[i];

    Big_Int a(first.SIZE - k, 0);
    for (int i = 0; i < a.SIZE; ++i)
        a.number[i] = first.number[i + k];

    Big_Int d(k, 0);
    for (int i = 0; i < k; ++i)
        d.number[i] = second.number[i];

    Big_Int c(second.SIZE - k, 0);
    for (int i = 0; i < c.SIZE; ++i)
        c.number[i] = second.number[i + k];

    Big_Int a_plus_b = a + b;
    Big_Int c_plus_d = c + d;
    Big_Int a_c = a * c;
    Big_Int b_d = b * d;
    Big_Int middle = a_plus_b * c_plus_d - a_c - b_d;
    result = (naive_multiplication(a_c, x2)) + naive_multiplication(middle, x) + b_d;
    result._squeeze();
    return result;
}
const Big_Int Big_Int::_pow(const Big_Int& base, const Big_Int& exponent)
{
    return exponent == 0 ? 1 : naive_multiplication(base,_pow(base, exponent - 1));
}
Big_Int Big_Int::operator/(const Big_Int& other)
{
    if (other == 0) return 0; // error
    if (*this == other) return 1;
    if (other == 1) return *this;
    Big_Int result(this->SIZE, 0); 
    if (this->negative && other.negative)
    {
        Big_Int tmp1 = *this;
        Big_Int tmp2 = other;
        tmp1.negative = false;
        tmp2.negative = false;
        result = tmp1 / tmp2;
        result._squeeze();
        return result;
    }
    if (this->negative) 
    {
        Big_Int tmp = *this;
        tmp.negative = false;
        result = (tmp / other);
        result.negative = true;
        result._squeeze();
        return result;
    }
    if (other.negative)
    {
        Big_Int tmp = other;
        tmp.negative = false;
        result = (*this / tmp);
        result.negative = true;
        result._squeeze();
        return result;
    }
    if (this->negative && other.negative) if (other < *this) return 0;
    else if (*this < other) return 0;

    Big_Int current("0");

    for (auto i = this->SIZE -1; i != -1; --i)
    {
        current.number[0] = this->number[i];
        unsigned long long x = 0, l = 0, r = insides.MODULO;
        while (l <= r)
        {
            auto m = (l + r) / 2;
            Big_Int minus = Big_Int(m) * other;
            if (minus <= current)
            {
                x = m;
                l = m + 1;
            }
            else
                r = m - 1;
        }
        result.number[i] = x;
        current = current - (Big_Int(x)*other);
        current._increaseByModulo();
    }
    result._squeeze();
    return result;

}

void Big_Int::_squeeze()
{
    if ((*this) == Big_Int("0")) return;
    int counter = 0;
    for (int i = this->SIZE - 1; i != -1; --i)
    {
        if (this->number[i] == 0) counter++;
        else break;
    }
    if (counter == 0) return;
    if (counter == SIZE)
    {
        *this = Big_Int("0");
        return;
    };
    unsigned long long* tmp = new unsigned long long[this->SIZE - counter];
    for (int i = 0; i < this->SIZE - counter; ++i) tmp[i] = number[i];
    delete[] this->number;
    SIZE -= counter;
    this->number = new unsigned long long[SIZE];
    for (int i = 0; i < this->SIZE; ++i) number[i] = tmp[i];
    delete[] tmp;
}

void Big_Int::_to_equal_size(Big_Int& first, Big_Int& other)
{
    if (first.SIZE == other.SIZE) return;
    Big_Int tmp(max(first.SIZE, other.SIZE), 0);
    if (first.SIZE < other.SIZE) for (int i = 0; i < first.SIZE; ++i)
    {
        tmp.number[i] = first.number[i];
        first = tmp;
    }
    else for (int i = 0; i < other.SIZE; ++i)
    {
        tmp.number[i] = other.number[i];
        other = tmp;
    }
}

void Big_Int::_increaseByModulo()
{

    unsigned long long* tmp = new unsigned long long[this->SIZE + 1];
    for (int i = this->SIZE - 1; i != -1; --i)
        tmp[i + 1] = this->number[i];
    delete[] this->number;
    tmp[0] = 0;
    this->number = new unsigned long long[++SIZE];
    for (int i = 0; i <this->SIZE; ++i)
        this->number[i] = tmp[i];
    delete[] tmp;
}


bool Big_Int::operator<(const Big_Int& other) const
{
    if (this->negative && other.negative)
    {
        if (this->SIZE < other.SIZE) return false;
        else if (other.SIZE < this->SIZE) return true;
        else
        {
            for (int i = SIZE - 1; i != -1; --i)
            {
                if (this->number[i] < other.number[i]) return false;
                else if (other.number[i] < this->number[i]) return true;
            }
            return false;
        }
    }
    else if (!(other.negative) && this->negative) return true;
    else if (other.negative && !(this->negative)) return false;
    else
    {
        if (this->SIZE < other.SIZE) return true;
        else if (other.SIZE < this->SIZE) return false;
        else 
        {
            for (int i = SIZE - 1; i != -1; --i)
            {
                if (this->number[i] < other.number[i]) return true;
                else if (other.number[i] < this->number[i]) return false;
            }
            return false;
        }
    }
}

bool Big_Int::operator==(const Big_Int& other) const
{
    if (this->SIZE == other.SIZE && this->negative == other.negative)
    {
        for (int i = 0; i < SIZE; ++i)
        {
            if (this->number[i] != other.number[i]) return false;
        }
        return true;
    }
    else return false;

}

bool Big_Int::operator<=(const Big_Int& other) const
{
    return ((*this) < (other) || (*this) == (other));
}

ostream& operator<<(ostream& os, const Big_Int& obj)
{
    if (obj == 0) return os << "0";
    string result;
    if (obj.negative) result.push_back('-');
    for (size_t i = obj.SIZE - 1; i != -1; --i)
    {
        if (obj.number[i] == 0)
        {
            string tmp = "0";
            tmp.insert(0, Big_Int::insides.BASE_POWER-1, '0');
            result += tmp;
        }
        else if (i == obj.SIZE - 1)
        {
            string tmp = to_string(obj.number[i]);
            result += tmp;
        }
        else 
        {
            string tmp = to_string(obj.number[i]);
            if (tmp.size() < Big_Int::insides.BASE_POWER)
            {
                string nulls = "0";
                nulls.insert(0, Big_Int::insides.BASE_POWER - tmp.size() - 1, '0');
                tmp = nulls + tmp;
            }
                

            result += tmp;
        }
    }
    return os << result;

}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Interface review

Please don't do this, especially in headers:

 using namespace std;

That brings all of std namespace into global scope, in every program that includes the header. That can lead to all sorts of surprises. It's much better to qualify each name where it's used (and makes your code much clearer about which library types and functions are used).


The header file has library includes which aren't needed just to define Big_Int (e.g. <cmath> and <algorithm> are used in only in the implementation file, so can be moved there). Prefer to include <iosfwd> rather than <iostream> as a more lightweight definition of std::ostream.


Think about which parts of the interface should be public and which not. For example, outside code should not be able to change the invariants managed by SIZE and number (and why is the former written in all-caps? We normally only write macro names that way). Similarly, do we actually want to expose naive_multiplication() and Karatsuba_multiplication() multiplication to users, or are they better served with the simple operator*() interface?


A good design rule in C++ is that classes shouldn't manage their own memory, except for a few classes that serve that purpose only (containers and smart pointers).

In our case, we should use std::vector rather than *unsigned long long for our storage. Then we wouldn't need to write a destructor, nor the reallocation code in operator=(). In fact, we would be able to just use the compiler-generated assignment operators (both copy and move) rather than writing any code there - code you don't have to write is the easiest to get right and to maintain!


Construction from std::string should probably be explicit, as we really don't want that to be an automatic conversion. Consider accepting a string view as argument where that's available (C++17 onwards).


I'm surprised not to see assignment-arithmetic operators such as +=, *=, %= and so on. Usually we want to implement these first, in order to then implement the corresponding non-assigning versions very simply - e.g.

Big_Int& operator/=(const Big_Int&);

friend Big_Int operator/(Big_Int a, const Big_Int& b)
{
    return a /= b;
}

Returning a const object like this is pointless:

static const Big_Int _pow(const Big_Int&, const Big_Int&);

The constness of the result object doesn't help the user (and it's trivially copied into a mutable object anyway), so just return a plain Big_Int.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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