# 機能設計書：48-random

## 1. 概要

### 機能名
random - 乱数生成モジュール

### 目的
Nim言語の標準乱数生成器（RNG）を提供する。xoroshiro128+アルゴリズムに基づく高速で高品質な疑似乱数生成を実装し、整数・浮動小数点数・スライス・配列要素のランダム選択、シャッフル、ガウス分布など多様な乱数生成機能を提供する。

### 関連画面
- 該当なし（ライブラリモジュール）

### 機能種別
- [x] ライブラリ
- [ ] バッチ
- [ ] 画面
- [ ] API
- [ ] イベント

### 重要な注意事項
**このモジュールは暗号化目的には使用しないでください！** 暗号学的に安全な乱数が必要な場合は `std/sysrand` モジュールを使用してください。

## 2. 入力仕様

### 乱数生成パラメータ
| パラメータ名 | 型 | 必須 | 説明 |
|-------------|-----|------|------|
| max | Natural | Yes | 整数乱数の上限値（0..max） |
| max | float | Yes | 浮動小数点乱数の上限値（0.0..max） |
| x | HSlice[T, T] | Yes | 範囲指定（a..b） |
| seed | int64 | No | 乱数シード値 |

### サンプリングパラメータ
| パラメータ名 | 型 | 必須 | 説明 |
|-------------|-----|------|------|
| a | openArray[T] | Yes | サンプリング対象の配列 |
| s | set[T] | Yes | サンプリング対象の集合 |
| cdf | openArray[U] | No | 累積分布関数（重み付きサンプリング用） |

### ガウス分布パラメータ
| パラメータ名 | 型 | 必須 | デフォルト | 説明 |
|-------------|-----|------|-----------|------|
| mu | float | No | 0.0 | 平均 |
| sigma | float | No | 1.0 | 標準偏差 |

## 3. 出力仕様

### 乱数結果
| 項目 | 型 | 説明 |
|------|-----|------|
| 整数乱数 | int / uint64 | 指定範囲内の整数 |
| 浮動小数点乱数 | float | 指定範囲内の浮動小数点数 |
| 要素 | T | 配列/集合からのランダム要素 |
| ガウス乱数 | float | 正規分布に従う乱数 |

## 4. 型定義

### Rand型（94-108行目）
```nim
type
  Rand* = object ## 乱数生成器の状態
    a0, a1: Ui   # xoroshiro128+の内部状態
```

### Ui型（84-91行目）
```nim
when hasWorkingInt64:
  type Ui = uint64
  const randMax = 18_446_744_073_709_551_615u64
else:
  type Ui = uint32
  const randMax = 4_294_967_295u32
```

## 5. 処理フロー

### 5.1 xoroshiro128+アルゴリズム（next関数）

```
[next(r: var Rand): uint64]
    │
    ├── s0 = r.a0
    ├── s1 = r.a1
    ├── result = s0 + s1
    │
    ├── s1 = s1 xor s0
    │
    ├── r.a0 = rotl(s0, 55) xor s1 xor (s1 shl 14)
    │        ↑
    │        回転左シフト55ビット + XOR + 左シフト14ビット
    │
    └── r.a1 = rotl(s1, 36)
             ↑
             回転左シフト36ビット
```

### 5.2 範囲付き整数乱数生成

```
[rand(r: var Rand; max: Natural): int]
    │
    ├── [max == 0] ── return 0
    │
    ├── [max == uint64.high] ── return next(r)
    │
    └── [その他] ── モジュロバイアス回避ループ
            │
            while true:
                x = next(r)
                if x <= randMax - (randMax mod max) or iters > 20:
                    return x mod (max + 1)
                inc iters
```

### 5.3 浮動小数点乱数生成

```
[rand(r: var Rand; max: float): float]
    │
    ├── x = next(r)
    │
    ├── [JS backend]
    │       result = (float(x) / float(high(uint64))) * max
    │
    └── [C backend]
            u = (0x3FF shl 52) or (x shr 12)
            result = (cast[float](u) - 1.0) * max
```

### 5.4 シャッフルアルゴリズム（Fisher-Yates）

```
[shuffle(r: var Rand; x: var openArray[T])]
    │
    for i in countdown(x.high, 1):
        j = r.rand(i)
        swap(x[i], x[j])
```

### 5.5 ガウス分布生成（Ratio of Uniforms法）

```
[gauss(r: var Rand; mu, sigma: float): float]
    │
    const K = sqrt(2 / E)
    │
    while true:
        a = rand(r, 1.0)
        b = (2.0 * rand(r, 1.0) - 1.0) * K
        if b * b <= -4.0 * a * a * ln(a):
            break
    │
    result = mu + sigma * (b / a)
```

## 6. API一覧

### 6.1 状態初期化関数

| 関数名 | シグネチャ | 説明 | 行番号 |
|--------|-----------|------|--------|
| initRand | `proc initRand*(seed: int64): Rand` | シード指定でRand状態を初期化 | 588 |
| initRand | `proc initRand(): Rand` | 現在時刻でRand状態を初期化 | 687 |
| randomize | `proc randomize*(seed: int64)` | シード指定でデフォルトRNGを初期化 | 615 |
| randomize | `proc randomize*()` | 現在時刻でデフォルトRNGを初期化 | 739 |

### 6.2 基本乱数生成関数

| 関数名 | シグネチャ | 説明 | 行番号 |
|--------|-----------|------|--------|
| next | `proc next*(r: var Rand): uint64` | 生の64ビット乱数を生成 | 138 |
| rand | `proc rand*(r: var Rand; max: Natural): int` | 0..maxの整数乱数（状態指定） | 246 |
| rand | `proc rand*(max: int): int` | 0..maxの整数乱数（デフォルトRNG） | 263 |
| rand | `proc rand*(r: var Rand; max: range[0.0..high(float)]): float` | 0.0..maxの浮動小数点乱数（状態指定） | 284 |
| rand | `proc rand*(max: float): float` | 0.0..maxの浮動小数点乱数（デフォルトRNG） | 311 |

### 6.3 スライス・型指定乱数生成関数

| 関数名 | シグネチャ | 説明 | 行番号 |
|--------|-----------|------|--------|
| rand | `proc rand*[T: Ordinal or SomeFloat](r: var Rand; x: HSlice[T, T]): T` | スライス範囲の乱数（状態指定） | 332 |
| rand | `proc rand*[T: Ordinal or SomeFloat](x: HSlice[T, T]): T` | スライス範囲の乱数（デフォルトRNG） | 357 |
| rand | `proc rand*[T: Ordinal](r: var Rand; t: typedesc[T]): T` | 型の全範囲から乱数（状態指定） | 379 |
| rand | `proc rand*[T: Ordinal](t: typedesc[T]): T` | 型の全範囲から乱数（デフォルトRNG） | 400 |

### 6.4 サンプリング関数

| 関数名 | シグネチャ | 説明 | 行番号 |
|--------|-----------|------|--------|
| sample | `proc sample*[T](r: var Rand; s: set[T]): T` | 集合からランダム要素（状態指定） | 425 |
| sample | `proc sample*[T](s: set[T]): T` | 集合からランダム要素（デフォルトRNG） | 444 |
| sample | `proc sample*[T](r: var Rand; a: openArray[T]): T` | 配列からランダム要素（状態指定） | 464 |
| sample | `proc sample*[T](a: openArray[T]): lent T` | 配列からランダム要素（デフォルトRNG） | 479 |
| sample | `proc sample*[T, U](r: var Rand; a: openArray[T]; cdf: openArray[U]): T` | CDF使用サンプリング（状態指定） | 499 |
| sample | `proc sample*[T, U](a: openArray[T]; cdf: openArray[U]): T` | CDF使用サンプリング（デフォルトRNG） | 533 |

### 6.5 シャッフル関数

| 関数名 | シグネチャ | 説明 | 行番号 |
|--------|-----------|------|--------|
| shuffle | `proc shuffle*[T](r: var Rand; x: var openArray[T])` | 配列をシャッフル（状態指定） | 636 |
| shuffle | `proc shuffle*[T](x: var openArray[T])` | 配列をシャッフル（デフォルトRNG） | 652 |

### 6.6 ガウス分布関数

| 関数名 | シグネチャ | 説明 | 行番号 |
|--------|-----------|------|--------|
| gauss | `proc gauss*(r: var Rand; mu = 0.0; sigma = 1.0): float` | ガウス乱数（状態指定） | 562 |
| gauss | `proc gauss*(mu = 0.0, sigma = 1.0): float` | ガウス乱数（デフォルトRNG） | 578 |

### 6.7 並列計算支援関数

| 関数名 | シグネチャ | 説明 | 行番号 |
|--------|-----------|------|--------|
| skipRandomNumbers | `proc skipRandomNumbers*(s: var Rand)` | 2^64個の乱数をスキップ | 161 |

### 6.8 状態アクセス

| 関数名 | シグネチャ | 説明 | 行番号 |
|--------|-----------|------|--------|
| randState | `template randState*(): untyped` | デフォルトRNG状態へのアクセス | 130 |

## 7. ビジネスルール

