多倍長整数

math/bigint.hpp · GitHub で見る

共通ページ

符号付きの任意精度整数です。四則演算・剰余・比較と、10 進文字列との相互変換を扱います。

#include "lib/math/bigint.hpp"
#include <cassert>

BigInt a("123456789012345678901234567890");
BigInt b = -7;
auto [q, r] = divmod(a, b);
assert(q.to_string() == "-17636684144620811271604938270");
assert(r == 0);
assert(q * b + r == a);

BigInt x = -17;
assert(x / 5 == -3);
assert(x % 5 == -2);
assert(abs(x) == 17);
assert(BigInt("+0000").sign() == 0);
assert((a + 10).to_string() == "123456789012345678901234567900");

操作	内容・返り値
BigInt()	0 を作る
BigInt(value)	128 bit 以下の組み込み整数から正確に作る。暗黙変換可
BigInt(text)	std::string_view の 10 進整数から作る。明示的な変換
a.to_string()	符号付き 10 進表記の std::string を返す
a.sign()	負・零・正について、それぞれ -1・0・1 を int で返す
bool(a)	a != 0 を返す。bool への変換は明示的
+a, -a, abs(a)	符号を保った値・符号反転した値・絶対値を BigInt で返す
a + b, a - b, a * b	和・差・積を BigInt で返す
a / b, a % b	商・余りを BigInt で返す
divmod(a,b)	商と余りの std::pair<BigInt,BigInt> を返す
a += b, a -= b, a *= b, a /= b, a %= b	左辺を更新し、BigInt& を返す
++a, --a	1 増加・減少し、更新後の BigInt& を返す
a++, a--	1 増加・減少し、更新前の BigInt を返す
a == b, a != b, a < b, a <= b, a > b, a >= b	数値を比較し、bool を返す
a <=> b	std::strong_ordering を返す
out << a, in >> a	10 進表記で入出力し、ストリームの参照を返す

整数からの構築は、符号付き・符号なしの両方に対応します。__int128_t・__uint128_t の最小値・最大値も表せます。a + 1・1 + a のように、組み込み整数と混在させられます。

文字列の形式は、省略可能な先頭の + または - と、それに続く 1 桁以上の 0～9 です。先頭の零は許容し、-0・+000 も 0 として扱います。空文字列、符号だけ、空白、10 進数字以外を含む文字列では std::invalid_argument を送出します。to_string() は正の値に + を付けず、不要な先頭の零も出力しません。

商は零に向かって切り捨てます。余りは零または被除数と同じ符号で、a == (a / b) * b + a % b、abs(a % b) < abs(b) を満たします。零除算では std::domain_error を送出します。商と余りの両方が必要な場合は、除算を共有する divmod(a,b) を使ってください。

複合代入には a += a・a *= a・a /= a なども指定できます。コピーは独立した値を作り、ムーブ後の元の値は 0 になります。自己ムーブ代入は値を保ちます。

ストリーム入力は空白で区切った文字列を 1 個読み、その文字列全体を 10 進整数として解釈します。不正な入力では failbit を立て、代入先の値を保ちます。ストリームの std::hex・std::oct は整数の基数指定として使用しません。

桁数は固定されませんが、NTT を使う内部乗算では、繰り上げ前の係数列の長さが \(2^{24}\) 以下である必要があります。この上限を超える乗算は std::length_error を送出します。除算も内部で乗算を行うため、同じ上限が適用されます。確保できるメモリにも依存します。

参考: Nyaan’s Library の多倍長整数。

内部の基数 \(10^9\) における桁数を \(n,m\)、\(n\ge m\)、長さ \(k\) の乗算時間を \(M(k)\) とします。10 進文字列との変換は文字数に対して線形、加減算・比較は最悪 \(O(n)\) 時間です。小さい乗算は \(O(nm)\)、NTT を使う乗算は \(O((n+m)\log(n+m))\) 時間です。被除数が除数以上の場合、小さい除算は商の桁数を \(q\) として \(O(qm)\)、逆数を使う除算は \(O(\displaystyle\frac{n}{m}M(m))\) 時間です。商の桁数は \(q\le n-m+1\) です。被除数が除数未満なら、除算は余りのコピーを含め \(O(n)\) 時間です。大きな乗算・除算の追加空間は \(O(n+m)\) です。符号と零の判定は \(O(1)\)、コピー・単項演算・絶対値は \(O(n)\) 時間です。

