多倍精度整数の基礎 ( 四則演算編 )

( 次の記事 Karatsuba乗算編 )

概要

多倍精度整数は以下の式を実装する事で表現できる.

\sum_{i = 0}^{n} coe_{i} \space radix^i

coe は次数 i ごとの任意の係数, radix は基数.
具体的には std::vector の template 引数に coe を指定し配列の添え字を i とする.

実装

準備

まずクラスに与えられるべき必要な template parameters を確認する.

template<
    class UInt = std::uint16_t,
    class DoubleUInt = std::uint32_t,
    class DoubleInt = std::int32_t,
    DoubleUInt BitNum = sizeof(UInt) * CHAR_BIT
> class integer;

• class UInt = std::uint16_t
  ここには coe の型を指定する. coe で表現できる最も大きな値 + 1 が radix になる.

• class DoubleUInt = std::uint32_t
  UInt同士の演算でキャリー等を適切に処理するために UInt の二倍超の値を表現できる型を指定する.

• class DoubleInt = std::int32_t
  こちらも class DoubleUInt = std::uint32_t と同様の理由に拠る. ただし符号付でなければならない.

• DoubleUInt BitNum = sizeof(UInt) * CHAR_BIT
UInt の bit 数を指定する. デフォルト引数なので特に変更しなくても良いが, int_fast8_t 等を使用する際に手動で入力する.

比較

• unsigned_less, unsigned_less_eq

unsigned_less, unsigned_less_eq は lhs と rhs を符号無しの値とみなし大小を比較する.

static bool unsigned_less(const data_type &lhs, const data_type &rhs){
    if(lhs.size() < rhs.size()){ return true; }
    if(lhs.size() > rhs.size()){ return false; }
    for(std::size_t i = lhs.size() - 1; i + 1 > 0; --i){
        if(lhs[i] < rhs[i]){ return true; }
        if(lhs[i] > rhs[i]){ return false; }
    }
    return false;
}

static bool unsigned_less_eq(const data_type &lhs, const data_type &rhs){
    if(lhs.size() < rhs.size()){ return true; }
    if(lhs.size() > rhs.size()){ return false; }
    for(std::size_t i = lhs.size() - 1; i + 1 > 0; --i){
        if(lhs[i] < rhs[i]){ return true; }
        if(lhs[i] > rhs[i]){ return false; }
    }
    return true;
}

• operator <, operator >

unsigned_* とは違い, こちらは符号付の大小比較を行う.
一方が定義できればもう一方はそれを利用する事で定義できる.

bool operator <(const integer &other) const{
    if(sign < other.sign){ return true; }
    if(sign > other.sign){ return false; }
    if(data.size() < other.data.size()){ return sign > 0; }
    if(data.size() > other.data.size()){ return sign < 0; }
    std::size_t i = data.size() - 1;
    do{
        if(data[i] < other.data[i]){ return true; }
    } while(i-- > 0);
    return false;
}

bool operator >(const integer &other) const{
    return other < *this;
}

• operator <=, operator >=

bool operator <=(const integer &other) const{
    if(sign < other.sign){ return true; }
    if(sign > other.sign){ return false; }
    if(data.size() < other.data.size()){ return sign > 0; }
    if(data.size() > other.data.size()){ return sign < 0; }
    std::size_t i = data.size() - 1;
    do{
        if(data[i] > other.data[i]){ return false; }
    } while(i-- > 0);
    return true;
}

bool operator >=(const integer &other) const{
    return other <= *this;
}

• operator ==, operator !=

特に工夫する点はない.

bool operator ==(const integer &other) const{
    return sign == other.sign && data == other.data;
}

bool operator !=(const integer &other) const{
    return !(*this == other);
}

加減算

加減算は lhs += rhs, lhs -= rhs という左辺に変更を伴う処理が効率が良いため, その様に実装する.
後で融通を利かせるために符号無しのものを用意しておく.

• 加算

void add(const integer &other){
    if(sign == other.sign){
        unsigned_add(other);
    }else{
        if(unsigned_less(data, other.data)){
            integer t(other);
            t.unsigned_sub(*this);
            data.swap(t.data);
            sign = other.sign;
        }else{ unsigned_sub(other); }
    }
}

