高精度模板 | Trudbot's Blog

最近发现了一个很有意思的网站：codewars，上面有很多有趣的'kata'，通过kata可以提升你的段位。

codewars上的题目和传统的竞赛题目的风格不太一样，而且用户是可以创建kata的，这一点我觉得很有意思。

在codewars中老是遇到高精度的题目(高精度在普通OJ中基本只有模板题)，每次都要手写及处理细节十分的腻，于是决定把高精度好好的写一遍记录下来，供未来copy。

高模板模板类

包含：

高精度加高精度
高精度减高精度
高精度乘低精度
高精度乘高精度
高精度除以低精度
高精度除以高精度

cpp

namespace BigNumber {
    static string reversed(string &s) {//反转字符串并返回
        reverse(s.begin(), s.end());
        return s;
    }

    static bool comp(string a, string b) {//判断a大于等于b
        if (a.size() != b.size()) return a.size() > b.size();
        return a > b || a == b;
    }

    static string add(string a, string b) {//高精度加高精度
        string ans;
        int i = a.size() - 1, j = b.size() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry) {
            if (i >= 0) carry += a[i--] - '0';
            if (j >= 0) carry += b[j--] - '0';
            ans.push_back(carry % 10 + '0');
            carry /= 10;
        }
        return reversed(ans);
    }

    static string subtract(string a, string b) {//高精度减高精度
        if (!comp(a, b)) return "-" + subtract(b, a);
        string ans;
        int n = a.size(), m = b.size(), carry = 0;
        for (int i = n - 1, j = m - 1; i >= 0; i--, j--) {
            carry += a[i] - '0';
            if (j >= 0) carry -= b[j] - '0';
            if (carry < 0) ans.push_back(carry + 10 + '0'), carry = -1;
            else ans.push_back(carry + '0'), carry = 0;
        }
        while (ans.size() > 1 && ans.back() == '0') ans.pop_back();
        return reversed(ans); 
    }

    
    template<typename T>
    static string multiply(string s, T b) {//高精度乘以低精度
        if (b == 0) return "0";
        reversed(s);
        string ans;
        for (T i = 0, carry = 0; i < s.size() || carry; i++) {
            if (i < s.size()) carry += (s[i] - '0') * b;
            ans.push_back(carry % 10 + '0');
            carry /= 10;
        }
        return reversed(ans);
    }

    static string multiply(string a, string b) {//高精度乘以高精度
        reversed(a), reversed(b);
        vector<int> ans(a.size() + b.size(), 0);
        for (int i = 0; i < a.size(); i ++) 
            for (int j = 0; j < b.size(); j ++)
                ans[i + j] += (a[i] - '0')  *(b[j] - '0');
        int carry = 0; string res;
        for (int i = 0; i < ans.size(); i ++) {
            ans[i] += carry, carry = ans[i] / 10, ans[i] %= 10;
            res.push_back(ans[i] + '0');
        }
        while(res.back() == '0' && res.size() > 1) res.pop_back();
        return reversed(res);
    }
    
    template<typename T>
    static pair<string, T> divide(string a, T b) {//高精度除以低精度
        if (b == 0) return {"ERROR", 0};
        T r = 0;
        string ans;
        for (int i = 0; i < a.size(); i ++) {
            r = r * 10 + a[i] - '0';
            ans.push_back(r / b + '0'), r %= b;
        }
        reversed(ans);
        while(ans.size() > 1 && ans.back() == '0') ans.pop_back();
        return {reversed(ans), r};
    }

    static pair<string, string> divide(string a, string b) {//高精度除以高精度， 复杂度较高
        if (b == "0") return {"ERROR", "ERROR"};
        if (!comp(a, b)) return {"0", a};
        int t = a.size() - b.size();
        string ans;
        for (int i = 0; i < t; i ++) b.push_back('0');
        while (t >= 0) {
            int cnt = 0;
            while(comp(a, b)) a = subtract(a, b), cnt++;
            ans.push_back(cnt + '0');
            b.pop_back();
            t--;
        }
        reversed(ans);
        if (ans.back() == '0') ans.pop_back();
        return {reversed(ans), a};
    }
}

