Int — 多倍長整数

概要

Int は Python の int や Java の BigInteger に相当する多倍長整数クラスである。 暗号、数論、組合せ論など、C++ の組み込み型 (int, int64_t) では表現できない巨大な整数を扱う分野や、高精度の多倍長浮動小数点数への応用を前提に設計されている。

低水準部分はアセンブリ言語で記述されており、桁数に応じたアルゴリズムの自動切り替えにより、高速性を実現している。

数値は 64 ビットワード可変長配列で表現され、桁数に上限はない（利用可能なメモリのみが制約となる）。

※ 現在の主要プロセッサ (x64, ARM, RISC-V) はすべてリトルエンディアンであるため、calx もリトルエンディアンを採用している。

名前空間は calx。

主な特徴

• 自然な演算子構文: a + b, a * b, a ^ b（べき乗）のように 数式と同じ感覚で書ける。C++20 三方比較 (operator<=>) や std::format にも対応
• NaN / $\pm\infty$ の安全な伝播: ゼロ除算でクラッシュせず NaN を返す。 $\infty + 1 = \infty$、$\infty + (-\infty) = \text{NaN}$ のように double と同様の IEEE 754 風ルールに従う
• 負の値のビット演算: 2 の補数セマンティクスで処理される（Python, Java BigInteger と同じ）

クイックスタート

#include <math/core/mp/Int.hpp>
#include <iostream>

int main() {
    using namespace calx;

    // 100 桁の数でも問題なく扱える
    Int a("12345678901234567890123456789012345678901234567890"
          "12345678901234567890123456789012345678901234567890");
    Int b = a * a;
    std::cout << "a² = " << b << "\n";
    std::cout << "桁数 = " << b.digitCount() << "\n";

    // ゼロ除算は NaN を返す（例外を投げない）
    Int c = a / Int(0);
    std::cout << "a/0 = " << c << "\n";           // NaN
    std::cout << "NaN? " << c.isNaN() << "\n";    // true
}

ヘッダー

#include <math/core/mp/Int.hpp>

リンク: calx_int.lib（CMake ターゲット名: calx_int）

MSVC 直接コンパイル

cl /std:c++latest /EHsc /O2 /MD /utf-8 /I<calx>/include your_code.cpp ^
   /link calx_int.lib /MACHINE:X64

CMake

find_package(calx REQUIRED)
target_link_libraries(your_target PRIVATE calx::calx_int)

コンストラクタ

Int()

デフォルトコンストラクタ。値は $0$ に初期化される。未初期化状態にはならない。

Int()

Int a;
std::cout << a << std::endl;

0

数値コンストラクタ

組み込み整数型からの構築。暗黙の型変換が可能で、Int a = 42; のように自然な記法で初期化できる。

Int(int8_t value)
Int(uint8_t value)
Int(short value)
Int(unsigned short value)
Int(int value)
Int(uint64_t value)
Int(int64_t value)

Int a = 42;
Int b = int64_t(-9223372036854775807);
Int c = uint64_t(18446744073709551615ULL);
std::cout << a << "\n" << b << "\n" << c << std::endl;

42
-9223372036854775807
18446744073709551615

Int(std::string_view, int)

文字列からの構築。explicit 指定。桁数に制限はなく、数万桁の数も構築できる。 先頭の - は負の符号として認識される。空白は許容されない。

explicit Int(std::string_view str, int base = 10)

// 基数を明示的に指定
Int dec("123456789012345678901234567890");
Int hex("DEADBEEF", 16);
Int bin("11111111", 2);
std::cout << dec << "\n" << hex << "\n" << bin << "\n";

// base=0 でプレフィックスから自動判定
Int autoHex("0xDEADBEEF");
Int autoBin("0b11111111");
Int autoOct("0377");
std::cout << autoHex << "\n" << autoBin << "\n" << autoOct << std::endl;

123456789012345678901234567890
3735928559
255
3735928559
255
255

コピー / ムーブ

コピーは値のディープコピーを行う（ワード配列全体を複製）。 ムーブは内部バッファの所有権を移動するため $O(1)$ で完了する。 ムーブ後の移動元はゼロにリセットされる。

Int(const Int& other)
Int(Int&& other) noexcept
Int& operator=(const Int& other)
Int& operator=(Int&& other) noexcept
Int& operator=(int value)

Int a = 100;
Int b = a;            // コピー（b = 100, a = 100）
Int c = std::move(a); // ムーブ（c = 100, a = 0）

特殊値ファクトリ