• 符号無し加算

void unsigned_add(const integer &other){
    if(data.size() < other.data.size()){
        data.resize(other.data.size());
    }

    DoubleUInt c = 0;
    std::size_t i;
    for(i = 0; i < other.data.size(); ++i){
        DoubleUInt v = static_cast<DoubleUInt>(data[i]) + static_cast<DoubleUInt>(other.data[i]) + c;
        data[i] = static_cast<UInt>(v & base_mask);
        c = v >> BitNum;
    }

    for(; c > 0; ++i){
        if(i >= data.size()){ data.resize(data.size() + 1); }
        DoubleUInt v = static_cast<DoubleUInt>(data[i]) + c;
        data[i] = static_cast<UInt>(v & base_mask);
        c = v >> BitNum;
    }
}

• 1word の符号無し加算. 次数付き.

void unsigned_single_add(UInt c, std::size_t i = 0){
    if(i >= data.size()){ data.resize(i + 1); }
    for(; c > 0; ++i){
        DoubleUInt v = static_cast<DoubleUInt>(data[i]) + c;
        data[i] = static_cast<UInt>(v & base_mask);
        c = v >> BitNum;
    }
}

• 減算.

void sub(const integer &other){
    if(sign != other.sign){
        unsigned_add(other);
    }else{
        if(unsigned_less(data.data, other.data)){
            integer t(other);
            t.unsigned_sub(*this);
            data.swap(t.data);
            sign = other.sign;
        }else{ unsigned_sub(other); }
    }
}

• 符号無し減算. 次数付き.

2の補数を使用した.

void unsigned_sub(const integer &other, std::size_t i = 0){
    UInt c = 0;
    for(; i < other.data.size(); ++i){
        UInt t = data[i] - (other.data[i] + c);
        if(data[i] < other.data[i] + c){
            c = 1;
        }else{
            c = 0;
        }
        data[i] = t;
    }
    for(; c > 0; ++i){
        UInt t = data[i] - c;
        if(data[i] < c){
            c = 1;
        }else{
            c = 0;
        }
        data[i] = t;
    }
    normalize_data_size();
}

乗算

乗算は result := lhs * rhs という様に, 新たにオブジェクトを生成してそこに結果を挿入する処理が効率が良いため, その様に実装する.
こちらも符号無しがあると後々都合が良い.

• 乗算

static integer mul(const integer &lhs, const integer &rhs){
    integer r;
    unsigned_mul(r, lhs, rhs);
    r.sign = lhs.sign * rhs.sign;
    return r;
}

• 符号無し乗算

static void unsigned_mul(integer &r, const integer &lhs, const integer &rhs){
    std::size_t s = lhs.data.size() + rhs.data.size();
    r.data.resize(s + 1);
    for(std::size_t i = 0; i < lhs.data.size(); ++i){
        for(std::size_t j = 0; j < rhs.data.size(); ++j){
            DoubleUInt c = static_cast<DoubleUInt>(lhs.data[i]) * static_cast<DoubleUInt>(rhs.data[j]);
            for(std::size_t k = 0; i + j + k < s + 1; ++k){
                std::size_t u = i + j + k;
                DoubleUInt v = static_cast<DoubleUInt>(r.data[u]) + c;
                UInt a = static_cast<UInt>(v & base_mask);
                r.data[u] = a;
                c = v >> BitNum;
            }
        }
    }
    r.normalize_data_size();
}

• 1word の符号無し乗算

static void unsigned_single_mul(integer &r, const integer &lhs, UInt rhs){
    std::size_t s = lhs.data.size() + 1;
    r.data.resize(s + 1);
    for(std::size_t i = 0; i < lhs.data.size(); ++i){
        DoubleUInt c = static_cast<DoubleUInt>(lhs.data[i]) * static_cast<DoubleUInt>(rhs);
        for(std::size_t k = 0; i + k < s + 1; ++k){
            std::size_t u = i + k;
            DoubleUInt v = static_cast<DoubleUInt>(r.data[u]) + c;
            UInt a = static_cast<UInt>(v & base_mask);
            r.data[u] = a;
            c = v >> BitNum;
        }
    }
    r.normalize_data_size();
}

