# 機能設計書 11-多倍長整数（BigInt）

## 概要

本ドキュメントは、Julia言語における多倍長整数（BigInt）機能の設計を記述する。BigIntはGMP（GNU Multiple Precision Arithmetic Library）ライブラリを基盤とした任意精度整数演算を提供する。

### 本機能の処理概要

BigInt型は、固定長整数型（Int64, Int128等）では表現できない大きな整数値を扱うための任意精度整数型である。GMPライブラリのmpz系関数をccallで直接呼び出すことにより、高速な多倍長整数演算を実現している。

**業務上の目的・背景**：科学技術計算、暗号学、数論研究などの分野では、64ビットや128ビットの固定長整数では桁溢れが発生する超大数を扱う必要がある。BigIntはメモリが許す限り任意の精度で整数演算を可能にし、精度の制約なく正確な計算結果を保証する。また、Int128からのwiden先としてBigIntが設定されており、型昇格チェーンの終端を担う。

**機能の利用シーン**：（1）大きな階乗・二項係数の計算（factorial, binomial）、（2）暗号学的な冪剰余演算（powermod）、（3）任意精度の整数演算が必要な数学的証明・検証、（4）Rational{BigInt}による精密な有理数演算、（5）big"..."文字列リテラルや parse(BigInt, s) によるユーザー入力からの大数生成。

**主要な処理内容**：
1. BigInt型の定義とGMPメモリ管理の統合（Juliaの GC に管理されたメモリ割り当て関数をGMPに設定）
2. 四則演算（+, -, *, div, mod, rem）及びビット演算（&, |, xor, <<, >>）の提供
3. 比較演算（==, <, <=, >, >=）と符号操作（sign, flipsign, signbit）
4. 数論関数（gcd, lcm, gcdx, invmod, powermod, factorial, binomial, isqrt）
5. 型変換（Integer/Float64/String との相互変換、parse/string）
6. ハッシュ計算の最適化（64ビットシステム向けの特殊実装）
7. Rational{BigInt}演算のMPQモジュールによる高速化

**関連システム・外部連携**：GMP（GNU Multiple Precision Arithmetic Library）のlibgmpと直接連携する。メモリ割り当てはjl_gc_counted_malloc/realloc/free経由でJuliaのGCに統合されている。

**権限による制御**：特になし。すべてのユーザーが利用可能。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 2 | Juliaプロンプト（julia>） | 参照画面 | REPL上でBigInt演算を対話的に実行・結果表示 |
| 3 | ヘルプモード（help?>） | 参照画面 | BigInt関連のdocstring表示 |

## 機能種別

計算処理（任意精度整数演算）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| x | Integer / Float64 / String | Yes | BigIntに変換する値 | Float64の場合isinteger(x)が必要。Stringの場合は有効な整数表現であること |
| base | Integer | No | 文字列パース時の基数（デフォルト10） | 2 <= base <= 62 |
| nbits | Integer | No | BigIntコンストラクタでの初期ビット数 | 0以上 |

### 入力データソース

Julia式からの直接入力（リテラル、変数、式の評価結果）。parse(BigInt, s)による文字列パース。big"..."文字列マクロ。widen(Int128)による型昇格。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | BigInt | 演算結果の任意精度整数 |
| string_repr | String | string(n; base=10, pad=1)による文字列表現 |
| float_repr | Float64/Float32/Float16 | 浮動小数点変換結果（丸めモード指定可） |

### 出力先

演算結果はメモリ上のBigIntオブジェクトとして返却。REPL表示時はshow関数を経由してstdoutへ出力。

## 処理フロー

### 処理シーケンス

```
1. BigIntオブジェクト生成
   └─ MPZ.init2!でGMPのmpz構造体を初期化、finalizerに__gmpz_clearを登録
2. 値の設定
   └─ 型に応じてMPZ.set_si/set_ui/set_d/set_str!を呼び出し
3. 演算実行
   └─ ccallでGMPのmpz系関数を呼び出し（例：__gmpz_add, __gmpz_mul）
4. 結果の返却
   └─ 新規BigIntオブジェクトに結果を格納して返却
5. メモリ解放
   └─ GCのfinalizer経由で__gmpz_clearが呼ばれ、GMP内部メモリを解放
```

### フローチャート