Int は通常の整数値に加え、NaN (非数) と $\pm\infty$ (無限大) を表現できる。 これは浮動小数点数の IEEE 754 に倣った設計で、ゼロ除算や無効な演算の結果を例外なしで安全に伝播させるためのものである。 一般的な多倍長整数ライブラリ (GMP, Java BigInteger) にはこの機能はない。

すべて static メソッド。

static Int Zero()
static Int One()
static Int NaN()
static Int PositiveInfinity()
static Int NegativeInfinity()
static Int nan()              // NaN() のエイリアス
static Int infinity()         // PositiveInfinity() のエイリアス
static Int negInfinity()      // NegativeInfinity() のエイリアス

Int inf = Int::infinity();
Int nan = Int::NaN();
std::cout << inf << "\n" << nan << "\n";
std::cout << (inf + Int(1)) << "\n";   // ∞ + 1 = ∞
std::cout << (inf + Int::negInfinity()) << std::endl; // ∞ + (−∞) = NaN

Infinity
NaN
Infinity
NaN

NaN / $\pm\infty$ の伝播ルール

特殊値を含む演算の結果は以下のルールで決まる。 NaN の伝播や $\infty$ の吸収則など、基本的な考え方は IEEE 754 浮動小数点に倣っている。

IEEE 754 との相違点

NaN の原因分類 (NumericError)

Int オブジェクトは NaN 状態とともに、なぜ NaN になったかの原因情報を内部に保持している。 getError() メソッドで NumericError 列挙値として取得できる。

Int a = 42;
Int zero;
Int result = a / zero;  // ゼロ除算 → NaN

std::cout << std::boolalpha;
std::cout << result.isNaN() << "\n";  // true
std::cout << (result.getError() == NumericError::DivideByZero) << "\n";  // true

Int inf = Int::infinity();
Int indef = inf - inf;  // ∞ - ∞ → NaN (不定形)
std::cout << (indef.getError() == NumericError::InfiniteIndeterminate) << "\n";  // true

Int propagated = result + Int(1);  // NaN + 1 → NaN (伝播)
std::cout << (propagated.getError() == NumericError::NaNPropagation) << "\n";  // true

true
true
true
true

fromState

内部状態コードを直接指定して特殊な Int を構築する。 通常のアプリケーションコードでは NaN() や infinity() を使えば十分であり、 このメソッドはライブラリ内部や高度なエラーハンドリング向けである。

static Int fromState(NumericState state, NumericError error = NumericError::None)

返り値: 指定した状態を持つ Int。

// ゼロ除算エラー情報付きの NaN を構築
Int result = Int::fromState(NumericState::NaN, NumericError::DivideByZero);
std::cout << result.isNaN() << "\n";  // true

fromRawWords

64 ビットワード配列から直接 Int を構築する。 外部ライブラリとのデータ受け渡しや、バイナリシリアライズからの復元に使用する。

static Int fromRawWords(const std::vector<uint64_t>& words, int sign)
static Int fromRawWords(std::span<const uint64_t> words, int sign)

返り値: 指定ワード列から構築した Int。

// 2⁶⁴ + 1 = 0x10000000000000001 を直接ワードから構築
std::vector<uint64_t> w = {1, 1};  // w[0]=1 (下位), w[1]=1 (上位)
Int n = Int::fromRawWords(w, +1);
std::cout << n.toString(16) << "\n";  // 10000000000000001

状態確認

Int は「正常な整数値」の他に「NaN」「$\pm\infty$」「発散」といった 特殊状態 を持つ。 以下のメソッドで現在の状態を問い合わせることができる。 すべて const メンバ関数で、constexpr 対応。

constexpr bool isZero() const
constexpr bool isOne() const
constexpr bool isPositive() const
constexpr bool isNegative() const
bool isEven() const
bool isOdd() const
constexpr bool isNaN() const
constexpr bool isInfinite() const
constexpr bool isNormal() const
constexpr bool isSpecialState() const
constexpr int getSign() const
constexpr NumericState getState() const
constexpr NumericError getError() const
constexpr bool isDivergent() const
constexpr DivergenceDetail getDivergenceDetail() const

Int a(42);
Int b(-7);
Int z(0);
std::cout << std::boolalpha;
std::cout << a.isPositive() << "\n";  // true
std::cout << b.isNegative() << "\n";  // true
std::cout << z.isZero() << "\n";      // true
std::cout << a.isEven() << "\n";      // true
std::cout << b.isOdd() << "\n";       // true
std::cout << Int::NaN().isNaN() << std::endl; // true

true
true
true
true
true
true

自由関数版も提供:

bool isNormal(const Int& value)
bool isNaN(const Int& value)
bool isInfinite(const Int& value)
bool isPosInfinite(const Int& value)
bool isNegInfinite(const Int& value)
bool isOverflow(const Int& value)
bool isDivergent(const Int& value)
std::string getStateDescription(const Int& value)

型範囲判定

Int を C++ の組み込み整数型に変換する前に、値がその型の表現可能な範囲内にあるかを確認するメソッド。 範囲外の値を変換すると未定義動作になるため、変換前に必ずチェックすること。

constexpr bool fitsByte() const
constexpr bool fitsUByte() const
constexpr bool fitsShort() const
constexpr bool fitsUShort() const
constexpr bool fitsInt() const
constexpr bool fitsUInt() const
constexpr bool fitsInt64() const
constexpr bool fitsUInt64() const

Int small(100);
Int medium(40000);
Int big("99999999999999999999");
std::cout << std::boolalpha;
std::cout << small.fitsByte() << "\n";    // true   (100 ≤ 127)
std::cout << small.fitsUByte() << "\n";   // true   (100 ≤ 255)
std::cout << medium.fitsShort() << "\n";  // false  (40000 > 32767)
std::cout << medium.fitsUShort() << "\n"; // true   (40000 ≤ 65535)
std::cout << small.fitsInt() << "\n";     // true
std::cout << big.fitsInt64() << "\n";     // false
std::cout << big.fitsUInt64() << "\n";    // false

true
true
false
true
true
false
false

算術演算子

Int は C++ の組み込み整数型と同じ演算子構文をサポートする。 いずれかのオペランドが NaN または $\pm\infty$ の場合、前述の伝播ルールに従って結果が決まる。

二項演算子

friend Int operator+(const Int& lhs, const Int& rhs)   // + 右辺値オーバーロード ×3
friend Int operator-(const Int& lhs, const Int& rhs)   // + 右辺値オーバーロード ×3
friend Int operator*(const Int& lhs, const Int& rhs)
friend Int operator/(const Int& lhs, const Int& rhs)   // + 右辺値オーバーロード ×1
friend Int operator%(const Int& lhs, const Int& rhs)   // + 右辺値オーバーロード ×1
friend Int operator^(const Int& lhs, const Int& rhs)

複合代入演算子

Int& operator+=(const Int& other)
Int& operator-=(const Int& other)
Int& operator*=(const Int& other)
Int& operator/=(const Int& other)
Int& operator%=(const Int& other)
Int& operator^=(const Int& other)  // べき乗代入

単項・インクリメント

Int operator-() const     // 単項マイナス
Int operator+() const     // 単項プラス（コピー）
friend Int& operator++(Int& value)       // 前置 ++
friend Int operator++(Int& value, int)   // 後置 ++
friend Int& operator--(Int& value)       // 前置 --
friend Int operator--(Int& value, int)   // 後置 --

Int a("123456789012345678901234567890");
Int b("987654321098765432109876543210");
std::cout << (a + b) << "\n";
std::cout << (a * b) << "\n";
std::cout << (b / a) << "\n";
std::cout << (b % a) << "\n";
std::cout << (Int(2) ^ Int(100)) << std::endl;  // 2¹⁰⁰

1111111110111111111011111111100
121932631137021795226185032733866767003075587200439230
8
9876543210
1267650600228229401496703205376

乗算アルゴリズム

オペランドのワード数に応じて Basecase / Karatsuba / Toom-Cook-3 / Toom-Cook-4 / NTT (Schönhage–Strassen) が自動選択される。自乗 ($a \times a$) は対称性を利用して約 30% 高速である。

除算アルゴリズム

除数のサイズに応じて Schoolbook / Burnikel-Ziegler / Newton 逆数反復が自動選択される。 2 のべき乗除数は右シフトのみで完了する。

特殊な除算 — IntOps

C++ の / と % はゼロ方向への切り捨て (truncation toward zero) を行う。 用途によってはこれとは異なる丸め規則が必要になるため、以下のバリエーションを提供する。

static Int IntOps::divmod(const Int& dividend, const Int& divisor, Int& remainder)
static Int IntOps::floorDiv(const Int& dividend, const Int& divisor)
static Int IntOps::ceilDiv(const Int& dividend, const Int& divisor)
static Int IntOps::divExact(const Int& dividend, const Int& divisor)

Int a(17), b(5);
Int rem;
Int q = IntOps::divmod(a, b, rem);
std::cout << "17 / 5 = " << q << " 余り " << rem << "\n";

// 床除算 (Python 式): 負の除算で差が出る
std::cout << "floorDiv(-7, 3) = " << IntOps::floorDiv(Int(-7), Int(3)) << "\n";
// C++ の -7/3 = -2 だが、floorDiv は -3