除算

ここでは基礎的な低速な除算を扱う.

準備

• 次数単位で値を左増やす = 単に先頭に n 個の 0 を追加するだけ.

void shift_container(std::size_t n){
    data.insert(data.begin(), n, 0);
}

• offset の位置にある値を表現するのに bit 数がいくつ必要かを得る

std::size_t bit_num(std::size_t offset) const{
    std::size_t n = 0;
    UInt x = data[offset];
    while(x > 0){
        ++n;
        x >>= 1;
    }
    return n;
}

• 多倍精度整数を bit 単位で left shift

処理系の定める std::size_t の扱える数値の大きさで制限を受ける点に注意.

std::size_t finite_bit_shift_lsr(std::size_t n){
    std::size_t
        digit = n / static_cast<std::size_t>(BitNum),
        shift = n % static_cast<std::size_t>(BitNum),
        rev_shift = static_cast<std::size_t>(BitNum) - shift;
    UInt c = 0;
    for(std::size_t i = 0; i < data.size(); ++i){
        UInt x = data[i];
        data[i] = (x << shift) | c;
        if(rev_shift < BitNum){
            c = x >> rev_shift;
        }else{
            c = 0;
        }
    }
    if(c > 0){ data.push_back(c); }
    return digit;
}

• bit 単位の left shift 本体

void bit_shift_lsr(std::size_t n){
    shift_container(finite_bit_shift_lsr(n));
}

• bit 単位の right shift

void bit_shift_rsl(std::size_t n){
    std::size_t
        digit = n / static_cast<std::size_t>(BitNum),
        shift = n % static_cast<std::size_t>(BitNum),
        rev_shift = BitNum - shift,
        size = data.size();

    if(digit > 0){
        for(std::size_t i = 0, length = size - digit; i < length; ++i){
            data[i] = data[i + digit];
        }
        for(std::size_t i = 0; i < digit; ++i){
            data[size - i - 1] = 0;
        }
    }

    UInt c = 0;
    for(std::size_t i = 0; i < data.size(); ++i){
        std::size_t j = size - i - 1;
        UInt x = data[j];
        data[j] = (x >> shift) | c;
        if(rev_shift < BitNum){
            x = x << rev_shift;
        }else{
            c = 0;
        }
    }
    normalize_data_size();
}

• 多倍精度整数内部表現の正規化

void normalize_data_size(){
    if(data.size() == 0 && data.front() == 0){
        data.clear();
    }else{
        std::size_t n = data.size() - 1;
        while(n > 0 && data[n] == 0){ --n; }
        data.resize(n + 1);
    }
}

• Quotient, Remainder を格納する構造体の定義

struct quo_rem{
    integer quo, rem;

    quo_rem() = default;
    quo_rem(const quo_rem&) = default;
    quo_rem(quo_rem &&other) : quo(std::move(other.quo)), rem(std::move(other.rem)){}
    ~quo_rem() = default;
};

実装

簡単にするため, bit 単位の回復型除算を実装する. まずは unsigned から.

static quo_rem unsigned_div(const integer &lhs, const integer &rhs){
    quo_rem qr;
    qr.quo.data.reserve(lhs.data.size());
    qr.rem.data.reserve(rhs.data.size());
    qr.rem.data.push_back(0);
    for(std::size_t i = lhs.data.size() * static_cast<std::size_t>(BitNum)-1; i + 1 > 0; --i){
        qr.rem <<= 1;
        qr.rem.data[0] |= (lhs.data[i / static_cast<std::size_t>(BitNum)] >> (i % static_cast<std::size_t>(BitNum))) & 1;
        if(unsigned_less_eq(rhs.data, qr.rem.data)){
            qr.rem.unsigned_sub(rhs);
            std::size_t t = i / static_cast<std::size_t>(BitNum);
            if(qr.quo.data.size() < t + 1){ qr.quo.data.resize(t + 1); }
            qr.quo.data[t] |= 1 << (i % BitNum);
        }
    }
    return qr;
}