```mermaid
flowchart TD
    A[BigInt生成要求] --> B{入力型の判定}
    B -->|Integer Clong範囲内| C[MPZ.set_si/set_ui]
    B -->|Integer 範囲外| D[limb単位で手動設定]
    B -->|Float64| E{isinteger?}
    E -->|Yes| F[MPZ.set_d]
    E -->|No| G[InexactError]
    B -->|String| H[MPZ.set_str!]
    C --> I[BigIntオブジェクト返却]
    D --> I
    F --> I
    H --> I
    I --> J[演算実行: ccall GMP関数]
    J --> K[結果BigInt返却]
    K --> L[GC finalizer登録済み]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 任意精度保証 | BigInt演算はオーバーフローしない（メモリ上限まで） | 全BigInt演算 |
| BR-02 | GCメモリ統合 | GMPのメモリ割り当てはJuliaのGC経由で行う | __init__時に設定 |
| BR-03 | 型昇格ルール | BigIntとIntegerの演算結果はBigInt | promote_rule定義 |
| BR-04 | ゼロ除算 | div/remでゼロ除算時はDivideError | 除数がゼロの場合 |
| BR-05 | 負の階乗 | factorial(n)でn<0の場合DomainError | nが負の場合 |
| BR-06 | GMP互換性検証 | 実行時のGMPバージョンとコンパイル時バージョンの一致を検証 | __init__時 |

### 計算ロジック

- 冪剰余: powermod(x, p, m) は MPZ.powm で計算し、m < 0 の場合は結果にmを加算して符号を調整
- 拡張GCD: gcdx(a, b) は MPZ.gcdext で計算。GMP版差異への対処として a==b 時の結果を補正
- Float64変換: limb数から指数を計算し、上位54ビットを抽出して丸め。ties-to-even方式

## データベース操作仕様

### 操作別データベース影響一覧

該当なし（本機能はデータベースを使用しない）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | InexactError | Float64からの変換時にisinteger(x)がfalse | 整数値のみを変換する |
| - | ArgumentError | parse時の不正な文字列または基数範囲外(2-62) | 有効な整数文字列と基数を指定 |
| - | DomainError | factorial(n)でn < 0 | 非負整数を指定 |
| - | DomainError | invmod(n, m)でm==0またはgcd(n,m)!=1 | 互いに素な値を指定 |
| - | OverflowError | bigint_pow(x, y)でy > typemax(Culong)かつx!=0,1,-1 | 指数を制限する |
| - | OutOfMemoryError | GMP割り当てオーバーフロー（パッチ版GMPのみ） | メモリ使用量を削減 |

### リトライ仕様

該当なし（メモリ不足は再試行不可）

## トランザクション仕様

該当なし（インメモリ計算のみ）

## パフォーマンス要件

- GMPライブラリの高度に最適化されたアセンブリ実装を活用
- add/subではビット数を事前計算して適切なサイズのBigIntを割り当て（再割り当て回避）
- prod(Array{BigInt})では分割統治法で乗算を行い、小さなブロックではlimbサイズを事前計算
- sum(Array{BigInt})ではfoldlによるin-place加算で中間オブジェクト生成を抑制
- 64ビットシステムではhash関数の特殊最適化（UnsafeLimbViewによるイテレータベースアクセス）

## セキュリティ考慮事項

- unsafe_load/unsafe_store!によるポインタ操作はGMPの内部limb配列に限定
- GMP内部メモリはJuliaのGC管理下にあり、二重解放を防止
- ALLOC_OVERFLOW_FUNCTIONにより巨大割り当て時のabortをOutOfMemoryErrorに変換（パッチ版GMP）

## 備考

- BigIntはmutable structだが、Juliaの数値型規約に従い意味的にはimmutableとして扱われる
- Rational{BigInt}の高速演算はMPQサブモジュールで提供（__gmpq_add等を直接呼び出し）
- widen(Int128) = widen(UInt128) = BigInt により、整数型昇格チェーンの終端を担う

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

BigInt型の内部構造とGMPとの対応関係を把握することが出発点となる。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | gmp.jl | `base/gmp.jl` | BigInt構造体の定義（64-74行目）：alloc, size, dの3フィールドがGMPのmpz_struct直接対応 |

**読解のコツ**: BigIntの`size`フィールドは符号付きで、正の値は正の数、負の値は負の数、0はゼロを表す。`d`はlimb配列へのポインタであり、Limb型（UInt32またはUInt64、47-57行目で決定）の配列として格納される。`alloc`は割り当て済みlimb数。

#### Step 2: エントリーポイントを理解する

GMP初期化とBigIntコンストラクタが主要なエントリーポイントである。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | gmp.jl | `base/gmp.jl` | __init__関数（108-139行目）：GMP初期化とメモリ関数設定 |
| 2-2 | gmp.jl | `base/gmp.jl` | BigIntコンストラクタ群（315-346行目）：各入力型からの生成 |

**主要処理フロー**:
1. **108-139行目**: __init__でGMPバージョン検証、メモリ関数をJulia GC関数に差し替え、ZERO/ONE定数を初期化
2. **69-73行目**: 基本コンストラクタ。MPZ.init2!で初期化し、__gmpz_clearのfinalizerを登録
3. **315-316行目**: Clong/Culong範囲のIntegerはMPZ.set_si/set_uiで高速変換
4. **329-346行目**: 範囲外Integerはlimb単位の手動設定（ビット幅計算→realloc2→limb格納）

#### Step 3: MPZモジュール（GMP関数ラッパー）を理解する

MPZモジュールはGMPのmpz系関数のJuliaラッパーを提供する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | gmp.jl | `base/gmp.jl` | MPZモジュール（142-274行目）：ccallベースのGMP関数ラッパー |

**主要処理フロー**:
- **156-157行目**: init!/init2!による初期化
- **164-175行目**: メタプログラミングによる二項演算の一括定義（add, sub, mul, fdiv_q等）
- **182-189行目**: 符号なし整数引数版の二項演算（add_ui, mul_ui, pow_ui等）
- **204-212行目**: 単項演算（neg, com, sqrt, set）
- **227-231行目**: divremの同時計算（tdiv_qr）
- **233-236行目**: 冪剰余（powm）
- **244-250行目**: 比較演算（cmp, cmp_si, cmp_ui, cmp_d）

#### Step 4: 算術演算の定義を理解する

BigInt同士およびBigIntとプリミティブ型の演算定義。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | gmp.jl | `base/gmp.jl` | 二項演算（496-503行目）：+,-,*,mod,rem,gcd,lcm,&,|,xor |
| 4-2 | gmp.jl | `base/gmp.jl` | 効率的な混合型演算（548-563行目）：BigIntとCulongMax/ClongMaxの直接演算 |
| 4-3 | gmp.jl | `base/gmp.jl` | 冪乗とpowermod（637-672行目） |

#### Step 5: 型変換とハッシュを理解する

BigIntと他の数値型の間の変換、および効率的なハッシュ実装。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | gmp.jl | `base/gmp.jl` | Float64変換（407-434行目）：RoundNearest丸めの詳細実装 |
| 5-2 | gmp.jl | `base/gmp.jl` | hash関数（915-953行目）：64ビットシステム向けの最適化 |
| 5-3 | gmp.jl | `base/gmp.jl` | string変換（763-780行目）：MPZ.get_str!による文字列化 |

#### Step 6: MPQモジュール（Rational{BigInt}高速演算）を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 6-1 | gmp.jl | `base/gmp.jl` | MPQモジュール（956-1109行目）：Rational{BigInt}の高速演算 |

### プログラム呼び出し階層図

```
BigInt(x) [コンストラクタ]
    |
    +-- MPZ.init2!(new(), nbits)       [GMP初期化]
    |       +-- ccall(:__gmpz_init2)
    |
    +-- MPZ.set_si(x) / set_ui(x)     [値の設定（小さい整数）]
    |       +-- ccall(:__gmpz_set_si / :__gmpz_set_ui)
    |
    +-- limb単位手動設定               [値の設定（大きい整数）]
    |       +-- MPZ.realloc2(nd)
    |       +-- unsafe_store!(z.d, ux % Limb, size)
    |
    +-- +(x, y) [演算例]
    |       +-- MPZ.add(x, y)
    |               +-- MPZ.add!(BigInt(nbits=...), x, y)
    |                       +-- ccall(:__gmpz_add)
    |
    +-- show(io, x) [表示]
            +-- string(x; base=10)
                    +-- MPZ.get_str!(p, base, n)
                            +-- ccall(:__gmpz_get_str)