// 天井除算
std::cout << "ceilDiv(7, 3) = " << IntOps::ceilDiv(Int(7), Int(3)) << std::endl;

17 / 5 = 3 余り 2
floorDiv(-7, 3) = -3
ceilDiv(7, 3) = 3

比較演算子 (C++20 三方比較)

C++20 の宇宙船演算子 (operator<=>) を実装しており、 <, <=, >, >= が自動導出される。

返り値は std::strong_ordering ではなく std::partial_ordering である。 これは NaN が存在するためで、NaN との比較はどの比較演算子でも false を返す （IEEE 754 の浮動小数点数と同じ挙動）。

friend std::partial_ordering operator<=>(const Int& lhs, const Int& rhs)
friend bool operator==(const Int& lhs, const Int& rhs)

NaN との比較は std::partial_ordering::unordered を返す。 これにより NaN == NaN も false、NaN < x も false となる。

Int a(100), b(200);
std::cout << (a <=> b == std::partial_ordering::less) << "\n";  // true
std::cout << (a == b) << "\n";  // false
std::cout << (a < b) << "\n";   // true
std::cout << (a >= b) << "\n";  // false

ビット演算子

多倍長整数に対するビット単位の演算を行う。 正の値は通常の 2 進表現で処理される。 負の値は 2 の補数の無限ビット列として解釈される（Python, Java BigInteger と同じ規則）。 たとえば $-1$ は ...1111 (全ビット 1) であり、$\sim(-1) = 0$ となる。

friend Int operator&(const Int& lhs, const Int& rhs)       // + 右辺値オーバーロード ×3
friend Int operator|(const Int& lhs, const Int& rhs)       // + 右辺値オーバーロード ×3
friend Int operator~(const Int& value)                     // + 右辺値オーバーロード ×1
friend Int operator<<(const Int& lhs, int shift)           // + 右辺値オーバーロード ×1
friend Int operator>>(const Int& lhs, int shift)           // + 右辺値オーバーロード ×1
Int bitwiseXor(const Int& lhs, const Int& rhs)             // + 右辺値オーバーロード ×3

複合代入版: &=, |=, <<=, >>= も提供。

負の値は 2 の補数セマンティクス で処理される。 これは Python や Java の BigInteger と同じ動作である。

$$\tilde{n} = -(n + 1)$$

Int a(0b1100);
Int b(0b1010);
std::cout << (a & b).toBinaryString() << "\n";  // 1000
std::cout << (a | b).toBinaryString() << "\n";  // 1110
std::cout << bitwiseXor(a, b).toBinaryString() << "\n";  // 110
std::cout << (a << 4).toBinaryString() << "\n";  // 11000000

// 負の値の NOT (2の補数)
Int c(-1);
std::cout << (~c) << std::endl;  // 0  (∵ ~(-1) = 0 in 2's complement)

1000
1110
110
11000000
0

ビット操作

個々のビットの取得・設定やビット長の問い合わせを行う。ビット位置は最下位ビット (LSB) を $0$ とする。

bool getBit(size_t position) const
void setBit(size_t position)
void clearBit(size_t position)
void complementBit(size_t position)
size_t bitLength() const
size_t countLeadingZeros() const
size_t countTrailingZeros() const
size_t scanBit0(size_t startPos = 0) const
size_t scanBit1(size_t startPos = 0) const
static size_t hammingDistance(const Int& a, const Int& b)

自由関数:

std::size_t bitCount(const Int& value)

Int a(255);  // 0b11111111
std::cout << a.bitLength() << "\n";           // 8
std::cout << a.countTrailingZeros() << "\n";  // 0

Int b(256);  // 0b100000000
std::cout << b.countTrailingZeros() << "\n";  // 8
std::cout << Int::hammingDistance(a, b) << std::endl;

8
0
8
9

NaN / $\pm\infty$ に対する挙動

ビット操作メソッドの特殊値に対する挙動は以下のとおり。

数値変換

Int を C++ の組み込み型に変換する。変換先の型の範囲を超える値を変換すると未定義動作になるため、 事前に fitsInt() / fitsInt64() / fitsUInt64() で範囲を確認すること。

int toInt() const
int64_t toInt64() const
uint64_t toUInt64() const
size_t toSizeT() const
double toDouble() const

自由関数版:

int64_t toInt64(const Int& value)
uint64_t toUInt64(const Int& value)
double toDouble(const Int& value)

Int a(42);
int i = a.toInt();
int64_t j = a.toInt64();
double d = a.toDouble();
std::cout << i << " " << j << " " << d << std::endl;

