# 機能設計書 22-累積演算

## 概要

本ドキュメントは、Julia Base ライブラリが提供する累積演算機能の設計について記述する。累積演算とは、コレクションの要素を先頭から順に二項演算子で畳み込みながら、各中間結果を配列として保持する処理群である。

### 本機能の処理概要

累積演算は、`accumulate` / `accumulate!` による汎用累積関数と、`cumsum` / `cumsum!` / `cumprod` / `cumprod!` による特化型累積関数を提供する。多次元配列に対しては `dims` キーワード引数により特定次元に沿った累積演算も可能である。

**業務上の目的・背景**：時系列データの累積合計、累積積の計算、ランニングトータルの算出など、各ステップでの中間結果が必要な場面で利用される。科学計算や金融データ分析において、累積分布関数の計算やポートフォリオの累積リターン計算などの基本操作を提供する。浮動小数点演算においてはペアワイズ加算アルゴリズムにより数値安定性を向上させている。

**機能の利用シーン**：時系列データの累積合計グラフの作成、累積積による確率計算、前方から順に二項演算を適用した中間結果の記録、多次元配列の特定次元に沿った累積処理で利用される。

**主要な処理内容**：
1. `accumulate(op, A)` による汎用累積演算
2. `accumulate!(op, B, A)` によるインプレース累積演算
3. `cumsum` / `cumsum!` による累積和（型昇格付き）
4. `cumprod` / `cumprod!` による累積積（型昇格付き）
5. `dims` 指定による次元沿い累積演算
6. `init` キーワード引数による初期値指定
7. ペアワイズ加算による数値安定な累積和
8. Tuple に対する累積演算（コンパイル時展開）

**関連システム・外部連携**：なし。Base モジュール内で完結する。

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

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 画面関連なし（ライブラリ関数） |

## 機能種別

計算処理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| op | Function | Yes | 二項演算子（+, *, min 等） | 呼び出し可能であること |
| A | Any (iterable) | Yes | 累積演算対象のコレクション | iterateプロトコルを実装していること |
| B | AbstractArray | No（accumulate!の場合Yes） | 出力先配列 | Aと同じサイズであること |
| dims | Integer | No | 累積を行う次元 | 1以上の整数 |
| init | Any | No | 初期値 | opの引数として有効な値 |

### 入力データソース

Julia プログラム内のコレクション（Array、Vector、Tuple、Range、その他イテラブルオブジェクト）。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | AbstractArray / Tuple | 各位置での累積演算結果を格納した配列またはタプル |

### 出力先

呼び出し元への戻り値（accumulate!の場合は引数Bに書き込み）。

## 処理フロー

### 処理シーケンス

```
1. cumsum(A) / accumulate(op, A) が呼ばれる
   └─ cumsumの場合: add_sum を op として accumulate に委譲
2. accumulate(op, A; dims, init)
   └─ dims未指定 + 非ベクトル: Iterators.accumulate でイテレータ版を使用
   └─ dims指定 or ベクトル: accumulate!(op, out, A; dims, init) へ
3. accumulate! の内部処理
   └─ dims未指定: _accumulate!(op, B, A, init)
   └─ dims指定: _accumulate!(op, B, A, init, dim)
4. cumsumの特殊処理
   └─ ArithmeticRounds型の場合: accumulate_pairwise! でペアワイズ加算
   └─ その他: 通常の accumulate! を使用
5. accumulate_pairwise!
   └─ 要素数 < 128: 逐次累積
   └─ 要素数 >= 128: 半分に分割して再帰的にペアワイズ累積
```

### フローチャート

