# 機能設計書 61-BigIntクラス

## 概要

本ドキュメントは、mrubyにおける多倍長整数（BigInt）機能の設計を記述する。mruby-bigint gemとして実装され、Integerクラスを拡張して任意精度の整数演算をサポートする。

### 本機能の処理概要

BigIntクラスは、mrubyの固定精度整数（mrb_int: 32bit/64bit）で表現できない大きな整数値を扱うための多倍長整数演算機能を提供する。FREE GMP（fgmp）ライブラリをベースとした独自実装により、GMP等の外部ライブラリに依存せずに任意精度整数の四則演算、ビット演算、べき乗、文字列変換等を実現する。

**業務上の目的・背景**：暗号処理や科学計算、金融計算等において、64bitを超える整数値を正確に扱う必要がある場面は多い。CRubyではBignumが標準で組み込まれているが、mrubyは組み込み用途を想定しており、メモリ効率を重視した独自のBigInt実装を提供することで、必要な場合にのみ多倍長整数機能を有効化できる設計としている。

**機能の利用シーン**：Integerの演算結果がmrb_intの範囲を超えた場合に自動的にBigIntへ昇格して計算が継続される。ユーザは明示的にBigIntを操作する必要はなく、透過的に利用できる。暗号計算（RSA等）でのべき乗剰余演算（powm）、大規模な数値の文字列変換、ビット演算等で活用される。

**主要な処理内容**：
1. 多倍長整数の内部表現管理（limb配列による桁管理、埋め込み/ヒープの2モード）
2. 四則演算（加算・減算・乗算・除算・剰余）
3. ビット演算（AND・OR・XOR・NOT・左シフト・右シフト）
4. べき乗演算・モジュラべき乗演算（Montgomery乗算対応）
5. 文字列との相互変換（2進数〜36進数対応）
6. 浮動小数点数との相互変換
7. GCD/LCM演算、平方根演算
8. 自動正規化（BigIntがmrb_intの範囲に収まる場合はFixnumへ自動降格）

**関連システム・外部連携**：mruby-rational（有理数演算でのGCD利用）、mruby-sprintf（フォーマット出力での2の補数変換）と連携する。

**権限による制御**：特になし。全てのコンテキストで利用可能。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | CLIベースのため画面なし |

## 機能種別

計算処理 / データ変換

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| 整数値 | mrb_int / mrb_float / String | Yes | BigIntに変換する元の値 | 文字列の場合はbase 2〜36の数値文字列であること |
| base | mrb_int | No | 文字列変換時の基数（デフォルト10） | 2〜36の範囲 |
| 演算対象 | Integer / BigInt / Float | Yes | 演算のオペランド | 型に応じた自動変換が行われる |

### 入力データソース

mrubyの整数演算でオーバーフローが発生した場合に自動的にBigInt値が生成される。また、`to_i`メソッドや文字列パース時に直接生成される場合もある。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 演算結果 | Integer / BigInt | 演算結果。mrb_intの範囲内であれば自動的にFixnumに降格 |
| 文字列表現 | String | to_sメソッドによる指定基数の文字列表現 |
| 浮動小数点値 | Float | to_fメソッドによる近似浮動小数点値 |

### 出力先

mruby値スタック上に結果を返却

## 処理フロー

### 処理シーケンス

```
1. BigInt値の生成
   └─ mrb_intのオーバーフロー検知 or 明示的な文字列パースにより、RBigint構造体を割り当て
2. 内部表現の選択
   └─ limb数がRBIGINT_EMBED_SIZE_MAX以下なら埋め込みモード、それ以上ならヒープモード
3. 演算の実行
   └─ オペランドの型判定 → 必要に応じてBigIntへの変換 → mpz_*関数による演算
4. 結果の正規化
   └─ bint_norm()により、結果がmrb_intの範囲内であればFixnumに降格
5. メモリ管理
   └─ GC時にmrb_gc_free_bint()でヒープメモリを解放
```

### フローチャート

