大整数高精度计算——有趣的实现

Mar 5, 2021 6 min read 杂谈

这里收录一些有意思的实现，不过我都有进行改编以更方便使用，不过千万不要指望这性能有多高。收录的条件：

支持四则运算，必须包含除法及求余
支持字符串输入输出
代码不长

small biginteger library for contest

代码原作者Jane Alam Jan，你可以在Google上直接搜索small_biginteger_library_for_contest.pdf并下载到原始说明文档及代码，这里提供一份代码，改动不多，增加了int的构造函数和其它不等号的重载，乘法效率有优化，且增加输出到string而不直接输出终端，以便在其它场合使用更方便。

struct Bigint {
    // representations and structures
    std::string a; // to store the digits
    int sign;      // sign = -1 for negative numbers, sign = 1 otherwise
    // constructors
    Bigint() {}                            // default constructor
    Bigint(std::string b) { (*this) = b; } // constructor for string
    Bigint(int v) {
        char buf[30];
        sprintf(buf, "%d", v);
        (*this) = buf;
    }
    // some helpful methods
    int size() { return a.size(); } // returns number of digits
    Bigint inverseSign() {
        sign *= -1;
        return (*this);
    }
    Bigint normalize(int newSign) { // removes leading 0, fixes sign
        for (int i = a.size() - 1; i > 0 && a[i] == '0'; i--)
            a.erase(a.begin() + i);
        sign = (a.size() == 1 && a[0] == '0') ? 1 : newSign;
        return (*this);
    }
    // assignment operator
    void operator=(std::string b) { // assigns a string to Bigint
        a = b[0] == '-' ? b.substr(1) : b;
        reverse(a.begin(), a.end());
        this->normalize(b[0] == '-' ? -1 : 1);
    }
    // conditional operators
    bool operator<(const Bigint &b) const { // less than operator
        if (sign != b.sign) return sign < b.sign;
        if (a.size() != b.a.size()) return sign == 1 ? a.size() < b.a.size() : a.size() > b.a.size();
        for (int i = a.size() - 1; i >= 0; i--)
            if (a[i] != b.a[i]) return sign == 1 ? a[i] < b.a[i] : a[i] > b.a[i];
        return false;
    }
    bool operator==(const Bigint &b) const { return a == b.a && sign == b.sign; }
    // mathematical operators
    Bigint operator+(Bigint b) { // addition operator overloading
        if (sign != b.sign) return (*this) - b.inverseSign();
        Bigint c;
        for (int i = 0, carry = 0; i < a.size() || i < b.size() || carry; i++) {
            carry += (i < a.size() ? a[i] - 48 : 0) + (i < b.a.size() ? b.a[i] - 48 : 0);
            c.a += (carry % 10 + 48);
            carry /= 10;
        }
        return c.normalize(sign);
    }
    Bigint operator-(Bigint b) { // subtraction operator overloading
        if (sign != b.sign) return (*this) + b.inverseSign();
        int s = sign;
        sign = b.sign = 1;
        if ((*this) < b) return ((b - (*this)).inverseSign()).normalize(-s);
        Bigint c;
        for (int i = 0, borrow = 0; i < a.size(); i++) {
            borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
            c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
            borrow = borrow >= 0 ? 0 : 1;
        }
        return c.normalize(s);
    }
    Bigint operator*(Bigint b) { // multiplication operator overloading
        if (b < *this) return b * *this;
        Bigint c("0");
        for (int i = 0, k = a[i] - 48; i < a.size(); i++, k = a[i] - 48) {
            while (k--)
                c = c + b;                // ith digit is k, so, we add k times
            b.a.insert(b.a.begin(), '0'); // multiplied by 10
        }
        return c.normalize(sign * b.sign);
    }
    Bigint operator/(Bigint b) { // division operator overloading
        if (b.size() == 1 && b.a[0] == '0') b.a[0] /= (b.a[0] - 48);
        Bigint c("0"), d;
        for (int j = 0; j < a.size(); j++)
            d.a += "0";
        int dSign = sign * b.sign;
        b.sign = 1;
        for (int i = a.size() - 1; i >= 0; i--) {
            c.a.insert(c.a.begin(), '0');
            c = c + a.substr(i, 1);
            while (!(c < b))
                c = c - b, d.a[i]++;
        }
        return d.normalize(dSign);
    }
    Bigint operator%(Bigint b) { // modulo operator overloading
        if (b.size() == 1 && b.a[0] == '0') b.a[0] /= (b.a[0] - 48);
        Bigint c("0");
        b.sign = 1;
        for (int i = a.size() - 1; i >= 0; i--) {
            c.a.insert(c.a.begin(), '0');
            c = c + a.substr(i, 1);
            while (!(c < b))
                c = c - b;
        }
        return c.normalize(sign);
    }
    std::string to_str() const {
        std::string s;
        if (sign == -1) s += '-';
        for (int i = a.size() - 1; i >= 0; i--)
            s += a[i];
        return s;
    }
    bool operator>(const Bigint &b) const { return b < *this; }
    bool operator<=(const Bigint &b) const { return !(b < *this); }
    bool operator>=(const Bigint &b) const { return !(*this < b); }
    bool operator!=(const Bigint &b) const { return !(*this == b); }
};

