(FOLLOW-UP) Библиотека bigint только для заголовков, написанная на c ++ 20

От: Из: Общие

Этот вопрос является продолжением библиотеки bigint только для заголовков, написанной на C ++ 20.

Я внес все (или почти все) исправления, предложенные в ответах, плюс некоторые незначительные изменения здесь и там и модификацию алгоритма деления. Вместо множества конструкторов теперь есть только два конструктора шаблонов, ограниченных концепциями. Причина, по которой я делаю это вместо того, чтобы просто определять конструктор для самых больших типов, заключается в том, что я хочу, чтобы класс bigint работал без проблем со всеми встроенными целочисленными типами.

Я задал дополнительный вопрос по двум причинам:

  1. Один из ответивших сказал, что он / она «уверен, что есть еще кое-что».
  2. Если все остальное в основном верно, я хотел бы сделать несколько комментариев по алгоритмам, которые я использовал (если есть лучшие варианты, можно ли их оптимизировать в некоторых местах и ​​т. Д.), Особенно для stobi и алгоритм деления (но также и для прочего).

ПРЕДУПРЕЖДЕНИЕ: не используйте GCC 11.1 для компиляции, компиляция остановится из-за внутренней ошибки компилятора из-за эта ошибка. Вместо этого используйте GCC 10 или GCC 11.2, когда он выйдет.

#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;
}

1 ответ
1

Я пробовал этот код с помощью простого main():

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

Это выделило на 47 580 байт больше, чем std::cout << 'n';, что кажется намного больше, чем необходимо. Мы должны выяснить, почему происходит так много копирования, особенно учитывая, что класс кажется удобным для перемещения.

Одна из возможностей состоит в том, что литералы 0_bi а также 1_bi которые так часто появляются, можно с пользой заменить статическими константами.

Стиль: код трудно читать, без пробелов вокруг операторов.

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

Все они находятся в глобальной области и поэтому влияют на каждую единицу перевода, которая включает этот заголовок. Они имели бы больше смысла как типы членов bigint.

BASE а также DIGITS10BASE являются идентификаторами C ++, поэтому не пишите их заглавными буквами — стандартное соглашение резервирует это для макросов (которые требуют особого внимания, потому что они не подчиняются правилам области видимости и расширяют аргументы, а не оценивают их).

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

container.size() == 0 чаще пишется container.empty(). Я не уверен, что мне нравится удалять последний ноль, а затем восстанавливать при необходимости (хотя я вижу, что это удобный способ конвертировать -0 к +0).

Мне нравится, как вы позаботились о том, чтобы избежать переполнения:

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

Возможно, стоит прокомментировать, что мы знаем n — знаковый тип, поэтому результат будет удобно помещаться в std::uintmax_t.

Я думаю, мы могли бы использовать std::remquo здесь:

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

Это станет

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

В системах с двоичной плавающей точкой нет необходимости продвигать аргумент в long double, поскольку мы убедились, что BASE является степенью 2, делающей деление точным. Мы могли бы сделать этот код более эффективным на большинстве систем, сохранив продвижение только для тех, где std::numeric_limits<T>::radix это не степень двойки.

biabs() похоже, это должно называться abs(), чтобы его можно было использовать в универсальных функциях взаимозаменяемо со стандартными целочисленными типами. По аналогии, stobi() должно быть stoi(). Оба они работали бы лучше, если бы у нас было закрывающее пространство имен.

В dump() member, похоже, больше не используется, поэтому я не стал бы его предоставлять.

stobi() было бы лучше взять std::string_view. Я думаю, это тоже могло reserve() разумное предположение о необходимой длине вектора для уменьшения перераспределения.

stobi() вероятно, следует игнорировать ' на входе, поэтому мы можем читать сгруппированные числа:

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

Дублирование в operator<=> можно уменьшить, просто поменяв местами указатели:

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());
}

(Я также исключил избыточное сравнение bool с участием true).

Вместо сравнения с 0_bi, наш operator bool() мог напрямую проверить содержимое массива с гораздо меньшими затратами:

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

    Похожие записи:

    1. Библиотека bigint только для заголовков, написанная на c ++ 20
    2. C ++ 20: я — матрица, вещание, np.dot () и np.matmul ()
    3. Функция batch_recursive_count_if с уровнем распаковки для произвольной вложенной итерируемой реализации произвольного типа в C ++
    4. Оценка покерных рук (оптимизация скорости)
    5. C ++ 20: N-мерный минимальный класс Matrix

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *