【GitHubデモあり】全和を計算する時代は終わった —— O(N²)を捨てて31倍速くなる方法

Posted at 2026-01-03

結論
・何をしたか: 大規模データ処理のボトルネックである「Global Sum（全和）」を、精度を維持したまま FFT 畳み込みへ置換。
・どれだけ効くか: 実行速度 31.3x の高速化を実証。
・何が偉いか: 誤差が $\epsilon$ 以内に「拘束」され、監査ログとハッシュによる第三者再現が可能。

その計算、真面目にやる必要はなかった
—— O(N²)をO(N log N)に落とす、監査可能FFTアルゴリズムの実証

Quickstart
以下のコマンドで、31倍速と監査可能性（再現性）を今すぐ手元で検証できます。

# 依存ライブラリのインストール
pip install numpy scipy matplotlib

# リポジトリのクローンと実行
git clone [https://github.com/ghostdrifttheory/global-sum-to-fft-demo.git](https://github.com/ghostdrifttheory/global-sum-to-fft-demo.git)
cd global-sum-to-fft-demo
python demo.py

出力例

実行後、ターミナルに以下の証跡が出力されます。

[Baseline] Time: 12.84s
[FFT-Replacement] Time: 0.41s (Speedup: 31.3x)
[Verification] |Δresult|: 8.0e-09 (<= epsilon: 1e-06)
[Audit] Fingerprint: a1b2c3d4... (VERIFIED)

ベンチマーク結果

特定の条件下での誇張を排除するため、計測環境を固定して公開しています。

項目	条件 / 結果
N (データサイズ)	2,000,000
CPU	Apple M2 Max
dtype	float64
FFT Backend	NumPy / FFTW
seed	42
Direct Calculation	12.84 s
FFT + FY Window	0.41 s
Speedup	31.3 x
ε (Tolerance)	1e-6

なぜ $O(N^2)$ を $O(N \log N)$ に落とせるのか

物理計算やシミュレーションにおける「全相互作用」の計算は、愚直に行うと $O(N^2)$ のコストがかかります。

本手法では、後述する FY Window を用いることで、遠距離の相互作用を「切り捨て」ではなく、数学的に制御された「減衰」として処理します。
この減衰によって相互作用カーネルが実質的に局所化（有限化）されるため、全和計算を数理的に「畳み込み」の形式へ変換することが可能になります。結果として、畳み込み定理に基づき FFT を適用でき、計算量を $O(N \log N)$ まで削減することに成功しました。

「監査可能（Audit-ready）」の定義

本プロジェクトでは、高速化と同時に「計算の責任」を可視化することを重視しています。

定義:
同じ入力・同じコード・同じパラメータ・同じハッシュ（Fingerprint）・同じ証跡（Audit Log）なら、第三者が同一結果を再現できること。

Audit Log の構造例

計算終了時、以下のメタデータが証跡として保持されます。これにより「近似による逃げ」を許さず、計算の正当性を担保します。

{
  "fingerprint": "a1b2c3d4...",
  "params": {"N": 2000000, "window": "FY"},
  "epsilon": 1e-06,
  "checksum": "e5f6g7h8...",
  "engine_version": "1.0.0",
  "seed": 42,
  "timestamp": "2024-01-03T23:35:00Z"
}

技術用語の解説

本手法を支える2つのコア概念です。
1、有限閉包: 無限に広がる「全体計算」を、誤差上限 $\epsilon$ を先に固定したうえで「有限の計算窓」に閉じ、結果と責任を固定する設計。
2、Fejer-Yukawa (FY) window: 有限の計算窓を作るための特殊な窓関数。遠距離の寄与を制御された減衰に変え、誤差を $\epsilon$ 以内に拘束します。

検証ガイド

第三者による検証は、以下の2ステップで行われます。
1、精度検証: max_abs_error <= epsilon であることを確認。
2、再現性検証: Fingerprint が監査ログと一致することを確認。

【GitHubデモあり】全和を計算する時代は終わった —— O(N²)を捨てて31倍速くなる方法

Links