42 42 42

文字列変換

Int を文字列に変換する方法は複数ある。基数 2〜36 を指定できる。 C++20 の std::format にも対応しており、書式指定子でフォーマットを制御できる。

toString

std::string toString(int base = 10) const

返り値: std::string — 指定基数での文字列表現。負の値は先頭に -。

Int a(255);
std::cout << a.toString() << "\n";     // 10進
std::cout << a.toString(16) << "\n";   // 16進
std::cout << a.toString(2) << "\n";    // 2進
std::cout << a.toString(8) << std::endl; // 8進

255
ff
11111111
377

専用文字列メソッド

std::string toHexString(bool uppercase = false) const
std::string toBinaryString() const
std::string toOctalString() const

fromString

static Int fromString(std::string_view str, int base = 10)

返り値: パースされた Int。

Int a = Int::fromString("DEADBEEF", 16);
std::cout << a << std::endl;

3735928559

ストリーム入出力

friend std::ostream& operator<<(std::ostream& os, const Int& value)
friend std::istream& operator>>(std::istream& is, Int& value)

std::format 対応

Int a(255);
std::cout << std::format("{}", a) << "\n";     // 255
std::cout << std::format("{:x}", a) << "\n";   // ff
std::cout << std::format("{:#X}", a) << "\n";  // 0XFF
std::cout << std::format("{:b}", a) << "\n";   // 11111111
std::cout << std::format("{:+d}", a) << std::endl; // +255

255
ff
0XFF
11111111
+255

桁数・対数

数値の大きさを桁数や対数で問い合わせる。sizeInBase は正確な桁数より高速だが、 $+1$ の誤差が生じる場合がある。正確な桁数が必要な場合は digitCount を使用すること。

size_t digitCount(int base = 10) const
size_t sizeInBase(int base = 10) const
size_t ilog2() const
size_t ilog10() const

Int a("123456789012345678901234567890");
std::cout << a.digitCount() << "\n";    // 30
std::cout << a.sizeInBase() << "\n";    // 30 or 31
std::cout << a.ilog2() << "\n";         // 96
std::cout << a.ilog10() << std::endl;   // 29

30
30
96
29

GCD / LCM

最大公約数 (Greatest Common Divisor) と最小公倍数 (Least Common Multiple) の計算。 gcd と lcm は自由関数（calx 名前空間）として提供される。 拡張ユークリッド互除法は IntGCD クラスの static メソッドとして提供される。

gcd

最大公約数を計算する。2 つの整数に共通する最大の約数を返す。

Int gcd(const Int& a, const Int& b)

返り値: Int — $\gcd(a, b) \geq 0$。

アルゴリズム: Binary GCD (Stein)、$O(n^2)$。 詳細

特殊値: $\gcd(0, b) = |b|$、$\gcd(\text{NaN}, x) = \text{NaN}$、$\gcd(\infty, x) = \text{NaN}$

Int a(48), b(36);
std::cout << gcd(a, b) << std::endl;  // 12

12

lcm

最小公倍数を計算する。

Int lcm(const Int& a, const Int& b)

返り値: Int — $\text{lcm}(a, b) \geq 0$。

内部的に $\text{lcm}(a, b) = |a| \times (|b| / \gcd(a, b))$ で計算する（中間オーバーフロー回避）。

Int a(12), b(18);
std::cout << lcm(a, b) << std::endl;  // 36

36

extendedGcd

拡張ユークリッド互除法。GCD に加えて Bézout 係数 $x$, $y$ を求める。 これは暗号学での乗法的逆元の計算や、不定方程式の解法で使われる。

$$ax + by = \gcd(a, b)$$

static Int IntGCD::extendedGcd(const Int& a, const Int& b, Int& x, Int& y)

返り値: Int — $\gcd(a, b)$。

Int a(35), b(15), x, y;
Int g = IntGCD::extendedGcd(a, b, x, y);
std::cout << "gcd = " << g << "\n";
std::cout << "x = " << x << ", y = " << y << "\n";
std::cout << "check: " << (a * x + b * y) << std::endl;

gcd = 5
x = 1, y = -2
check: 5

冪乗

整数の冪乗と冪剰余を計算する。いずれも繰り返し二乗法 (binary exponentiation) により、 指数 $e$ の大きさに対して $O(\log e)$ 回の乗算で計算を完了する。

pow

冪乗を計算する。結果は急速に巨大になるため、大きな指数では powMod（冪剰余）の使用を検討すること。

$$\text{pow}(a, n) = a^n$$

Int pow(const Int& base, unsigned int exponent)
Int pow(const Int& base, const Int& exponent)

