(FOLLOW-UP) Header-only bigint library written in c++20

Question

This question is a follow up of Header only bigint library written in c++20.

I've made all (or almost all) the corrections suggested in the answers, plus some minor change here and there and a modification in the division algorithm. Instead of a lot of constructors, now there are only two template construcors, limited by concepts. The reason I do this instead of just defining a constructor for the biggest types is because I want the bigint class to work seamlessly with all the builtin integer types.

I made a follow-up question for two reasons:

One of the people who replied said that he/she's "sure there is more".
If everything else is mostly correct, I would like some comments on the algoritms that I used (If there are better choices, if they can be optimized in some places etc.), particularly for stobi and the division algorithm (but also for the other stuff).

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 GCC 11.2 when it will come out.

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

using std::uint_least64_t;
using std::uint32_t;
using std::uintmax_t;
using size_type = uint_least64_t;

class bigint {
    
    static const uint_least64_t BASE=static_cast<uint_least64_t>(std::numeric_limits<uint32_t>::max())+1;
    static const uint_least64_t DIGITS10BASE=static_cast<uint_least64_t>(std::numeric_limits<uint32_t>::digits10)+1;
    
    bool negative=false;
    std::vector<uint32_t> container;
    
    uint_least64_t getDigit(size_type k) const{
        if(k>=container.size()){
            return 0;
        }
        return container[k];
    }
    
    void normalize(){
        while(container.size()!=0 && container.back()==0){
            container.pop_back();
        }
        if(container.size()==0){
            container.push_back(0);
            negative=false;
        }
        container.shrink_to_fit();
    }
    
public:

    // Constructors
    bigint() : container{0} {}
    
    template<std::integral T>
    bigint(T n){
        if(n==0){
            container.push_back(0);
            return;
        }
        uintmax_t l;
        if(n<0){
            negative=true;
            l=static_cast<uintmax_t>(-(n+1))+1;
        } else {
            l=n;
        }
        while(l>0){
            container.push_back(l%BASE);
            l/=BASE;
        }
    }
    
    template<std::floating_point T>
    explicit bigint(T n){
        if(n>-1 && n<1){
            container.push_back(0);
            return;
        }
        long double l=n;
        if(l<0){
            negative=true;
            l=-l;
        }
        l=std::floor(l);
        while(l>=1){
            container.push_back(std::fmod(l,BASE));
            l=std::floor(l/BASE);
        }
    }

    // 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) = default;
    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(size_type con=container.size(); con>0; con--){
            std::cout << container[con-1] << "_";
        }
        std::cout << "[" << container.size() << "," << BASE << "," << DIGITS10BASE << "]" << "\n" << std::flush;
    }
};

bigint stobi(const std::string &str){
    bigint res;
    
    std::string::const_iterator msd=std::find_if_not(str.begin(),str.end(),[](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(),[](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(),[](char d){return std::isdigit(d);});
    
    res.container.clear();
    std::string n(msd,alsd);
    while(n.size()>bigint::DIGITS10BASE || std::stoull(std::string(n,0,bigint::DIGITS10BASE))>=bigint::BASE){
        std::string quot;
        size_type con=bigint::DIGITS10BASE;
        uint_least64_t partdivid=std::stoull(std::string(n,0,bigint::DIGITS10BASE));
        if(partdivid<bigint::BASE){
            partdivid=partdivid*10+(n[con]-'0');
            con++;
        }
        while(con<n.size()){
            quot+=partdivid/bigint::BASE+'0';
            partdivid=(partdivid%bigint::BASE)*10+(n[con]-'0');
            con++;
        }
        quot+=partdivid/bigint::BASE+'0';
        partdivid%=bigint::BASE;
        res.container.push_back(partdivid);
        n=quot;
    }
    res.container.push_back(std::stoull(n));
    
    return res;
}

inline 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;
}
    
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;
    }
    size_type digits=container.size();
    if(digits<b.container.size()){
        digits=b.container.size();
    }
    uint_least64_t rem=0;
    for(size_type k=0; k<digits; k++){
        uint_least64_t 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;
    }
    size_type digits=container.size();
    uint_least64_t rem=0;
    for(size_type k=0; k<digits; k++){
        uint_least64_t diff=BASE+getDigit(k)-b.getDigit(k)-rem;
        rem=1;
        if(diff>=BASE){
            diff-=BASE;
            rem=0;
        }
        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(size_type k=0; k<b.container.size(); k++){
        bigint part;
        part.container=std::vector<uint32_t>(k,0);
        uint_least64_t rem=0;
        for(size_type j=0; j<container.size() || rem!=0; j++){
            uint_least64_t prod=(b.getDigit(k)*getDigit(j))+rem;
            rem=prod/BASE;
            prod%=BASE;
            part.container.push_back(prod);
        }
        part.normalize();
        sum+=part;
    }
    *this=sum;
    negative=sign;
    return *this;
}

