Header only bigint library written in c++20

Question

I made this over the course of a week and a half, to use it for some Project Euler problems. My goal was to make something relatively efficient that could be used as easily as a builtin type. I also tried to make the code fully portable.

I used c++20 because of the spaceship operator, implicit comparisons and the constexpr std::vector/std::string features. When the latter will be actually implemented I will make the user defined literal operator"" _bi consteval, so that bigint literals will be computed at compile time. EDIT: I checked and apparently, even if vectors will become constexpr, they also will have to be destructed at compile-time, which means no pre-initialization of literals. :-(

Internally I used base 256, which means that the I/O functions are not trivial. Where I needed to use the base number in the code I instead used the BASE global constant, but changing the value from 256 to something else will probably break the program.

stobi (string to bigint) tries to behave exactly as std::stoi, minus the "chose the base" feature. I didn't implement it as a constructor because I wanted to encourage the use of operator"" _bi.

The arithmetic operators use "grade school" algorithms, and were inspired by the ones found in The Large Integer Case Study in C++.pdf, though they differ in some ways (also division was done entirely by me).

WARNING: don't use GCC 11.1 to compile this, the compilation will stop with an internal compiler error because of this bug. Use GCC 10 instead, or maybe GCC 11.2 when it will come out.

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <stdexcept>
#include <cctype>
#include <algorithm>
#include <limits>
#include <compare>

inline const unsigned int BASE=256;
inline const unsigned int DIGITS10BASE=3;

template<typename T>
constexpr unsigned char abs_c(const T &n){
    if(n<0){
        return -n;
    }
    return n;
}

class bigint {
    
    std::vector<unsigned char> container;
    bool negative=false;
    
    template<typename T>
    void constructFromSignInt(T n);
    template<typename T>
    void constructFromUnsignInt(T n);
    template<typename T>
    void constructFromFloat(T n);
    
    unsigned char getDigit(unsigned int &k) const{
        if(k>=container.size()){
            return 0;
        }
        return container[k];
    }
    
    void normalize(){
        container.erase(std::find_if(container.rbegin(),container.rend(),[](const unsigned char &d){return d!=0;}).base(),container.end());
        container.shrink_to_fit();
        if(container.size()==0){
            container.push_back(0);
            negative=false;
        }
        return;
    }
    
public:

    // Constructors
    bigint() : container{0} {}
    
    bigint(const bool &n) : container{n} {}
    bigint(const unsigned char &n) : container{n} {}
    bigint(const unsigned short &n) {constructFromUnsignInt<unsigned short>(n);}
    bigint(const unsigned int &n) {constructFromUnsignInt<unsigned int>(n);}
    bigint(const unsigned long &n) {constructFromUnsignInt<unsigned long>(n);}
    bigint(const unsigned long long &n) {constructFromUnsignInt<unsigned long long>(n);}
    
    bigint(const signed char &n) : container{abs_c<signed char>(n)}, negative{n<0} {}
    bigint(const char &n) : container{abs_c<char>(n)}, negative{n<0} {}
    bigint(const short &n) {constructFromSignInt<short>(n);}
    bigint(const int &n) {constructFromSignInt<int>(n);}
    bigint(const long &n) {constructFromSignInt<long>(n);}
    bigint(const long long &n) {constructFromSignInt<long long>(n);}
    
    explicit bigint(const float &n) {constructFromFloat<float>(n);}
    explicit bigint(const double &n) {constructFromFloat<double>(n);}
    explicit bigint(const long double &n) {constructFromFloat<long double>(n);}

    // Unary arithmetic operators
    bigint operator+() const {return *this;}
    inline bigint operator-() const;
    
    friend inline bigint biabs(bigint n) {n.negative=false; return n;}
    
    // Comparison operators
    friend bool operator==(const bigint &a,const bigint &b);
    friend std::strong_ordering operator<=>(const bigint &a,const bigint &b);
    
    // Compound assignment operators
    bigint& operator+=(const bigint &b);
    bigint& operator-=(const bigint &b);
    bigint& operator*=(const bigint &b);
    bigint& operator/=(const bigint &b);
    bigint& operator%=(const bigint &b);
    
    // Increment/decrement
    inline bigint& operator++();
    inline bigint& operator--();
    bigint operator++(int) {bigint old=*this; ++*this; return old;}
    bigint operator--(int) {bigint old=*this; --*this; return old;}
    
    // Conversion functions
    inline explicit operator bool() const;
    explicit operator std::string() const;
    
    friend bigint stobi(const std::string &n);
    
    // Debug
    void dump() const{
        if(negative){
            std::cout << "-_";
        }
        for(int con=container.size()-1; con>=0; con--){
            std::cout << +container[con] << "_";
        }
        std::cout << std::endl;
    }
};

bigint stobi(const std::string &str){
    bigint res;
    
    std::string::const_iterator msd=std::find_if_not(str.begin(),str.end(),[](const char &d){return std::isspace(d);});
    if(*msd=='+'){
        msd++;
    } else if(*msd=='-'){
        res.negative=true;
        msd++;
    }
    if(!std::isdigit(*msd)){
        throw std::invalid_argument("stobi");
    }
    msd=std::find_if(msd,str.end(),[](const char &d){return d!='0';});
    if(!std::isdigit(*msd)){
        res.negative=false;
        return res;
    }
    std::string::const_iterator alsd=std::find_if_not(msd,str.end(),[](const char &d){return std::isdigit(d);});
    
    res.container.clear();
    std::string n(msd,alsd);
    while(n.size()>DIGITS10BASE || std::stoul(std::string(n,0,DIGITS10BASE))>=BASE){
        std::string quot;
        unsigned int con=DIGITS10BASE;
        unsigned int partdivid=std::stoi(std::string(n,0,DIGITS10BASE));
        if(partdivid<BASE){
            partdivid=partdivid*10+(n[con]-'0');
            con+=1;
        }
        while(con<n.size()){
            quot+=partdivid/BASE+'0';
            partdivid=(partdivid%BASE)*10+(n[con]-'0');
            con++;
        }
        quot+=partdivid/BASE+'0';
        partdivid%=BASE;
        res.container.push_back(partdivid);
        n=quot;
    }
    res.container.push_back(std::stoi(n));
    
    return res;
}

bigint operator"" _bi (const char *n){
    std::string str=n;
    if(str.size()<=std::numeric_limits<unsigned long long>::digits10){
        return bigint(std::stoull(str));
    }
    return stobi(str);
}

inline bigint bigint::operator-() const{
    bigint flip=*this;
    if(flip!=0_bi){
        flip.negative=!(flip.negative);
    }
    return flip;
}

inline bigint& bigint::operator++(){
    *this+=1_bi;
    return *this;
}

inline bigint& bigint::operator--(){
    *this-=1_bi;
    return *this;
}

bool operator==(const bigint &a,const bigint &b){
    if(a.negative!=b.negative){
        return false;
    }
    return std::equal(a.container.begin(),a.container.end(),b.container.begin(),b.container.end());
}
    
std::strong_ordering operator<=>(const bigint &a,const bigint &b){
    if(a.negative!=b.negative){
        return b.negative<=>a.negative;
    }
    if(a.negative==true){
        if(a.container.size()!=b.container.size()){
            return b.container.size()<=>a.container.size();
        }
        return std::lexicographical_compare_three_way(b.container.rbegin(),b.container.rend(),a.container.rbegin(),a.container.rend());
    }
    if(a.container.size()!=b.container.size()){
        return a.container.size()<=>b.container.size();
    }
    return std::lexicographical_compare_three_way(a.container.rbegin(),a.container.rend(),b.container.rbegin(),b.container.rend());
}

inline bigint::operator bool() const{
    return *this!=0_bi;
}

inline bigint operator+(bigint a,const bigint &b){
    a+=b;
    return a;
}

inline bigint operator-(bigint a,const bigint &b){
    a-=b;
    return a;
}

inline bigint operator*(bigint a,const bigint &b){
    a*=b;
    return a;
}

inline bigint operator/(bigint a,const bigint &b){
    a/=b;
    return a;
}

inline bigint operator%(bigint a,const bigint &b){
    a%=b;
    return a;
}

bigint& bigint::operator+=(const bigint &b){
    if(this==&b){
        *this*=2_bi;
        return *this;
    }
    if(b==0_bi){
        return *this;
    }
    if(negative!=b.negative){
        *this-=-b;
        return *this;
    }
    unsigned int digits=container.size();
    if(digits<b.container.size()){
        digits=b.container.size();
    }
    unsigned int rem=0;
    for(unsigned int k=0; k<digits; k++){
        unsigned int sum=rem+getDigit(k)+b.getDigit(k);
        rem=sum/BASE;
        sum%=BASE;
        if(k<container.size()){
            container[k]=sum;
        } else {
            container.push_back(sum);
        }
    }
    if(rem!=0){
        container.push_back(rem);
    }
    return *this;
}

bigint& bigint::operator-=(const bigint &b){
    if(this==&b){
        *this=0_bi;
        return *this;
    }
    if(b==0_bi){
        return *this;
    }
    if(negative!=b.negative){
        *this+=-b;
        return *this;
    }
    if(biabs(*this)<biabs(b)){
        *this=-(b-*this);
        return *this;
    }
    unsigned int digits=container.size();
    unsigned int rem=0;
    for(unsigned int k=0; k<digits; k++){
        int diff=container[k]-b.getDigit(k)-rem;
        rem=0;
        if(diff<0){
            diff+=BASE;
            rem=1;
        }
        container[k]=diff;
    }
    normalize();
    return *this;
}

bigint& bigint::operator*=(const bigint &b){
    if(*this==0_bi){
        return *this;
    }
    if(b==0_bi){
        *this=0_bi;
        return *this;
    }
    bool sign=(negative!=b.negative);
    bigint sum=0_bi;
    for(unsigned int k=0; k<b.container.size(); k++){
        bigint part;
        part.container=std::vector<unsigned char>(k,0);
        unsigned int rem=0;
        for(unsigned int j=0; j<container.size() || rem!=0; j++){
            unsigned int prod=(b.container[k]*getDigit(j))+rem;
            rem=prod/BASE;
            prod%=BASE;
            part.container.push_back(prod);
        }
        sum+=part;
    }
    *this=sum;
    negative=sign;
    return *this;
}

bigint& bigint::operator/=(const bigint &b){
    if(b==0_bi){
        throw std::domain_error("Division by zero");
    }
    if(biabs(*this)<biabs(b)){
        *this=0_bi;
        return *this;
    }
    bool sign=(negative!=b.negative);
    bigint quot,partdivid;
    unsigned int con=b.container.size();
    quot.container.clear();
    partdivid.container=std::vector<unsigned char>(container.end()-con,container.end());
    con++;
    if(partdivid<b){
        partdivid.container.insert(partdivid.container.begin(),*(container.end()-con));
        con++;
    }
    while(con<=container.size()){
        unsigned int partquot=0;
        while(partdivid>=0_bi){
            partdivid-=b;
            partquot++;
        }
        partdivid+=b;
        partquot--;
        quot.container.push_back(partquot);
        partdivid.container.insert(partdivid.container.begin(),*(container.end()-con));
        partdivid.normalize();
        con++;
    }
    unsigned int partquot=0;
    while(partdivid>=0_bi){
        partdivid-=b;
        partquot++;
    }
    partquot--;
    quot.container.push_back(partquot);
    std::reverse(quot.container.begin(),quot.container.end());
    *this=quot;
    negative=sign;
    return *this;
}

bigint& bigint::operator%=(const bigint &b){
    *this=*this-(*this/b)*b;
    return *this;
}

bigint::operator std::string() const{
    std::string str;
    if(*this==0_bi){
        str+='0';
        return str;
    }
    bigint n=*this;
    n.negative=false;
    while(n>0_bi){
        str+=(n%10_bi).container[0]+'0';
        n/=10_bi;
    }
    if(negative){
        str+='-';
    }
    std::reverse(str.begin(),str.end());
    return str;
}

std::ostream& operator<<(std::ostream &os, const bigint &n){
    os << static_cast<std::string>(n);
    return os;
}

std::istream& operator>>(std::istream &is, bigint &n){
    std::string str;
    is >> str;
    try{
        n=stobi(str);
    } catch(std::invalid_argument&){
        is.setstate(std::ios::failbit);
    }
    return is;
}

template<typename T>
void bigint::constructFromSignInt(T n){
    if(n==0){
        container.push_back(0);
        return;
    }
    if(n<0){
        negative=true;
        n=-n;
    }
    while(n>0){
        container.push_back(n%BASE);
        n/=BASE;
    }
    return;
}

template<typename T>
void bigint::constructFromUnsignInt(T n){
    if(n==0){
        container.push_back(0);
        return;
    }
    while(n>0){
        container.push_back(n%BASE);
        n/=BASE;
    }
    return;
}

template<typename T>
void bigint::constructFromFloat(T n){
    if(n>-1 && n<1){
        container.push_back(0);
        return;
    }
    if(n<0){
        negative=true;
        n=-n;
    }
    n=std::floor(n);
    while(n>0){
        container.push_back(std::fmod(n,BASE));
        n/=BASE;
    }
    return;
}

Answer 1

1. Sort the includes to avoid loosing track.

2. Instead of manually providing BASE and DIGITS10BASE, use std::numeric_limits<> to derive them as needed.

3. Generally, passing a scalar type (pointer type, any fundamental type) by constant reference is premature pessimization. It opens the can of aliasing, adds an indirection for access, and rarely saves space. A reference needs the same space as an ordinary pointer, and that's generally the granularity for passing arguments.

4. Never pass by mutable reference if you don't want to use it as an out-parameter. Doing so confuses and inconveniences everyone.

5. Only use return; if you need a premature exit from a void-returning function. Otherwise, it's clutter.

6. Your abs_c() is a bit error-prone. Use <type_traits> as needed and it will be broader and correct.

   constexpr auto abs_c(std::integral auto i) noexcept {
       if constexpr(std::signed_integral<decltype(i)>)
           return std::make_unsigned_t<decltype(i)>(i < 0 ? -i : i);
       else
           return i < 0 ? -i : i;
   }
   

7. unsigned char is a bit small for a chunk-size. Using something bigger like uint32_t would give far more efficient code, unless you are on an 8-bit micro. As long as there is at least one bigger type, you can still convert to that before arithmetic to avoid wrap-around.

8. Remove all the ctors for smaller types. They won't signigicantly enhance efficiency, if at all, but clutter things up. Inlining constructFromSignInt(), constructFromUnsignInt(), and constructFromFloat() after that doubles the effect.

9. Construction from signed type could re-use construction from unsigned type after fixing negative values. Flip the sign after if needed.

10. The type for an index or byte-count is std::size_t. If you want to use something potentially smaller, make your own typedef using size_type = whatever; and use that. The type-name signals the use.

11. .normalize() fails to ensure the invariant (container always has at least one element) if the reallocation triggered by pushing an element fails. If it doesn't, it wastes time and potentially results in a larger allocation than wnted. Move shrinking after achieving the final size and simplify.

    void normalize() {
        while (container.size() && !container.back())
            container.pop_back();
        if (!container.size()) {
            container.emplace_back();
            negative = false;
        }
        container.shrink_to_fit();
    }
    

12. Don't use std::endl but \n. If flushing the stream is actually needed instead of a waste of time, use std::flush instead.

13. Defining short member-functions inline can save effort, and not only for the writer.

I'm sure there is more, but I'm done for now.

Answer 2

    if(a.negative!=b.negative){
        return false;
    }
    return std::equal(a.container.begin(),a.container.end(),b.container.begin(),b.container.end());
}

For the last line, doesn't vector's operator== do what you need?

So you end up just checking if all the data members are equal. So use the C++20 capability to autogenerate it.

But you mentioned using C++20 in order to have <=> and that includes == when you have strong_ordering. So why do you define this at all?

---

unsigned int digits=container.size();

you mean size_t. Or why not use auto? And shouldn't it be const?

int diff=container[k]-b.getDigit(k)-rem;

you're mixing signed and unsigned arithmetic. Or rather, you're doing unsigned subtractions (promoted to unsigned int for the second subtract operation) and then casting that to signed. You'll have trouble if you change the type of the container's element (like making it the largest word you can handle).

Why do you need to call normalize() at the end of the subtract function?