返り値: Int — $\text{base}^{\text{exponent}}$。

アルゴリズム: 繰り返し二乗法、$O(\log e \times M(n))$。 詳細

Int a(2);
std::cout << pow(a, 100u) << std::endl;

1267650600228229401496703205376

powMod

冪剰余（modular exponentiation）。

$$\text{powMod}(a, e, m) = a^e \bmod m$$

Int powMod(const Int& base, const Int& exponent, const Int& modulus)

返り値: Int — $a^e \bmod m$、範囲 $[0, |m|)$。

アルゴリズム: 繰り返し二乗法 (right-to-left)、各ステップで $\bmod m$ を取る。 詳細

負の指数: $\text{powMod}(a, -n, m) = \text{inverseMod}(a^n, m)$

Int base(2), exp(100), mod(1000000007);
std::cout << powMod(base, exp, mod) << std::endl;

976371285

IntOps::pow2

$2$ のべき乗の高速生成。

static Int IntOps::pow2(uint64_t exponent)

返り値: Int — $2^n$。ビットセットのみで構築するため乗算より大幅に高速である。

モジュラ演算

整数の剰余演算と乗法的逆元を求める。IntModular クラスの static メソッドとして提供される。 より高度なモジュラ演算（テンプレートベースの ModularInt<P> クラス）は modular.html を参照。

IntModular::mod

正規化剰余。C++ の % 演算子と異なり、常に非負の結果 $0 \leq r < |m|$ を返す。

static Int IntModular::mod(const Int& x, const Int& m)

返り値: Int — $x \bmod m$、範囲 $[0, |m|)$。

std::cout << IntModular::mod(Int(-7), Int(5)) << "\n";  // 3 (C++の%は-2)
std::cout << IntModular::mod(Int(7), Int(5)) << std::endl; // 2

3
2

IntModular::inverseMod

乗法的逆元を計算する。$a$ に対して $a \times x \equiv 1 \pmod{m}$ を満たす $x$ を求める。 暗号学（RSA 鍵生成など）や連立合同式の求解で頻繁に使用される。

$$a \times x \equiv 1 \pmod{m}$$

static Int IntModular::inverseMod(const Int& a, const Int& m, bool is_prime = false)

返り値: Int — $a^{-1} \bmod m$。逆元が存在しない場合は $0$。

前提条件: $\gcd(a, m) = 1$（互いに素）。

アルゴリズム: 拡張ユークリッド互除法（is_prime=true なら Fermat の小定理で高速化）。 詳細

std::cout << IntModular::inverseMod(Int(3), Int(7)) << "\n";   // 5  (3×5=15≡1 mod 7)
std::cout << IntModular::inverseMod(Int(2), Int(5)) << std::endl; // 3  (2×3=6≡1 mod 5)

5
3

素数判定

大きな整数が素数であるかを判定する。多倍長整数に対する確定的な素数判定は計算コストが非常に高いため、 確率的アルゴリズム (Miller-Rabin) を使用する。 「素数である」と判定された場合にわずかな誤判定の確率があるが、その確率は任意に小さくできる。

isProbablePrime

確率的素数判定。多くの用途ではこの自由関数を使えば十分である。

bool isProbablePrime(const Int& value, int iterations = 25)

返り値: bool — 素数なら true（確率的）。

アルゴリズム: Miller-Rabin 確率的素数判定法。 誤判定確率 $\leq 4^{-k}$（デフォルト $k = 25$ で $\leq 2^{-50}$）。 詳細

Int mersenne = pow(Int(2), 127u) - Int(1);
std::cout << mersenne << "\n";
std::cout << std::boolalpha << isProbablePrime(mersenne) << std::endl;

170141183460469231731687303715884105727
true

IntPrime クラス

素数関連のユーティリティを集めた static メソッド群。 判定アルゴリズムの直接呼び出しや、次の素数・前の素数の探索ができる。

static bool IntPrime::isMillerRabinPrime(const Int& n, int k = 20)
static bool IntPrime::isFermatPrime(const Int& n, int k = 5)
static bool IntPrime::isProbablePrime(const Int& n, int k = 20)
static Int IntPrime::nextPrime(const Int& n, int k = 20)
static Int IntPrime::prevPrime(const Int& n, int k = 20)

std::cout << IntPrime::nextPrime(Int(100)) << std::endl;  // 101
std::cout << IntPrime::prevPrime(Int(100)) << std::endl;   // 97

101
97

組合せ論