```mermaid
flowchart TD
    A[cumsum/cumprod/accumulate] --> B{cumsumか?}
    B -->|Yes| C{ArithmeticRounds?}
    B -->|No| D[accumulate!]
    C -->|Yes| E[accumulate_pairwise!]
    C -->|No| D
    D --> F{dims指定?}
    F -->|Yes| G[_accumulate! with dims]
    F -->|No| H{Vectorか?}
    H -->|Yes| I[_accumulate!]
    H -->|No| J[Iterators.accumulate]
    E --> K{要素数 < 128?}
    K -->|Yes| L[逐次累積]
    K -->|No| M[分割+再帰ペアワイズ]
    G --> N[結果返却]
    I --> N
    J --> N
    L --> N
    M --> N
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 型昇格 | cumsum/cumprod は小整数型（Int8等）を Int/UInt に昇格する | add_sum/mul_prod 使用時 |
| BR-02 | ペアワイズ加算 | 浮動小数点のcumsumではペアワイズアルゴリズムを使用して数値安定性を向上 | ArithmeticRounds 型の場合 |
| BR-03 | 出力サイズ | 出力配列は入力配列と同じサイズ・形状 | 常時 |
| BR-04 | init の扱い | init指定時、最初の要素は op(init, A[1]) として計算される | init が指定された場合 |

### 計算ロジック

- `accumulate(op, [a, b, c])` = `[a, op(a,b), op(op(a,b),c)]`
- `accumulate(op, [a, b, c]; init=x)` = `[op(x,a), op(op(x,a),b), op(op(op(x,a),b),c)]`
- ペアワイズ累積加算: 128要素未満では逐次処理、128以上では半分に分割して再帰的に処理し中間部分和を維持

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

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

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

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | DimensionMismatch | accumulate!でBとAのサイズが不一致 | 同サイズの配列を用意する |
| - | ArgumentError | 不正なキーワード引数 | dims, init のみ使用可能 |
| - | MethodError | 要素型にopが適用不可 | 適切な演算子を選択する |

### リトライ仕様

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

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

該当なし。

## パフォーマンス要件

- O(n) 時間計算量（ペアワイズ版は定数倍のオーバーヘッドで約1.2倍の演算回数）
- ペアワイズ加算により浮動小数点の誤差蓄積を O(log n) に抑制
- accumulate! によるインプレース演算で追加メモリ割り当てを回避

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

特になし。

## 備考

- Julia 1.5 以降、非配列イテレータに対する cumsum / accumulate をサポート
- Tuple に対する accumulate は `afoldl` を用いてコンパイル時に展開される
- `Iterators.accumulate` による遅延版も存在する（別機能 No.26 参照）

---

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

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

### 推奨読解順序

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

累積演算は特別なデータ構造を定義しないが、リダクション演算の BottomRF を内部で使用する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | reduce.jl | `base/reduce.jl` | BottomRF, _InitialValue, reduce_first の定義を確認 |

**読解のコツ**: 累積演算は reduce.jl の BottomRF を利用して初回要素の特別処理を行う。accumulate.jl を読む前に reduce.jl の 70-84行目を確認すると理解しやすい。

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | accumulate.jl | `base/accumulate.jl` | cumsum, cumprod, accumulate, accumulate! の公開API |

**主要処理フロー**:
1. **69-119行目**: `cumsum` の定義と ArithmeticStyle による分岐
2. **149-150行目**: `cumsum(itr)` - 非配列イテレータ版
3. **174-198行目**: `cumprod` の定義
4. **234-294行目**: `accumulate` の汎用実装
5. **305-346行目**: `accumulate!` のインプレース実装

#### Step 3: ペアワイズ加算アルゴリズムを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | accumulate.jl | `base/accumulate.jl` | _accumulate_pairwise!, accumulate_pairwise! の実装 |

**主要処理フロー**:
- **7-23行目**: `_accumulate_pairwise!` - 再帰的ペアワイズ累積の本体
  - **8行目**: n < 128 で逐次処理に切り替え
  - **18-20行目**: n >= 128 で半分に分割して再帰
- **25-36行目**: `accumulate_pairwise!` - エントリーポイント、最初の要素を reduce_first で処理

#### Step 4: Tuple版累積演算を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | accumulate.jl | `base/accumulate.jl` | accumulate(op, xs::Tuple) の実装 |

**主要処理フロー**:
- **296-303行目**: `accumulate(op, xs::Tuple)` - afoldl を使用したコンパイル時展開版

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

```
cumsum(A) / cumprod(A) / accumulate(op, A)
    |
    +-- cumsum(A; dims=d)
    |       +-- cumsum!(out, A; dims=d)
    |               +-- [ArithmeticRounds] accumulate_pairwise!(add_sum, out, v)
    |               |       +-- _accumulate_pairwise!(op, c, v, s, i1, n)
    |               +-- [その他] accumulate!(add_sum, out, A; dims=d)
    |
    +-- accumulate(op, A; dims, init)
    |       +-- [非ベクトル, dims=nothing] Iterators.accumulate(op, A)
    |       +-- accumulate!(op, out, A; dims, init)
    |               +-- [dims=nothing] _accumulate!(op, B, A, init)
    |               +-- [dims指定] _accumulate!(op, B, A, init, dim)
    |
    +-- accumulate(op, xs::Tuple)
            +-- afoldl (コンパイル時展開)
```

### データフロー図

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

A (Array/Vector)    ---->  accumulate(op, A)
                           |
                           +-- accumulate_pairwise!            ---->  [a, op(a,b),
                           |   (ペアワイズ: 数値安定)                    op(op(a,b),c), ...]
                           |
                           +-- _accumulate!                    ---->  同サイズ配列
                           |   (逐次累積)
                           |
xs (Tuple)          ---->  accumulate(op, xs)
                           +-- afoldl (展開)                   ---->  Tuple
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| accumulate.jl | `base/accumulate.jl` | ソース | 累積演算の全実装（cumsum, cumprod, accumulate, accumulate!） |
| reduce.jl | `base/reduce.jl` | ソース | BottomRF, _InitialValue, reduce_first, add_sum, mul_prod の定義 |
| iterators.jl | `base/iterators.jl` | ソース | Iterators.accumulate（遅延累積）の定義 |