符号の処理を追記して完了.

static quo_rem div(const integer &lhs, const integer &rhs){
    quo_rem qr = unsigned_div(lhs, rhs);
    qr.quo.sign = qr.rem.sign = lhs.sign == rhs.sign;
    return qr;
}

全体像

#ifndef MULTI_PRECISION_INCLUDE_INTEGER_HPP
#define MULTI_PRECISION_INCLUDE_INTEGER_HPP

#include <vector>
#include <iostream>
#include <string>
#include <cstdint>
#include <climits>
#include <cmath>

namespace multi_precision{
    template<class UInt = std::uint16_t, class DoubleUInt = std::uint32_t, class DoubleInt = std::int32_t, DoubleUInt BitNum = sizeof(UInt) * CHAR_BIT>
    class integer{
    public:
        static const DoubleUInt base_mask = (static_cast<DoubleUInt>(1) << BitNum) - 1;
        static const UInt half = static_cast<UInt>(static_cast<DoubleUInt>(1) << (BitNum - 1));

        using data_type = std::vector<UInt>;
        data_type data;
        DoubleInt sign = +1;

        integer() = default;
        integer(const integer&) = default;
        integer(integer &&other) : data(std::move(other.data)), sign(other.sign){}
        integer(int x){
            if(x == 0){ return; }

            data.resize(1);
            data[0] = std::abs(x);

            sign = x >= 0 ? +1 : -1;
        }

        integer(UInt x){
            if(x == 0){ return; }

            data.resize(1);
            data[0] = x;

            sign = +1;
        }

        integer(const char *str){
            build_from_str(str);
        }

        integer(const std::string &str){
            build_from_str(str.begin());
        }

        template<class StrIter>
        void build_from_str(StrIter iter){
            if(*iter == '-'){
                sign = -1;
                ++iter;
            }

            char buff[2] = { 0 };
            while(*iter){
                buff[0] = *iter;
                int a = std::atoi(buff);
                *this *= 10;
                unsigned_single_add(a);
                ++iter;
            }
        }

        ~integer() = default;

        integer &operator =(const integer &other){
            data = other.data;
            sign = other.sign;
            return *this;
        }

        integer &operator =(integer &&other){
            data = std::move(other.data);
            sign = std::move(other.sign);
            return *this;
        }

        bool operator <(const integer &other) const{
            if(sign < other.sign){ return true; }
            if(sign > other.sign){ return false; }
            if(data.size() < other.data.size()){ return sign > 0; }
            if(data.size() > other.data.size()){ return sign < 0; }
            std::size_t i = data.size() - 1;
            do{
                if(data[i] < other.data[i]){ return true; }
            } while(i-- > 0);
            return false;
        }

        bool operator >(const integer &other) const{
            return other < *this;
        }

        bool operator <=(const integer &other) const{
            if(sign < other.sign){ return true; }
            if(sign > other.sign){ return false; }
            if(data.size() < other.data.size()){ return sign > 0; }
            if(data.size() > other.data.size()){ return sign < 0; }
            std::size_t i = data.size() - 1;
            do{
                if(data[i] > other.data[i]){ return false; }
            } while(i-- > 0);
            return true;
        }

        bool operator >=(const integer &other) const{
            return other <= *this;
        }

        bool operator ==(const integer &other) const{
            return sign == other.sign && data == other.data;
        }

        bool operator !=(const integer &other) const{
            return !(*this == other);
        }

        static bool unsigned_less(const data_type &lhs, const data_type &rhs){
            if(lhs.size() < rhs.size()){ return true; }
            if(lhs.size() > rhs.size()){ return false; }
            for(std::size_t i = lhs.size() - 1; i + 1 > 0; --i){
                if(lhs[i] < rhs[i]){ return true; }
                if(lhs[i] > rhs[i]){ return false; }
            }
            return false;
        }