依存ライブラリ

• 多倍長整数の絶対値演算
• NTT（法指定）
• 任意 mod・整数の畳み込み

検証コード

• test/bigint_add.test.cpp
• test/bigint_divide.test.cpp
• test/bigint_multiply.test.cpp

コード

#ifndef BIGINT_HPP
#define BIGINT_HPP

#include "../components/bigint_magnitude.hpp"
#include <algorithm>
#include <charconv>
#include <compare>
#include <cstddef>
#include <cstdint>
#include <ios>
#include <istream>
#include <limits>
#include <ostream>
#include <stdexcept>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>

class [[gnu::warn_unused]] BigInt {
	using Word = bigint_detail::Word;
	using Magnitude = bigint_detail::Magnitude;
	static constexpr Word base = bigint_detail::base;
	Magnitude digits_;
	int sign_ = 0;

	BigInt(Magnitude digits, int sign) : digits_(std::move(digits)), sign_(digits_.empty() ? 0 : sign) {}
	void add_magnitude(const Magnitude &other) { bigint_detail::add(digits_, other); }
	void subtract_magnitude(const Magnitude &other) {
		bigint_detail::subtract(digits_, other);
		if (digits_.empty()) sign_ = 0;
	}
	BigInt &add(const BigInt &other, int factor) {
		int sign = other.sign_ * factor;
		if (!sign) return *this;
		if (!sign_) {
			digits_ = other.digits_;
			sign_ = sign;
		} else if (sign_ == sign) add_magnitude(other.digits_);
		else {
			int order = bigint_detail::compare(digits_, other.digits_);
			if (!order) digits_.clear(), sign_ = 0;
			else if (order > 0) subtract_magnitude(other.digits_);
			else {
				BigInt result(other);
				result.subtract_magnitude(digits_);
				result.sign_ = sign;
				*this = std::move(result);
			}
		}
		return *this;
	}

public:
	BigInt() = default;
	BigInt(const BigInt &) = default;
	BigInt &operator=(const BigInt &) = default;
	BigInt(BigInt &&other) noexcept : digits_(std::move(other.digits_)), sign_(std::exchange(other.sign_, 0)) { other.digits_.clear(); }
	BigInt &operator=(BigInt &&other) noexcept {
		if (this != &other) {
			digits_ = std::move(other.digits_);
			sign_ = std::exchange(other.sign_, 0);
			other.digits_.clear();
		}
		return *this;
	}
	template <class T> requires (std::numeric_limits<T>::is_integer && sizeof(T) <= 16)
	BigInt(T value) {
		using U = std::conditional_t<(sizeof(T) <= 8), std::uint64_t, __uint128_t>;
		U magnitude = U(value);
		if constexpr (std::numeric_limits<T>::is_signed)
			if (value < 0) magnitude = U(0) - magnitude, sign_ = -1;
		while (magnitude) {
			digits_.push_back(Word(magnitude % base));
			magnitude /= base;
		}
		if (!digits_.empty() && !sign_) sign_ = 1;
	}
	explicit BigInt(std::string_view text) {
		if (text.empty()) throw std::invalid_argument("BigInt decimal string");
		std::size_t first = text.front() == '+' || text.front() == '-';
		if (first == text.size()) throw std::invalid_argument("BigInt decimal string");
		bool negative = text.front() == '-';
		while (first < text.size() && text[first] == '0') ++first;
		if (first == text.size()) return;
		digits_.reserve((text.size() - first - 1) / 9 + 1);
		for (std::size_t end = text.size(); end > first;) {
			std::size_t begin = end - first > 9 ? end - 9 : first;
			Word value = 0;
			for (std::size_t i = begin; i < end; ++i) {
				unsigned digit = unsigned(text[i] - '0');
				if (digit > 9) throw std::invalid_argument("BigInt decimal string");
				value = value * 10 + digit;
			}
			digits_.push_back(value);
			end = begin;
		}
		sign_ = negative ? -1 : 1;
	}
	[[nodiscard]] int sign() const { return sign_; }
	[[nodiscard]] explicit operator bool() const { return sign_ != 0; }
	[[nodiscard]] std::string to_string() const {
		if (!sign_) return "0";
		char top[10];
		std::size_t length = std::to_chars(top, top + 10, digits_.back()).ptr - top;
		std::string result((sign_ < 0) + length + 9 * (digits_.size() - 1), '0');
		if (sign_ < 0) result[0] = '-';
		std::copy_n(top, length, result.begin() + (sign_ < 0));
		std::size_t end = result.size();
		for (std::size_t i = 0; i + 1 < digits_.size(); ++i) {
			Word value = digits_[i];
			for (int j = 0; j < 9; ++j) result[--end] = char('0' + value % 10), value /= 10;
		}
		return result;
	}
	[[nodiscard]] BigInt operator+() const { return *this; }
	[[nodiscard]] BigInt operator-() const {
		BigInt result(*this);
		result.sign_ = -result.sign_;
		return result;
	}
	BigInt &operator+=(const BigInt &other) { return add(other, 1); }
	BigInt &operator-=(const BigInt &other) { return add(other, -1); }
	BigInt &operator*=(const BigInt &other) { return *this = *this * other; }
	BigInt &operator/=(const BigInt &other) { return *this = divmod(*this, other).first; }
	BigInt &operator%=(const BigInt &other) { return *this = divmod(*this, other).second; }
	BigInt &operator++() { return *this += 1; }
	BigInt &operator--() { return *this -= 1; }
	BigInt operator++(int) { BigInt old(*this); ++*this; return old; }
	BigInt operator--(int) { BigInt old(*this); --*this; return old; }
	[[nodiscard]] friend BigInt operator+(BigInt a, const BigInt &b) { a += b; return a; }
	[[nodiscard]] friend BigInt operator-(BigInt a, const BigInt &b) { a -= b; return a; }
	[[nodiscard]] friend BigInt operator*(const BigInt &a, const BigInt &b) {
		if (!a || !b) return {};
		return BigInt(bigint_detail::multiply(a.digits_, b.digits_), a.sign_ * b.sign_);
	}
	[[nodiscard]] friend BigInt operator/(const BigInt &a, const BigInt &b) { return divmod(a, b).first; }
	[[nodiscard]] friend BigInt operator%(const BigInt &a, const BigInt &b) { return divmod(a, b).second; }
	[[nodiscard]] friend std::pair<BigInt, BigInt> divmod(const BigInt &a, const BigInt &b) {
		if (!b) throw std::domain_error("BigInt division by zero");
		auto [quotient, remainder] = bigint_detail::divide(a.digits_, b.digits_);
		return {BigInt(std::move(quotient), a.sign_ * b.sign_), BigInt(std::move(remainder), a.sign_)};
	}
	[[nodiscard]] friend BigInt abs(BigInt value) { if (value.sign_ < 0) value.sign_ = 1; return value; }
	[[nodiscard]] friend bool operator==(const BigInt &a, const BigInt &b) { return a.sign_ == b.sign_ && a.digits_ == b.digits_; }
	[[nodiscard]] friend std::strong_ordering operator<=>(const BigInt &a, const BigInt &b) {
		if (a.sign_ != b.sign_) return a.sign_ <=> b.sign_;
		return (a.sign_ * bigint_detail::compare(a.digits_, b.digits_)) <=> 0;
	}
	friend std::ostream &operator<<(std::ostream &out, const BigInt &value) { return out << value.to_string(); }
	friend std::istream &operator>>(std::istream &in, BigInt &value) {
		std::string text;
		if (!(in >> text)) return in;
		try { value = BigInt(text); }
		catch (const std::invalid_argument &) { in.setstate(std::ios::failbit); }
		return in;
	}
};

#endif

Back to top page