### BR-001: xoroshiro128+アルゴリズム
- 実装は xoroshiro128+ (xor/rotate/shift/rotate) に基づく（12-15行目）
- 参考: https://xoroshiro.di.unimi.it

### BR-002: デフォルトRNGは非スレッドセーフ
- デフォルトRNGを使用する関数はスレッドセーフではない（51, 107行目）
- スレッド間で乱数を使用する場合は各スレッドで独自のRand状態を保持すること

### BR-003: 初期化なしの決定論的動作
- `randomize()` を呼び出さない場合、常に同じ乱数列が生成される（53-58行目）
- デフォルト状態: a0 = 0x69B4C98CB8530805, a1 = 0xFED1DD3004688D67CA（111-113行目）

### BR-004: モジュロバイアス回避
- rand(max) はモジュロバイアスを回避するため、条件を満たす値が出るまでループ（229-244行目）
- 最大20回のリトライ後は強制的に値を返却（241行目）

### BR-005: skipRandomNumbers による並列計算サポート
- `skipRandomNumbers` は 2^64 回の `next` 呼び出しと等価（164-165行目）
- スレッド間で重複しない乱数列を生成するために使用

### BR-006: シード値0の特別処理
- seed == 0 の場合、内部的に int32.high を使用（606-607行目）
- 理由: 0は xoroshiro128+ の固定点（全ビット0は常に0を出力）

### BR-007: 浮動小数点乱数のビット操作
- Cバックエンドでは IEEE 754 のビット表現を直接操作して効率的に生成（308-309行目）
- `(0x3FF shl 52) or (x shr 12)` で [1.0, 2.0) の値を生成し、1.0を引く

## 8. バリデーションルール

### VR-001: isValid関数による状態検証
- a0 と a1 が両方0の場合、無効な状態とみなす（122-127行目）
- 無効状態では next 関数が常に0を返却するため

### VR-002: スライス範囲の検証
- rand(a..b) で a <= b であることをアサート（348行目）

### VR-003: 集合サンプリングの検証
- sample(s) で集合が空でないことをアサート（438行目）

### VR-004: CDFサンプリングの検証
- cdf.len == a.len であることをアサート（526行目）
- cdf の最後の要素が正であることをアサート（527行目）

## 9. 例外・エラー処理

| エラー種別 | 発生条件 | 処理 |
|-----------|---------|------|
| AssertionDefect | スライスで a > b | アサート失敗 |
| AssertionDefect | 空の集合から sample | アサート失敗 |
| AssertionDefect | CDF長と配列長の不一致 | アサート失敗 |
| quit | urandom 失敗時 | プログラム終了（722行目） |

## 10. プラットフォーム依存性

### JavaScript バックエンド
- uint32 を使用（hasWorkingInt64 が false の場合）
- 浮動小数点乱数生成が異なる実装（299-306行目）
- 時刻取得に times.epochTime を使用（699行目）

### C/C++ バックエンド
- uint64 を使用
- sysrand.urandom を使用して初期シードを取得（714行目）
- スレッドサポート時は Lock を使用（680-683行目）

### NimScript
- CompileTime と CompileDate のハッシュをシードとして使用（704-706行目）

## 11. スレッドセーフティ

### スレッドセーフな関数
- `initRand(seed: int64): Rand`
- `rand(r: var Rand; ...)` - 状態を明示的に渡す全ての関数
- `shuffle(r: var Rand; ...)`
- `sample(r: var Rand; ...)`
- `gauss(r: var Rand; ...)`

### スレッドセーフでない関数
- `rand(max: int)` - デフォルトRNGを使用
- `rand(max: float)` - デフォルトRNGを使用
- `shuffle(x)` - デフォルトRNGを使用
- `sample(a)` - デフォルトRNGを使用
- `gauss()` - デフォルトRNGを使用
- `randomize()` / `randomize(seed)` - グローバル状態を変更

## 12. 関連モジュール

- `std/sysrand` - 暗号学的に安全な乱数生成（68行目）
- `std/math` - 基本数学ルーチン（69, 74行目）
- `std/stats` - 統計分析（70行目）
- `std/algorithm` - upperBound 使用（74行目）
- `std/times` - 時刻ベースのシード取得
- `std/hashes` - NimScript でのシード生成
- `std/monotimes` - 高精度時刻取得

## 13. バージョン履歴

| バージョン | 追加機能 |
|-----------|---------|
| 1.3 | gauss関数 |
| 1.5 | randStateテンプレート |
| 1.5.1 | initRand()（引数なし版）のエクスポート |
| 1.7.1 | rand(typedesc[T])関数 |

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

### 14.1 推奨読解順序