        static bool unsigned_less_eq(const data_type &lhs, const data_type &rhs){
            if(lhs.size() < rhs.size()){ return true; }
            if(lhs.size() > rhs.size()){ return false; }
            for(std::size_t i = lhs.size() - 1; i + 1 > 0; --i){
                if(lhs[i] < rhs[i]){ return true; }
                if(lhs[i] > rhs[i]){ return false; }
            }
            return true;
        }

        void add(const integer &other){
            if(sign == other.sign){
                unsigned_add(other);
            }else{
                if(unsigned_less(data, other.data)){
                    integer t(other);
                    t.unsigned_sub(*this);
                    data.swap(t.data);
                    sign = other.sign;
                }else{ unsigned_sub(other); }
            }
        }

        void sub(const integer &other){
            if(sign != other.sign){
                unsigned_add(other);
            }else{
                if(unsigned_less(data.data, other.data)){
                    integer t(other);
                    t.unsigned_sub(*this);
                    data.swap(t.data);
                    sign = other.sign;
                }else{ unsigned_sub(other); }
            }
        }

        void unsigned_add(const integer &other){
            if(data.size() < other.data.size()){
                data.resize(other.data.size());
            }

            DoubleUInt c = 0;
            std::size_t i;
            for(i = 0; i < other.data.size(); ++i){
                DoubleUInt v = static_cast<DoubleUInt>(data[i]) + static_cast<DoubleUInt>(other.data[i]) + c;
                data[i] = static_cast<UInt>(v & base_mask);
                c = v >> BitNum;
            }

            for(; c > 0; ++i){
                if(i >= data.size()){ data.resize(data.size() + 1); }
                DoubleUInt v = static_cast<DoubleUInt>(data[i]) + c;
                data[i] = static_cast<UInt>(v & base_mask);
                c = v >> BitNum;
            }
        }

        void unsigned_single_add(UInt c, std::size_t i = 0){
            if(i >= data.size()){ data.resize(i + 1); }
            for(; c > 0; ++i){
                DoubleUInt v = static_cast<DoubleUInt>(data[i]) + c;
                data[i] = static_cast<UInt>(v & base_mask);
                c = v >> BitNum;
            }
        }

        void unsigned_sub(const integer &other, std::size_t i = 0){
            UInt c = 0;
            for(; i < other.data.size(); ++i){
                UInt t = data[i] - (other.data[i] + c);
                if(data[i] < other.data[i] + c){
                    c = 1;
                }else{
                    c = 0;
                }
                data[i] = t;
            }
            for(; c > 0; ++i){
                UInt t = data[i] - c;
                if(data[i] < c){
                    c = 1;
                }else{
                    c = 0;
                }
                data[i] = t;
            }
            normalize_data_size();
        }

        static void unsigned_mul(integer &r, const integer &lhs, const integer &rhs){
            std::size_t s = lhs.data.size() + rhs.data.size();
            r.data.resize(s + 1);
            for(std::size_t i = 0; i < lhs.data.size(); ++i){
                for(std::size_t j = 0; j < rhs.data.size(); ++j){
                    DoubleUInt c = static_cast<DoubleUInt>(lhs.data[i]) * static_cast<DoubleUInt>(rhs.data[j]);
                    for(std::size_t k = 0; i + j + k < s + 1; ++k){
                        std::size_t u = i + j + k;
                        DoubleUInt v = static_cast<DoubleUInt>(r.data[u]) + c;
                        UInt a = static_cast<UInt>(v & base_mask);
                        r.data[u] = a;
                        c = v >> BitNum;
                    }
                }
            }
            r.normalize_data_size();
        }

        static integer mul(const integer &lhs, const integer &rhs){
            integer r;
            unsigned_mul(r, lhs, rhs);
            r.sign = lhs.sign * rhs.sign;
            return r;
        }

        static void unsigned_single_mul(integer &r, const integer &lhs, UInt rhs){
            std::size_t s = lhs.data.size() + 1;
            r.data.resize(s + 1);
            for(std::size_t i = 0; i < lhs.data.size(); ++i){
                DoubleUInt c = static_cast<DoubleUInt>(lhs.data[i]) * static_cast<DoubleUInt>(rhs);
                for(std::size_t k = 0; i + k < s + 1; ++k){
                    std::size_t u = i + k;
                    DoubleUInt v = static_cast<DoubleUInt>(r.data[u]) + c;
                    UInt a = static_cast<UInt>(v & base_mask);
                    r.data[u] = a;
                    c = v >> BitNum;
                }
            }
            r.normalize_data_size();
        }