实例 codewars 2kyu--Challenge Fun #10: Integer Square Root

Task
For each given a number N, the integer S is called integer square root of N if S x S <= N and (S+1) x (S+1) > N.
In other words, S = Math.floor(Math.sqrt(N))
Your task is to calculate the integer square root of a given Number.
Note: Input is given in string format. That is, the Number may be very very large 😉
Example
For: Number = "4", result = "2".
For: Number = "17", result = "4".
For: Number = "101", result = "10".
For: Number = "23232328323215435345345345343458098856756556809400840980980980980809092343243243243243098799634", result = "152421548093487868711992623730429930751178496967".
Input/Output
[input] string Number
number in decimal form.
0 < Number < 10^100^
[output] a string
integer squareroot of Number.

显然是一道高精度二分，调用模板完成即可。

cpp

using namespace BigNumber;
string integer_square_root(string n) {
  string l = "0", r = n;
  while (!comp(l, r)) {
    auto [mid, rem] = divide(add(add(l, r), "1"), 2);
    if (comp(n, multiply(mid, mid))) l = mid;
    else r = subtract(mid, "1");
  }
  return l;
}

C++大数类模板

我们可以模仿java的BigInteger类，写一个c++类来模拟正常的整数的各种运算。

由于c++的重载运算符功能，我们可以做到和原生几乎没有使用区别。

以下是尝试性的实现。

c++

//
// Created by trudbot on 2023/1/19.
//

#include "iostream"
#include "string"
#include "algorithm"
#include "map"

class BigInteger {
public:
    BigInteger() {}

    BigInteger(long long num) {
        if (num < 0) {
            this->data = std::to_string(num).substr(1);
            this->sign = -1;
        } else {
            this->data = std::to_string(num);
            this->sign = 1;
        }
    }

    BigInteger(std::string num) {
        if (num[0] == '-') {
            this->data = num.substr(1);
            sign = -1;
        } else {
            this->data = num;
            sign = 1;
        }
    }

    BigInteger(const std::string& num, int sign) {
        this->data = num, this->sign = sign;
    }

    BigInteger operator+(const BigInteger& b) const {
        BigInteger ans;
        if (this->sign == 1 && b.sign == 1) {
            ans = BigInteger(add(this->data, b.data), 1);
        } else if (this->sign == 1 && b.sign == -1) {
            ans = BigInteger(subtract(this->data, b.data));
        } else if (this->sign == -1 && b.sign == 1) {
            ans = BigInteger(subtract(b.data, this->data));
        } else {
            ans = BigInteger(add(this->data, b.data), -1);
        }
        return ans;
    }

    BigInteger operator+(long long & b) const {
        return this->operator+(BigInteger(b));
    }

    BigInteger operator-(const BigInteger &b) const {
        BigInteger ans;
        if (this->sign == 1 && b.sign == 1) {
            ans = BigInteger(subtract(this->data, b.data));
        } else if (this->sign == 1 && b.sign == -1) {
            ans = BigInteger(add(this->data, b.data));
        } else if (this->sign == -1 && b.sign == 1) {
            ans = BigInteger(add(this->data, b.data), -1);
        } else {
            ans = BigInteger(subtract(b.data, this->data));
        }
        return ans;
    }

    BigInteger operator*(const BigInteger &b) {
        return BigInteger(multiply(this->data, b.data), this->sign * b.sign);
    }

    BigInteger operator/(const BigInteger &b) {
        if (lessEqual(b.data, limit)) {
            return BigInteger(divide(this->data, std::stoll(b.data)).first, this->sign * b.sign);
        }
        return BigInteger(divide(this->data, b.data).first, this->sign * b.sign);
    }