```mermaid
flowchart TD
    A[整数演算開始] --> B{mrb_intで表現可能?}
    B -->|Yes| C[通常のFixnum演算]
    B -->|No| D[BigInt値生成]
    D --> E{埋め込みサイズ以内?}
    E -->|Yes| F[埋め込みモードで格納]
    E -->|No| G[ヒープモードで格納]
    F --> H[mpz_*関数で演算]
    G --> H
    H --> I[結果をbint_norm]
    I --> J{結果がmrb_int範囲内?}
    J -->|Yes| K[Fixnumに降格して返却]
    J -->|No| L[BigIntとして返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-61-01 | 自動昇格 | mrb_intでオーバーフローが発生した場合、自動的にBigIntに昇格する | 整数演算時 |
| BR-61-02 | 自動降格 | 演算結果がmrb_intの範囲に収まる場合、Fixnumに自動降格する | BigInt演算結果の正規化時 |
| BR-61-03 | ゼロ除算禁止 | 除算・剰余演算でゼロ除算を検出した場合、ZeroDivisionError例外を発生させる | 除算・剰余演算時 |
| BR-61-04 | べき乗制限 | 結果のビット数がMRB_BIGINT_POW_MAX_BITS（100万ビット）を超える場合、RangeError例外を発生させる | べき乗演算時 |
| BR-61-05 | 符号付き除算 | Rubyのfloor除算セマンティクスに従い、負数の除算結果は負の無限大方向に丸める | 除算・divmod演算時 |

### 計算ロジック

- 内部表現: mp_limb配列（デフォルト32bit limb）による多倍長整数表現
- 乗算: 教科書的なO(n^2)アルゴリズム + Karatsuba法（大きな数値の場合）
- 除算: Knuthの除算アルゴリズム（Algorithm D）
- べき乗剰余: Montgomery乗算法を使用した高速化
- ビット演算: 2の補数表現への変換を介した論理演算

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

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

該当なし（メモリ上での計算処理のみ）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | ZeroDivisionError | 除算・剰余演算でゼロ除算 | 演算前にゼロチェック |
| - | RangeError | mrb_intへの変換時に範囲超過、またはべき乗結果が大きすぎる | 値の範囲を確認 |
| - | TypeError | BigInt演算に不適切な型が渡された | 型チェックを実施 |
| - | ArgumentError | 負の指数でのべき乗、平方根の負数指定 | 引数の妥当性を検証 |
| - | RuntimeError | bigintサイズが大きすぎる（SIZE_MAXオーバーフロー） | メモリ制約に注意 |

### リトライ仕様

リトライは不要（計算処理のため）

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

該当なし

## パフォーマンス要件

- メモリプール（MRB_BIGINT_POOL_SIZE）によるスコープ付きメモリ管理で一時オブジェクトのヒープ割り当てを削減
- 埋め込みモード（RBIGINT_EMBED_SIZE_MAX）により小さなBigIntはRBigint構造体内に直接格納してヒープ割り当てを回避
- Montgomery乗算法によるモジュラべき乗の高速化
- 単一limb加算の高速パス最適化

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

- べき乗演算に上限（MRB_BIGINT_POW_MAX_BITS = 100万ビット）を設けて、リソース枯渇攻撃を防止
- メモリ割り当てサイズのオーバーフローチェック（SIZE_MAX / sizeof(mp_limb)）

## 備考

- ビルド時にMRB_USE_BIGINTが自動定義される
- MRB_NO_MPZ64BITを定義することで16bit limb（小さなプラットフォーム向け）を使用可能
- FREE GMP（fgmp）ベースの実装であり、パブリックドメインライセンス

---

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

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

### 推奨読解順序

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

まず、多倍長整数の内部表現を理解することが重要。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | bigint.h | `mrbgems/mruby-bigint/core/bigint.h` | mpz_t構造体、RBigint構造体、埋め込み/ヒープの2モード管理 |

**読解のコツ**:
- `mpz_t`は内部計算用の構造体で、`p`がlimb配列ポインタ、`sn`が符号（-1/0/1）、`sz`がlimb数を表す
- `RBigint`はmrubyオブジェクトとしての構造体で、union内に埋め込みモード（ary）とヒープモード（heap）を持つ
- **33-59行目**: RBigint構造体の定義。MRB_OBJECT_HEADERに続いてunionで埋め込み/ヒープを管理
- **62-113行目**: フラグビットフィールドの定義。下位4bitがサイズ、bit4-5が符号を表す

#### Step 2: メモリ管理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | bigint.c | `mrbgems/mruby-bigint/core/bigint.c` | メモリプール、limb配列の確保・解放 |

**主要処理フロー**:
- **32-99行目**: メモリプール基盤。mpz_pool_t構造体とpool_alloc/pool_save/pool_restore関数
- **108-114行目**: mpz_init() - mpz_t構造体の初期化
- **117-135行目**: mpz_init_heap() - ヒープ優先のメモリ確保
- **139-158行目**: mpz_init_temp() - プール優先のメモリ確保（一時変数用）
- **173-207行目**: mpz_realloc() - limb配列の再確保（プールからヒープへの移行を含む）
- **306-324行目**: mpz_clear() - メモリ解放（プールメモリは解放しない）

#### Step 3: 基本演算を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | bigint.c | `mrbgems/mruby-bigint/core/bigint.c` | 四則演算の実装 |

**主要処理フロー**:
- **454-569行目**: mpz_add() - 加算。符号の組み合わせに応じてuadd/usubを使い分け
- **597-612行目**: mpz_sub() - 減算。符号を反転してmpz_addへ委譲
- **619-760行目**: mpz_mul() - 乗算。Karatsuba法による最適化を含む
- **820行目以降**: mpz_div系 - Knuth除算アルゴリズム

#### Step 4: mrubyインターフェースを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | bigint.c | `mrbgems/mruby-bigint/core/bigint.c` | mruby値との変換、C API |

**主要処理フロー**:
- **5262-5268行目**: bint_as_mpz() - RBigintからmpz_tへの変換（コピーなし、参照のみ）
- **5271-5291行目**: bint_set() - mpz_tの結果をRBigintに格納（埋め込み/ヒープの判定含む）
- **5293-5307行目**: bint_new() / bint_new_int() - 新規RBigintオブジェクトの生成
- **5342-5353行目**: bint_norm() - 結果がmrb_int範囲内ならFixnumに降格
- **5536-5579行目**: mrb_bint_add() - 加算のC API（Float対応含む）
- **5662-5677行目**: mrb_bint_mul() - 乗算のC API（0倍、1倍の高速パス）
- **5871-5905行目**: mrb_bint_pow() - べき乗演算（上限チェック含む）
- **5907-5979行目**: mrb_bint_powm() - モジュラべき乗（Montgomery乗算法）

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

```
mrubyの整数演算（src/numeric.c）
    |
    +-- mrb_bint_add() / mrb_bint_sub() / mrb_bint_mul() / mrb_bint_div()
    |       |
    |       +-- mrb_as_bint()       ... 必要に応じてBigIntへ変換
    |       +-- bint_as_mpz()       ... RBigint -> mpz_t参照
    |       +-- mpz_add/sub/mul/div ... 内部演算
    |       +-- bint_new()          ... mpz_t -> RBigint
    |       +-- bint_norm()         ... 自動降格判定
    |
    +-- mrb_bint_new_int() / mrb_bint_new_str() / mrb_bint_new_float()
    |       |
    |       +-- mpz_init_set_int()  ... 整数から初期化
    |       +-- mpz_init_set_str()  ... 文字列から初期化
    |
    +-- mrb_bint_pow() / mrb_bint_powm()
    |       |
    |       +-- mpz_pow()           ... 通常べき乗
    |       +-- mpz_powm()          ... Barrett法によるモジュラべき乗
    |       +-- mpz_powm_montgomery() ... Montgomery乗算法
    |
    +-- mrb_gc_free_bint()          ... GC時のメモリ解放
```

### データフロー図

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

mrb_int (Fixnum)    ──+
                      |
mrb_float (Float)   ──+──▶ BigInt生成               ──▶ RBigint構造体
                      |      (bint_new_int/float/str)        |
String              ──+                                      |
                                                             v
RBigint + RBigint   ──────▶ mpz_*演算関数             ──▶ mpz_t結果
                             (add/sub/mul/div/pow)           |
                                                             v
mpz_t結果           ──────▶ bint_norm()               ──▶ mrb_value
                             (自動降格判定)                (Fixnum or BigInt)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| bigint.h | `mrbgems/mruby-bigint/core/bigint.h` | ヘッダ | mpz_t, RBigint構造体定義、マクロ定義 |
| bigint.c | `mrbgems/mruby-bigint/core/bigint.c` | ソース | 多倍長整数演算の全実装（約6300行） |
| mrbgem.rake | `mrbgems/mruby-bigint/mrbgem.rake` | 設定 | gem仕様定義、MRB_USE_BIGINTの自動定義 |
| bigint.rb | `mrbgems/mruby-bigint/test/bigint.rb` | テスト | BigInt演算のテストケース |
| numeric.c | `src/numeric.c` | ソース | 整数演算からBigIntへの昇格処理 |