        struct quo_rem{
            integer quo, rem;

            quo_rem() = default;
            quo_rem(const quo_rem&) = default;
            quo_rem(quo_rem &&other) : quo(std::move(other.quo)), rem(std::move(other.rem)){}
            ~quo_rem() = default;
        };

        static quo_rem unsigned_div(const integer &lhs, const integer &rhs){
            quo_rem qr;
            qr.quo.data.reserve(lhs.data.size());
            qr.rem.data.reserve(rhs.data.size());
            qr.rem.data.push_back(0);
            for(std::size_t i = lhs.data.size() * static_cast<std::size_t>(BitNum)-1; i + 1 > 0; --i){
                qr.rem <<= 1;
                qr.rem.data[0] |= (lhs.data[i / static_cast<std::size_t>(BitNum)] >> (i % static_cast<std::size_t>(BitNum))) & 1;
                if(unsigned_less_eq(rhs.data, qr.rem.data)){
                    qr.rem.unsigned_sub(rhs);
                    std::size_t t = i / static_cast<std::size_t>(BitNum);
                    if(qr.quo.data.size() < t + 1){ qr.quo.data.resize(t + 1); }
                    qr.quo.data[t] |= 1 << (i % BitNum);
                }
            }
            return qr;
        }

        static quo_rem div(const integer &lhs, const integer &rhs){
            quo_rem qr = unsigned_div(lhs, rhs);
            qr.quo.sign = qr.rem.sign = lhs.sign == rhs.sign;
            return qr;
        }

        void shift_container(std::size_t n){
            data.insert(data.begin(), n, 0);
        }

        std::size_t bit_num(std::size_t offset = data.size() - 1) const{
            std::size_t n = 0, count = static_cast<std::size_t>(BitNum / 2);
            UInt mask = (1 << count) - 1, x = data[offset];
            while(x){
                n += x & mask > 0 ? count : 0;
                count /= 2;
                x >>= count;
                mask = (1 << count) - 1;
            }
            return n;
        }

        std::size_t finite_bit_shift_lsr(std::size_t n){
            std::size_t
                digit = n / static_cast<std::size_t>(BitNum),
                shift = n % static_cast<std::size_t>(BitNum),
                rev_shift = static_cast<std::size_t>(BitNum) - shift;
            UInt c = 0;
            for(std::size_t i = 0; i < data.size(); ++i){
                UInt x = data[i];
                data[i] = (x << shift) | c;
                if(rev_shift < BitNum){
                    c = x >> rev_shift;
                }else{
                    c = 0;
                }
            }
            if(c > 0){ data.push_back(c); }
            return digit;
        }

        void bit_shift_lsr(std::size_t n){
            shift_container(finite_bit_shift_lsr(n));
        }

        void bit_shift_rsl(std::size_t n){
            std::size_t
                digit = n / static_cast<std::size_t>(BitNum),
                shift = n % static_cast<std::size_t>(BitNum),
                rev_shift = BitNum - shift,
                size = data.size();

            if(digit > 0){
                for(std::size_t i = 0, length = size - digit; i < length; ++i){
                    data[i] = data[i + digit];
                }
                for(std::size_t i = 0; i < digit; ++i){
                    data[size - i - 1] = 0;
                }
            }

            UInt c = 0;
            for(std::size_t i = 0; i < data.size(); ++i){
                std::size_t j = size - i - 1;
                UInt x = data[j];
                data[j] = (x >> shift) | c;
                if(rev_shift < BitNum){
                    x = x << rev_shift;
                }else{
                    c = 0;
                }
            }
            normalize_data_size();
        }