1. **型定義とアルゴリズム概要** (10-127行目)
   - xoroshiro128+ の説明
   - Rand 型の定義
   - isValid 関数

2. **コアアルゴリズム** (135-227行目)
   - rotl（回転左シフト）
   - next（乱数生成の核）
   - skipRandomNumbers（並列計算サポート）

3. **整数乱数生成** (229-282行目)
   - モジュロバイアス回避の実装

4. **浮動小数点乱数生成** (284-330行目)
   - IEEE 754 ビット操作

5. **サンプリングとシャッフル** (425-669行目)
   - Fisher-Yates シャッフル
   - CDF を使った重み付きサンプリング

6. **初期化とシード** (588-754行目)
   - initRand / randomize の実装
   - プラットフォーム依存の初期化

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

```
random.nim
├── [Core RNG]
│   ├── rotl(x, k) (135-136)
│   │   └── 回転左シフト
│   │
│   ├── next(r) (138-159)
│   │   └── xoroshiro128+ アルゴリズム
│   │
│   └── skipRandomNumbers(s) (161-227)
│       └── 2^64 ジャンプ関数
│
├── [Integer Random]
│   ├── rand(r, max: uint|uint64) (229-244) [内部]
│   │   └── モジュロバイアス回避
│   │
│   ├── rand(r, max: Natural) (246-261)
│   │   └── rand(r, uint64(max))
│   │
│   └── rand(max: int) (263-282)
│       └── rand(state, max)
│
├── [Float Random]
│   ├── rand(r, max: float) (284-309)
│   │   └── IEEE 754 ビット操作
│   │
│   └── rand(max: float) (311-330)
│       └── rand(state, max)
│
├── [Slice/Type Random]
│   ├── rand(r, x: HSlice) (332-355)
│   │   └── rand(r, float) または rand(r, uint64)
│   │
│   └── rand(r, t: typedesc[T]) (379-398)
│       └── rand(r, low(T)..high(T))
│
├── [Sampling]
│   ├── sample(r, s: set) (425-442)
│   │   └── rand(r, card(s) - 1)
│   │
│   ├── sample(r, a: openArray) (464-477)
│   │   └── rand(r, a.low..a.high)
│   │
│   └── sample(r, a, cdf) (499-531)
│       └── upperBound(cdf, u)
│
├── [Shuffle]
│   └── shuffle(r, x) (636-650)
│       └── Fisher-Yates (countdown + swap)
│
├── [Gaussian]
│   └── gauss(r, mu, sigma) (562-576)
│       └── Ratio of Uniforms 法
│
└── [Initialization]
    ├── initRand(seed) (588-613)
    │   └── skipRandomNumbers + next
    │
    ├── initRand() (687-734)
    │   ├── [JS] times.epochTime
    │   ├── [NimScript] hash(CompileTime/Date)
    │   └── [C] sysrand.urandom
    │
    └── randomize() (739-754)
        └── initRand()
```

### 14.3 データフロー図

```
[シード/初期化]
      │
      ▼
┌─────────────────┐
│   Rand 状態     │
│ (a0, a1: Ui)    │
└─────────────────┘
      │
      ├── next(r) ─────────────────────┐
      │                                 │
      ▼                                 ▼
┌─────────────────┐         ┌─────────────────┐
│ xoroshiro128+   │         │    uint64       │
│ s0 + s1 + XOR   │────────▶│    乱数値       │
│ + ROTATE        │         └─────────────────┘
└─────────────────┘                  │
                                     ├── [整数] ── mod + バイアス回避
                                     │
                                     ├── [浮動小数点] ── ビット操作
                                     │
                                     └── [範囲] ── スケーリング
                                              │
                                              ▼
                                    ┌─────────────────┐
                                    │   最終結果      │
                                    │ (int/float/T)   │
                                    └─────────────────┘
```

### 14.4 関連ファイル一覧

| ファイルパス | 役割 |
|-------------|------|
| lib/pure/random.nim | メインモジュール（757行） |
| lib/std/sysrand.nim | 暗号学的乱数（urandom） |
| lib/std/private/since.nim | バージョンプラグマ |
| lib/std/private/jsutils.nim | JS用ユーティリティ |
| lib/pure/algorithm.nim | upperBound（CDF サンプリング） |
| lib/pure/math.nim | ln, sqrt（gauss 関数） |
| lib/pure/times.nim | 時刻取得（JS初期化） |
| lib/pure/hashes.nim | ハッシュ（NimScript初期化） |
| lib/pure/os.nim | OS機能（C初期化） |
| lib/pure/monotimes.nim | 高精度時刻 |
