全和を計算する時代は終わった —— O(N²)を捨てて31倍速くなる方法（デモ公開）
- kanna qed
- 1月3日
- 読了時間: 3分
「同じ精度が出るなら、31倍速い方がいいに決まっている」
そんな当たり前の、しかし極めて困難だった課題に対し、Ghost Drift研究所は一つの回答を提示しました。
O(N²)の全和計算をO(N log N)に置き換える方法―― 監査可能なFFTアルゴリズムによる31倍速化の実証
課題：Global Sum（全和）のコスト
シミュレーションや大規模データ処理において、全要素の相互作用を計算する「Global Sum」は常にボトルネックです。 この $O(N^2)$ の計算量を引き受け、その「全体」を真面目に計算し続ける必要はありません。
解決策：Ghost Drift理論によるFFT置換
今回GitHubに公開したのは、Ghost Drift理論の核心である**「有限閉包」**に基づくデモコードです。
独自の窓関数 Fejer-Yukawa (FY) window を用いることで、大規模シミュレーションや物理計算で「全和がボトルネックになる箇所」を、そのままこのアルゴリズムへ置き換えることが可能です。
実証データ：$O(N^2) \rightarrow O(N \log N)$ への跳躍
なぜ、これほどまでに速いのか。それはアルゴリズムの計算量そのものを変革したからです。
Speedup: 12.84s → 0.41s (31.3x)
精度保証: 許容誤差 $\epsilon$ 以内を厳密に維持 ($| \Delta \text{result} | \le 1e-6$)
再現性: 計算パラメータとハッシュ値による完全な検証が可能
監査可能（Audit-ready）の定義
同じ入力・同じコード・同じパラメータ・同じハッシュ（fingerprint）・同じ証跡（audit log）なら、第三者が同一結果を再現できる。
Audit Log出力項目: [hash, params, epsilon, checksum, engine_version, seed, timestamp]
用語解説
有限閉包: 無限に広がる「全体計算」を、誤差上限 $\epsilon$ を先に固定したうえで「有限の計算窓」に閉じ、結果と責任を固定する設計。
Fejer-Yukawa (FY) window: その有限の計算窓を作る窓関数。遠距離の寄与を「切り捨て」ではなく「制御された減衰」に変え、誤差を $\epsilon$ 以内に拘束する。
数理的根拠と検証環境
なぜ31倍なのか: Global Sum（直接計算）: $O(N^2) \rightarrow$ FY window + FFT畳み込み: $O(N \log N)$
Bench: $N=2,000,000$, dtype=float64, CPU=Apple M2 Max, FFT backend=NumPy/FFTW, seed=42
計算の「拘束」と説明責任
このコードは単なる高速化ではありません。誤差上限 $\epsilon$ を先に固定し、その範囲内でのみ「全体計算」を有限の窓へ閉じることで、計算の加速と監査（第三者再現）を同時に成立させます。
よくある「近似」の言い逃れではありません。誤差は切り捨てではなく拘束され、同じ入力・同じハッシュ・同じ証跡なら、同じ結果が再現されます。AIや量子コンピューティングが加速し、ブラックボックス化が進む現代において、計算の「説明責任」を数学という言語で実装します。
GitHubリポジトリ
精度の検証: 出力結果が許容誤差 $\epsilon$ 以内に「拘束」されていることを確認。
再現性の検証: clone → run → 出力ハッシュ（Fingerprint）の一致を確認。
これだけで「31倍速」と「監査可能性」を同時に検証できます。
あなたのStarが、この数理モデルを「信頼の標準」へと押し上げます。
コメント