        void normalize_data_size(){
            if(data.size() == 0 && data.front() == 0){
                data.clear();
            }else{
                std::size_t n = data.size() - 1;
                while(n > 0 && data[n] == 0){ --n; }
                data.resize(n + 1);
            }
        }

#define MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(assign_op, op, type) \
    integer &operator assign_op(const type &rhs){ *this = *this op integer(rhs); return *this; }

        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(+= , +, int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(-= , -, int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(*= , *, int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(/= , / , int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(%= , %, int);

        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(+= , +, unsigned int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(-= , -, unsigned int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(*= , *, unsigned int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(/= , / , unsigned int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(%= , %, unsigned int);
    };

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator +(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> t(lhs);
        t.add(rhs);
        return t;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator -(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> t(lhs);
        t.sub(rhs);
        return t;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator *(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        return integer<UInt, DoubleUInt, DoubleInt, BitNum>::mul(lhs, rhs);
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator /(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        return integer<UInt, DoubleUInt, DoubleInt, BitNum>::div(lhs, rhs).quo;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator %(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        return integer<UInt, DoubleUInt, DoubleInt, BitNum>::div(lhs, rhs).rem;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator <<(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, UInt n){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> x(lhs);
        x.bit_shift_lsr(n);
        return x;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator >>(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, UInt n){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> x(lhs);
        x.bit_shift_rsl(n);
        return x;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator +=(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        add(rhs);
        return *this;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator -=(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        sub(rhs);
        return *this;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator *=(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        *this = integer<UInt, DoubleUInt, DoubleInt, BitNum>::mul(lhs, rhs);
        return *this;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> &operator /=(integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        lhs = integer<UInt, DoubleUInt, DoubleInt, BitNum>::div(lhs, rhs).quo;
        return lhs;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator %=(integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        lhs = integer<UInt, DoubleUInt, DoubleInt, BitNum>::div(lhs, rhs).rem;
        return lhs;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator <<=(integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, std::size_t n){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> x(lhs);
        x.bit_shift_lsr(n);
        lhs = std::move(x);
        return lhs;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator >>=(integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, std::size_t n){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> x(lhs);
        x.bit_shift_rsl(n);
        lhs = std::move(x);
        return lhs;
    }

#define MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(op, type) \
    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum> \
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator op(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const type &rhs){ return lhs op integer<UInt, DoubleUInt, DoubleInt, BitNum>(rhs); } \
    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum> \
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator op(const type &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){ return integer<UInt, DoubleUInt, DoubleInt, BitNum>(lhs) op rhs; }

    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(+, int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(-, int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(*, int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(/ , int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(%, int);

    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(+, unsigned int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(-, unsigned int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(*, unsigned int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(/ , unsigned int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(%, unsigned int);

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    std::ostream &operator <<(
        std::ostream &os,
        integer<UInt, DoubleUInt, DoubleInt, BitNum> rhs
    ){
        using integer = integer<UInt, DoubleUInt, DoubleInt, BitNum>;
        std::vector<std::string> rseq;
        integer lo(10);
        for(; rhs.data.size() > 0; rhs /= lo){
            rseq.push_back(std::to_string((rhs % lo).data[0]));
        }
        os << (rhs.sign > 0 ? "" : "-");
        for(auto iter = rseq.rbegin(); iter != rseq.rend(); ++iter){
            os << *iter;
        }
        return os;
    }
}
#endif // MULTI_PRECISION_INCLUDE_INTEGER_HPP

動かしてみる

以下のコードでテストを行ってみる.

#include <iostream>
 
int main(){
    using integer = multi_precision::integer<>;
 
    integer
        a("4967236591364265674231193736514226168778105194000932034376"),
        b("19825292459530808971875");
 
    integer t = a / b, u = a % b;
 
    std::cout << "a = " << a << std::endl;
    std::cout << "b = " << b << std::endl;
    std::cout << "t = " << t << std::endl;
    std::cout << "u = " << u << std::endl;
 
    if(a == t * b + u){
        std::cout << "success.\nYOKATTANE..." << std::endl;
    }
 
    return 0;
}

実行結果...

a = 4967236591364265674231193736514226168778105194000932034376
b = 19825292459530808971875
t = 250550482496227534224774485356120781
u = 1
success.
YOKATTANE...