階乗、二重階乗、二項係数を計算する。IntCombinatorics クラスの static メソッドとして提供される。 大きな $n$ では結果が数千〜数万桁になるが、多倍長整数なので問題なく扱える。

factorial

階乗 $n!$ を計算する。$n$ のサイズに応じて最適なアルゴリズムを自動選択する。

static Int IntCombinatorics::factorial(const Int& n)

返り値: Int — $n! = 1 \times 2 \times \cdots \times n$。

アルゴリズム: $n$ の大きさに応じてテーブル参照 / 単純ループ / 篩法＋トーナメント乗算を自動選択。 詳細

std::cout << IntCombinatorics::factorial(Int(20)) << "\n";
std::cout << IntCombinatorics::factorial(Int(100)) << std::endl;

2432902008176640000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

doubleFactorial

二重階乗 $n!!$ を計算する。

static Int IntCombinatorics::doubleFactorial(const Int& n)

返り値: Int

$$n!! = \begin{cases} n \times (n-2) \times \cdots \times 4 \times 2 & (n \text{ が偶数}) \\ n \times (n-2) \times \cdots \times 3 \times 1 & (n \text{ が奇数}) \end{cases}$$

std::cout << IntCombinatorics::doubleFactorial(Int(6)) << "\n";   // 6×4×2 = 48
std::cout << IntCombinatorics::doubleFactorial(Int(7)) << std::endl; // 7×5×3×1 = 105

48
105

binomial

二項係数を計算する。

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

static Int IntCombinatorics::binomial(const Int& n, const Int& k)

返り値: Int — $\binom{n}{k}$。

対称性 $\binom{n}{k} = \binom{n}{n-k}$ を利用して $k > n/2$ のとき計算量を削減する。

std::cout << IntCombinatorics::binomial(Int(10), Int(3)) << "\n";
std::cout << IntCombinatorics::binomial(Int(100), Int(50)) << std::endl;

120
100891344545564193334812497256

平方根・$n$ 乗根

整数の平方根や $n$ 乗根を計算する。結果は常に整数部分（切り捨て）を返す。 余りが必要な場合は sqrtRem / nthRootRem を使用する。 すべて IntSqrt クラスの static メソッドとして提供される。

IntSqrt::sqrt

整数平方根 $\lfloor \sqrt{n} \rfloor$ を計算する。入力サイズに応じて最適なアルゴリズムが選択される。

$$\lfloor \sqrt{n} \rfloor$$

static Int IntSqrt::sqrt(const Int& value)

返り値: Int — $\lfloor \sqrt{\text{value}} \rfloor$。

アルゴリズム: 入力サイズに応じて double 精度 / Babylonian 法 / Karatsuba 平方根 (Zimmermann) を自動選択、$O(M(n))$。 詳細

std::cout << IntSqrt::sqrt(Int(1000000)) << "\n";  // 1000
std::cout << IntSqrt::sqrt(Int(2)) << std::endl;    // 1

1000
1

IntSqrt::sqrtRem

平方根と余りを同時に返す。

$$\text{value} = s^2 + r \quad (0 \leq r \leq 2s)$$

static Int IntSqrt::sqrtRem(const Int& value, Int& remainder)

返り値: Int — 平方根 $s = \lfloor \sqrt{\text{value}} \rfloor$。

Int rem;
Int s = IntSqrt::sqrtRem(Int(50), rem);
std::cout << "sqrt = " << s << ", rem = " << rem << std::endl;
// 50 = 7² + 1

sqrt = 7, rem = 1

IntSqrt::isSquare

完全平方数判定。

static bool IntSqrt::isSquare(const Int& value, Int* pSqrt = nullptr)

返り値: bool — 完全平方数なら true。

最適化: モジュラフィルタリングで非平方数を高速除外。 詳細

Int s;
std::cout << std::boolalpha;
std::cout << IntSqrt::isSquare(Int(144), &s) << " sqrt=" << s << "\n";
std::cout << IntSqrt::isSquare(Int(145)) << std::endl;

true sqrt=12
false

IntSqrt::nthRoot

$n$ 乗根の整数部分を計算する。

$$\lfloor \sqrt[n]{\text{value}} \rfloor$$

static Int IntSqrt::nthRoot(const Int& value, unsigned int n)

返り値: Int — $\lfloor \text{value}^{1/n} \rfloor$。

アルゴリズム: Newton 法 + 精度倍増、$O(M(n) \times \log n)$。 詳細

std::cout << IntSqrt::nthRoot(Int(1000000), 3) << std::endl;  // 100 (∛1000000)

100

IntSqrt::nthRootRem

$n$ 乗根と余りを同時に返す。

static Int IntSqrt::nthRootRem(const Int& value, unsigned int n, Int& remainder)