    BigInteger operator%(const BigInteger &b) const {
        return BigInteger(divide(this->data, b.data).second);
    }

    void operator*=(const BigInteger &b) {
        this->sign *= b.sign;
        this->data = multiply(this->data, b.data);
    }

    void operator/=(const BigInteger &b) {
        this->sign *= b.sign;
        if (lessEqual(b.data, limit)) {
            this->data = divide(this->data, std::stoll(b.data)).first;
        } else {
            this->data = divide(this->data, b.data).first;
        }
    }

    void operator++() {
        *this = *this + 1;
    }

    void operator--() {
        *this = *this - 1;
    }

    BigInteger& operator=(const BigInteger& b) {
        this->data = b.data, this->sign = b.sign;
        return *this;
    }

    template<typename T>
    BigInteger& operator=(const T& b) {
        *this = BigInteger(b);
        return *this;
    }

    bool operator==(const BigInteger &b) {
        return this->sign == b.sign && this->data == b.data;
    }

    bool operator<(const BigInteger &b) {
        if (this->sign == 1 && b.sign == -1) {
            return true;
        } else if (this->sign == -1 && b.sign == 1) {
            return true;
        } else if (this->sign == 1 && b.sign == 1) {
            return less(this->data, b.data);
        } else {
            return greater(this->data, b.data);
        }
    }

    bool operator>(const BigInteger &b) {
        if (this->sign == 1 && b.sign == -1) {
            return true;
        } else if (this->sign == -1 && b.sign == 1) {
            return false;
        } else if (this->sign == 1 && b.sign == 1) {
            return greater(this->data, b.data);
        } else {
            return less(this->data, b.data);
        }
    }

    bool operator<=(const BigInteger &b) {
        if (this->sign == 1 && b.sign == -1) {
            return false;
        } else if (this->sign == -1 && b.sign == 1) {
            return true;
        } else if (this->sign == 1 && b.sign == 1) {
            return lessEqual(this->data, b.data);
        } else {
            return greaterEqual(this->data, b.data);
        }
    }

    bool operator>=(const BigInteger &b) {
        if (this->sign == 1 && b.sign == -1) {
            return true;
        } else if (this->sign == -1 && b.sign == 1) {
            return false;
        } else if (this->sign == 1 && b.sign == 1) {
            return greaterEqual(this->data, b.data);
        } else {
            return lessEqual(this->data, b.data);
        }
    }

    bool operator!=(const BigInteger &b) {
        return this->sign != b.sign || this->data != b.data;
    }

    friend std::ostream &operator<<(std::ostream &output, const BigInteger &integer) {
        if (integer.sign == -1 && integer.data != "0") {
            output << "-" << integer.data;
        } else {
            output << integer.data;
        }
        return output;
    }

    friend std::istream &operator>>(std::istream  &input, BigInteger &integer) {
        std::string s;
        input >> s;
        integer = BigInteger(s);
        return input;
    }

    BigInteger pow(long long n) {
        BigInteger res = 1, a = *this;
        while (n) {
            if (n & 1) res = res * a;
            a = a * a;
            n >>= 1;
        }
        return res;
    }

    std::string value() {
        return this->data;
    }

private:
    std::string data;
    int sign = 0;
    const std::string limit = "9223372036854775807";

    static std::string reversed(std::string &s) {//反转字符串并返回
        std::reverse(s.begin(), s.end());
        return s;
    }

    static bool greaterEqual(const std::string& a, const std::string& b) {//判断a大于等于b
        return greater(a, b) || a == b;
    }

    static bool less(const std::string& a, const std::string& b) {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b;
    }

    static bool greater(const std::string& a, const std::string& b) {
        if (a.size() != b.size()) return a.size() > b.size();
        return a > b;
    }

    static bool lessEqual(const std::string& a, const std::string& b) {
        return less(a, b) || a == b;
    }