这个实现使用string来实现大整数，于是缺点就非常明显了，就是性能低下，求个2000阶乘用时0.7秒，2000位的除法平均用时0.2秒（在mingw下开O2），但对于商全是9的情况下用时0.5秒。不过，这代码里有不少写法是牺牲性能换代码长度，有的思路确实也不错。在同样代码长度级别下，我实现的BigIntTiny有着好得多的性能（2000阶乘用时0.03秒，2000位的除法0.02秒）。

一份70行不到的大整数实现

改编自wu-kan以及hqztrue的基于bitset实现的定长大整数（对定长长度除以3.322就可得到对应的最大10进制位数），支持10进制输入输出，四则运算及位运算均支持。

#include <algorithm>
#include <bitset>
#include <string>

#define BINT_MAXSIZE (1<<15)
typedef typename std::bitset<BINT_MAXSIZE> Bint;
bool operator<(const Bint &a, const Bint &b) {
    for (int i = a.size() - 1; i >= 0; --i)
        if (a[i] != b[i]) return a[i] < b[i];
    return false;
}
bool operator>(const Bint &a, const Bint &b) { return b < a; }
bool operator<=(const Bint &a, const Bint &b) { return !(b < a); }
bool operator>=(const Bint &a, const Bint &b) { return !(a < b); }
Bint operator+(Bint a, Bint b) {
    while (b.any()) {
        Bint c = (a & b) << 1;
        a ^= b, b = c;
    }
    return a;
}
Bint operator-(const Bint &a) { return Bint(1) + ~a; }
Bint operator-(Bint a, Bint b) {
    while (b.any()) {
        Bint c = (~a & b) << 1;
        a ^= b, b = c;
    }
    return a;
}
Bint operator*(Bint a, Bint b) {
    if (a < b) return b * a;
    Bint r(0);
    for (; b.any(); b >>= 1, a <<= 1) if (b[0]) r = r + a;
    return r;
}
std::pair<Bint, Bint> divide(Bint a, const Bint &b) {
    Bint c = 0;
    int i = 0;
    while (b << (i + 1) <= a) ++i;
    for (; i >= 0; --i)
        if (a >= (b << i)) a = a - (b << i), c.set(i, 1);
    return std::make_pair(c, a);
}
Bint operator/(const Bint &a, const Bint &b) { return divide(a, b).first; }
Bint operator%(const Bint &a, const Bint &b) { return divide(a, b).second; }
Bint BintFromStr(const char *p) {
    Bint x = 0;
    int sign = 1;
    for (; *p == '-'; ++p) sign = -sign;
    for (; *p >= '0' && *p <= '9'; ++p) x = (x << 3) + (x << 1) + (*p - '0');
    return sign > 0 ? x : -x;
}
Bint BintFromInt(int i) {
    char buf[20];
    sprintf(buf, "%d", i);
    return BintFromStr(buf);
}
std::string BintToStr(Bint x) {
    std::string out = x == 0 ? "0" : "";
    std::vector<Bint> v;
    if (x[x.size() - 1]) out += '-', x = -x;
    for (Bint y = 1; y <= x; y = (y << 3) + (y << 1)) v.push_back(y);
    for (int i = v.size() - 1; i >= 0; --i) {
        int t = 0;
        for (int l = 3; l >= 0; --l)
            if (x >= (v[i] << l)) x = x - (v[i] << l), t += 1 << l;
        out += t + '0';
    }
    return out;
}

这个实现的代码就短到极致了（原始代码更短，但为了解决较长长度时的递归溢出只好多写几行），但性能同样也挺糟糕的，而且负数支持不佳（做除法会出错，需要自己转为正数做除法，或者可以自己写个类封装一下来解决这个问题），还有一个缺点是受bitset所限只能定长，但部分运算性能上比上一份略好，例如说设置长度为1<<15，求2000阶乘用时0.4秒，但2000位除法用时0.7秒。但对于长度较短的时候不失为一个简易实现。所以这个适用于临时用用的大整数，对于只有加法和乘法运算时会更优于前一个。

其它的Github库实现

以下是我在Github找到的平均性能表现较好的一些小型实现，已经按平均性能进行排序（优先按1万位以内的乘法和除法运算性能进行排序~~，才没有打广告~~）

还有一个只能在x64平台且只能用支持AT&T内联汇编编译器(如GCC/clang)的实现 calebsander/bigint，它的加减法和小规模乘法速度确实飞快，比前面列举到的都快，但受编译环境限制较大。

备注

以上两份代码于2021/06/22有修改，优化了乘法效率，解决递归溢出，同时更新测试结果。

大整数高精度

抱抱熊

一个喜欢折腾和研究算法的大学生

大整数高精度计算——有趣的实现

small biginteger library for contest

一份70行不到的大整数实现

其它的Github库实现

备注

抱抱熊

Related