```

### データフロー図

```
[入力]                    [処理]                           [出力]

Julia Integer    ──────> BigInt() コンストラクタ ────────> BigInt オブジェクト
Float64          ──────> MPZ.set_d (ccall GMP)
String           ──────> MPZ.set_str! (ccall GMP)

BigInt a, b      ──────> MPZ.add/sub/mul (ccall GMP) ──> BigInt 結果
BigInt x, Int p  ──────> MPZ.powm (ccall GMP) ─────────> BigInt 結果
BigInt n         ──────> MPZ.get_str! (ccall GMP) ─────> String 表現
BigInt n         ──────> Float64(n, RoundNearest) ─────> Float64 近似値
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| gmp.jl | `base/gmp.jl` | ソース | BigInt型定義、GMP.MPZラッパー、算術演算、型変換、MPQモジュール |
| mpfr.jl | `base/mpfr.jl` | ソース | BigFloat定義（BigIntとの相互変換あり） |
| promotion.jl | `base/promotion.jl` | ソース | promote_rule定義の基盤 |
| hashing.jl | `base/hashing.jl` | ソース | hash関数の汎用定義 |
| rational.jl | `base/rational.jl` | ソース | Rational型定義（Rational{BigInt}の基盤） |
| GMP_jll | `stdlib/GMP_jll/` | JLL | libgmpバイナリの提供 |