    static std::string add(std::string a, std::string b) {//高精度加高精度
        std::string ans;
        int i = (int)a.size() - 1, j = (int)b.size() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry) {
            if (i >= 0) carry += a[i--] - '0';
            if (j >= 0) carry += b[j--] - '0';
            ans.push_back(carry % 10 + '0');
            carry /= 10;
        }
        return reversed(ans);
    }

    static std::string subtract(std::string a, std::string b) {//高精度减高精度
        if (!greaterEqual(a, b)) return "-" + subtract(b, a);
        std::string ans;
        int n = a.size(), m = b.size(), carry = 0;
        for (int i = n - 1, j = m - 1; i >= 0; i--, j--) {
            carry += a[i] - '0';
            if (j >= 0) carry -= b[j] - '0';
            if (carry < 0) ans.push_back(carry + 10 + '0'), carry = -1;
            else ans.push_back(carry + '0'), carry = 0;
        }
        while (ans.size() > 1 && ans.back() == '0') ans.pop_back();
        return reversed(ans);
    }

    static std::string multiply(std::string s, long long b) {//高精度乘以低精度
        if (b == 0) return "0";
        reversed(s);
        std::string ans;
        for (size_t i = 0, carry = 0; i < s.size() || carry; i++) {
            if (i < s.size()) carry += (s[i] - '0') * b;
            ans.push_back(carry % 10 + '0');
            carry /= 10;
        }
        return reversed(ans);
    }

    static std::string multiply(std::string a, std::string b) {//高精度乘以高精度
        reversed(a), reversed(b);
        int n = a.size() + b.size(), ans[n];
        for (int i = 0; i < n; i ++) ans[i] = 0;
        for (int i = 0; i < a.size(); i ++)
            for (int j = 0; j < b.size(); j ++)
                ans[i + j] += (a[i] - '0')  *(b[j] - '0');
        int carry = 0; std::string res;
        for (int i = 0; i < n; i ++) {
            ans[i] += carry, carry = ans[i] / 10, ans[i] %= 10;
            res.push_back(ans[i] + '0');
        }
        while(res.back() == '0' && res.size() > 1) res.pop_back();
        return reversed(res);
    }

    static std::pair<std::string, long long> divide(const std::string& a, long long b) {//高精度除以低精度
        if (b == 0) return {"ERROR", 0};
        long long r = 0;
        std::string ans;
        for (char i : a) {
            r = r * 10 + i - '0';
            ans.push_back(r / b + '0'), r %= b;
        }
        reversed(ans);
        while(ans.size() > 1 && ans.back() == '0') ans.pop_back();
        return {reversed(ans), r};
    }

    static std::pair<std::string, std::string> divide(std::string a, std::string b) {//高精度除以高精度， 复杂度较高
        if (b == "0") return {"ERROR", "ERROR"};
        if (less(a, b)) return {"0", a};
        int t = a.size() - b.size();
        std::string ans;
        for (int i = 0; i < t; i ++) b.push_back('0');
        while (t >= 0) {
            int cnt = 0;
            while(greaterEqual(a, b)) a = subtract(a, b), cnt++;
            ans.push_back(cnt + '0');
            b.pop_back();
            t--;
        }
        reversed(ans);
        if (ans.back() == '0') ans.pop_back();
        return {reversed(ans), a};
    }
};

用此模板，上面那题的代码可改成

c++

using namespace std;
using Int = BigInteger;

string integer_square_root(string args) {
  Int n = Int(args);
  Int l = 0, r = n;
  while (l < r) {
    Int mid = (l + r + 1) / 2;
    if (mid * mid <= n) l = mid;
    else r = mid - 1;
  }
  return l.value();
}

高模板模板类 ​

实例 codewars 2kyu--Challenge Fun #10: Integer Square Root ​

Task ​

Example ​

Input/Output ​

C++大数类模板 ​

高模板模板类

实例 codewars 2kyu--Challenge Fun #10: Integer Square Root

Task

Example

Input/Output

C++大数类模板