bigint& bigint::operator/=(const bigint &b){
    if(b==0_bi){
        throw std::domain_error("bigint: Division by zero");
    }
    if(biabs(*this)<biabs(b)){
        *this=0_bi;
        return *this;
    }
    bool sign=(negative!=b.negative);
    bigint quot,partdivid;
    size_type con=b.container.size();
    quot.container.clear();
    partdivid.container=std::vector<uint32_t>(container.end()-con,container.end());
    con++;
    if(partdivid<b){
        partdivid.container.insert(partdivid.container.begin(),*(container.end()-con));
        con++;
    }
    while(con<=container.size()){
        uint_least64_t min=0;
        uint_least64_t max=BASE-1;
        while(max-min>1){
            uint_least64_t mid=min+(max-min)/2;
            if(partdivid-b*mid<0_bi){
                max=mid-1;
            } else {
                min=mid;
            }
        }
        uint_least64_t partquot;
        if(partdivid-b*max<0_bi){
            partquot=min;
        } else {
            partquot=max;
        }
        partdivid-=b*partquot;
        quot.container.push_back(partquot);
        partdivid.container.insert(partdivid.container.begin(),*(container.end()-con));
        partdivid.normalize();
        con++;
    }
    uint_least64_t min=0;
    uint_least64_t max=BASE-1;
    while(max-min>1){
        uint_least64_t mid=min+(max-min)/2;
        if(partdivid-b*mid<0_bi){
            max=mid-1;
        } else {
            min=mid;
        }
    }
    uint_least64_t partquot;
    if(partdivid-b*max<0_bi){
        partquot=min;
    } else {
        partquot=max;
    }
    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;
}

Toby Speight · Accepted Answer · 2021-05-13 08:38:13Z

I tried this code with a simple main():

#include <iostream>
int main()
{
    bigint a(1'048'576);
    bigint b = a*a*a*a;
    std::cout
        << b/a/a/a
        << '\n';
}

This allocated 47,580 bytes more than std::cout << '\n';, which seems like much more than necessary. We should investigate just why there's so much copying going on, particularly as the class appears move-friendly.

One possibility is that the literals 0_bi and 1_bi that appear so often could be usefully be replaced with static constants.

Style: the code is hard to read with no spaces around operators.

using std::uint_least64_t;
using std::uint32_t;
using std::uintmax_t;
using size_type = uint_least64_t;

These are all in the global scope, and therefore affect every translation unit that includes this header. They would make more sense as member types of bigint.

BASE and DIGITS10BASE are C++ identifiers, so don't write them in all-caps - standard convention reserves that for macros (which need special attention because they don't obey the rules of scope, and expand arguments rather than evaluating them).

    while(container.size()!=0 && container.back()==0){
        container.pop_back();
    }
    if(container.size()==0){
        container.push_back(0);
        negative=false;
    }

container.size() == 0 is more usually written container.empty(). I'm not sure I like removing the last zero and then reinstating when necessary (although I can see it's a convenient way to convert -0 to +0).

I like the care you've taken to avoid overflow here:

        l=static_cast<uintmax_t>(-(n+1))+1;

It might be worth a comment pointing out that we know n is a signed type, and therefore the result will fit comfortably in a std::uintmax_t.

I think we could use std::remquo here:

        container.push_back(std::fmod(l,BASE));
        l=std::floor(l/BASE);

That would become

        container.push_back(std::remquo(l, BASE, &l));

On systems with binary floating-point, there's no need to promote the argument to long double, as we've ensured that BASE is a power of 2, making the division exact. We could could make this code more efficient on the majority of systems, saving the promotion only for those where std::numeric_limits<T>::radix is not a power of two.

biabs() looks like it should be called abs(), to enable it to be used in generic functions interchangeably with the standard integer types. Similarly, stobi() should be stoi(). These would both work better if we had an enclosing namespace.

The dump() member seems to be no longer used, so I wouldn't provide it.

stobi() would be better taking a std::string_view. I think it could also reserve() a reasonable guess at the required vector length to reduce reallocation.

stobi() should probably ignore ' in input, so we can read grouped numbers:

auto a = 1'048'576;
auto b = 1'048'576_bi;
assert(a == b);  // fails; b==1

The duplication in operator<=> could be reduced, by simply swapping pointers:

std::strong_ordering operator<=>(const bigint &a, const bigint &b)
{
    if (a.negative != b.negative) {
        return b.negative <=> a.negative;
    }
    auto const *da = &a.container;
    auto const *db = &b.container;
    if (a.negative) {
        std::swap(da, db);
    }
    if (da->size() != db->size()) {
        return da->size() <=> db->size();
    }
    return std::lexicographical_compare_three_way(da->rbegin(), da->rend(), db->rbegin(), db->rend());
}

(I also eliminated the redundant comparison of a bool with true).

Instead of comparing with 0_bi, our operator bool() could directly check the array contents, with much less work:

return container.size() > 1 && container.front();

Stack Exchange Network

(FOLLOW-UP) Header-only bigint library written in c++20

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

(FOLLOW-UP) Header-only bigint library written in c++20

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions