6
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ If you use C++20 then write it with modules instead of a header. \$\endgroup\$
    – ALX23z
    May 4 at 12:27
  • \$\begingroup\$ @ALX23z I'm a beginner so I didn't knew they existed. Has gcc already implemented them? Anyway, I'll look into it, thanks! \$\endgroup\$ May 4 at 12:31
  • \$\begingroup\$ Why are you using base 256 instead of the largest integer word available? \$\endgroup\$
    – JDługosz
    May 4 at 13:53
  • \$\begingroup\$ @JDługosz Because unsigned char gets automatically promoted to int during calculations, and that means no overflow problems. \$\endgroup\$ May 4 at 14:35
  • 1
    \$\begingroup\$ But if you held uint32_t values, you could do the arithmetic using uint64_t and it will be 4 times faster. The promotion is not automatic, but it is there for you to use. \$\endgroup\$
    – JDługosz
    May 4 at 14:42
3
\$\begingroup\$
  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.

\$\endgroup\$
5
  • \$\begingroup\$ What do you mean by "sort includes"? You mean alphabetically? \$\endgroup\$ May 6 at 16:05
  • \$\begingroup\$ Generally, there are three types of includes: 1. The header of the current TU. 2. The headers of libraries not part of the project. 3. Other headers from the project. The best way to assure independence for headers is putting (1) first. The best way to avoid your headers screwing around with others is putting (3) last. The best way to keep it maintainable (reduce diffs and keep it easily scannable by the mark 1 eyeball) is ordering each group with some universally applicable unambiguous and well-known rule. Alphabetically fits that. As an aside, some subdivide (2) into standard and others. \$\endgroup\$ May 6 at 16:23
  • \$\begingroup\$ If you use precompiled headers, that would be an exception due to mechanics and put above it all. \$\endgroup\$ May 6 at 16:24
  • \$\begingroup\$ What is "the current TU"? \$\endgroup\$ May 6 at 16:32
  • \$\begingroup\$ Translation Unit is the technical term C and C++ use for the code fed to the compiler in one chunk, usually stored in a file. Though the #includes the preprocessor handles generally draw much more code in then is in just that one file. compiled TUs and libs and assorted tidbits are then fed to the linker and result in an executable or dynamic library. \$\endgroup\$ May 6 at 16:38
2
\$\begingroup\$
    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?

\$\endgroup\$
7
  • \$\begingroup\$ I called normalize() at the end of the subtract function because the operations of the subtract function can leave leading zeroes in the number, which isn't a valid state and will break many things if not corrected. \$\endgroup\$ May 4 at 14:54
  • \$\begingroup\$ But operator<=> implicitly defines operator== only when it's defaulted. Defaulting == makes sense, and I will do it (thank you for the advice!), but I don't think I can default <=> too. \$\endgroup\$ May 4 at 15:02
  • \$\begingroup\$ I believe @ThePirate42 is right. For default to work it needs to compare from the back (if more significant digits are at the back). \$\endgroup\$ May 4 at 15:47
  • \$\begingroup\$ Isn't the 3-way comparison for Less, Equal, or Greater? It just needs to be returning a strong_ordering. \$\endgroup\$
    – JDługosz
    May 4 at 17:06
  • \$\begingroup\$ @JDługosz "If operator<=> is defaulted and operator== is not declared at all, then operator== is implicitly defaulted." From en.cppreference.com/w/cpp/language/default_comparisons. According to this site, operator<=> needs to be defaulted for operator== to be automatically generated. \$\endgroup\$ May 4 at 19:36

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.