返り値: Int — $s = \lfloor \text{value}^{1/n} \rfloor$。

Int rem;
Int r = IntSqrt::nthRootRem(Int(1000), 3, rem);
std::cout << "root = " << r << ", rem = " << rem << std::endl;
// 1000 = 10³ + 0

root = 10, rem = 0

その他のユーティリティ

絶対値、因子除去、整除性判定、合同判定、内部表現へのアクセスなど。

abs

絶対値を返す。自由関数として提供される。

Int abs(const Int& value)
Int abs(Int&& value)        // 右辺値オーバーロード

右辺値版は符号の反転のみでバッファをそのまま返す。

返り値: Int — $|value|$。

std::cout << abs(Int(-42)) << std::endl;  // 42

42

removeFactor

値を指定した因子で割れるだけ割り、「割り切れなくなった商」と「何回割れたか」のペアを返す。

たとえば $72$ から因子 $2$ を除去する場合:

$$72 \div 2 = 36, \quad 36 \div 2 = 18, \quad 18 \div 2 = 9 \quad (\text{9 は 2 で割り切れない})$$

$2$ で 3 回割れて、商は 9 になった。 すなわち $72 = 9 \times 2^3$ である。この関数は {9, 3} を返す。

整数論では「$n$ が素数 $p$ で何回割り切れるか」を $v_p(n)$（$p$-adic valuation）と呼ぶ。 上の例では $v_2(72) = 3$ である。

std::pair<Int, uint64_t> removeFactor(const Int& value, const Int& factor)

返り値: std::pair<Int, uint64_t>

• 第 1 要素 (Int): 因子を除去しきった後の商 — 上の例では $9$
• 第 2 要素 (uint64_t): 除去できた回数 — 上の例では $3$

これらは以下の関係を満たす:

$$\text{value} = \text{商} \times \text{factor}^{\text{回数}}$$

auto [quotient, count] = removeFactor(Int(72), Int(2));
std::cout << "72 = " << quotient << " × 2^" << count << std::endl;
// → 72 = 9 × 2^3

auto [q2, c2] = removeFactor(Int(1000), Int(10));
std::cout << "1000 = " << q2 << " × 10^" << c2 << std::endl;
// → 1000 = 1 × 10^3

72 = 9 × 2^3
1000 = 1 × 10^3

isDivisible

割り切れるかを判定する。

bool isDivisible(const Int& divisor) const

返り値: bool — *this が divisor で割り切れれば true。

std::cout << std::boolalpha;
std::cout << Int(12).isDivisible(Int(3)) << std::endl;  // true
std::cout << Int(13).isDivisible(Int(3)) << std::endl;  // false

true
false

isCongruent

2 つの値が指定した法のもとで合同かどうかを判定する。 内部的に差の剰余がゼロかを確認する。

$$\text{this} \equiv \text{other} \pmod{\text{modulus}}$$

bool isCongruent(const Int& other, const Int& modulus) const

返り値: bool — 合同なら true。

std::cout << std::boolalpha;
std::cout << Int(17).isCongruent(Int(2), Int(5)) << std::endl;  // true (17 ≡ 2 mod 5)

true

swap

void swap(Int& other) noexcept              // メンバ関数版
friend void swap(Int& a, Int& b) noexcept   // 自由関数版

2 つの Int を $O(1)$ で交換する。

Int a(10), b(20);
swap(a, b);
std::cout << a << " " << b << std::endl;  // 20 10

20 10

内部アクセス

Int の内部表現（64 ビットワード配列）に直接アクセスする。 デバッグや外部ライブラリとのデータ受け渡しに使用する。 ワードはリトルエンディアン順: word(0) が最下位 64 ビット。

constexpr uint64_t word(size_t index) const
constexpr size_t size() const
std::vector<uint64_t> words() const

使用アルゴリズム

各演算で使用されるアルゴリズムの詳細はそれぞれの解説ページを参照。

• 乗算 — Basecase / Karatsuba / Toom-Cook / NTT の 5 段階自動選択
• 除算 — Schoolbook / Burnikel-Ziegler / Newton 逆数反復
• GCD / 拡張 GCD — Binary GCD (Stein)、拡張ユークリッド互除法
• 冪乗・モジュラ演算 — 繰り返し二乗法、冪剰余、モジュラ逆元
• 素数判定 — 小素数テーブル + Miller-Rabin
• 平方根・$n$ 乗根 — Babylonian / Karatsuba sqrt (Zimmermann) / Newton 法
• 階乗・組合せ — テーブル / 篩法 + トーナメント乗算