collatz-m4m6 パフォーマンス分析レポート

ペア述語分解スキャンと u128 直接演算の速度差の構造的分析
2026-02-08  |  v0.2.0  |  Rust (edition 2021)

1. 要旨

collatz-m4m6 は、コラッツ型写像 T(n) = (xn+1)/2^d の m4/m6 ペア述語分解に基づく解析ツールである。 v0.2.0 では Vec<u64> パックドビット表現と Kogge-Stone 並列プリフィックススキャンを導入し、 v0.1 初期の逐次走査から大幅な構造改善を達成した。

しかし、区間検証（sweep）における実測速度では、 u128 直接演算の約4.4億 nums/s に対し、 ペアscan経由の処理は数桁遅い結果となった。 本レポートではこの速度差の構造的原因を分析し、 ペア述語分解の計算論的意義と今後の展望を述べる。

2. 実測ベンチマーク

2.1 3n+1 区間検証 (50M奇数, n ≤ 99,999,999, max_steps=1000)

Intel Core i7-12650H (Alder Lake, 10C/16T), 64GB DDR5 環境。 Phase1（u128 直接演算）の ON/OFF と GPK 統計収集の ON/OFF の4条件で計測。

u128 のみ（0.113s）と Packed のみ（9.516s）の速度差は約84倍。 3n+1 ではほぼ全数が u128 Phase 1 で完結するため、この差がそのまま出る。 GPK 統計の ON/OFF による差は u128 で約20倍。

2.2 5n+1 区間検証 (50K奇数, n ≤ 99,999, max_steps=1000)

5n+1 は発散系列を含むため、停止時間に到達しない数が存在する。同じ4条件で計測。

5n+1 では発散によりビット長が増大し u128 をオーバーフローするため、 Phase 1 の恩恵が限定的となる。 u128 のみ（1.667s）と Packed のみ（2.118s）の差は1.27倍に縮小。

2.3 単一ステップ命令数の比較

1ステップあたりの命令数を128bit幅で正規化した比較を示す。

3. u128 が圧倒的に速い構造的理由

3.1 ハードウェア乗算器の壁

u128 の演算は CPU の乗算器回路で直接実行される。 Intel Alder Lake の整数乗算パイプラインは 64bit×64bit を 3–4 クロックサイクルで完了し、 128bit 結果をレジスタペアに格納する。 この処理にはメモリアクセスが一切発生せず、パイプラインを止める分岐もない。

これは数十億ドル規模の半導体設計投資が生んだハードウェア最適化であり、 ソフトウェアで組んだビット演算が同じ土俵で競うことは原理的に不可能である。

3.2 コラッツ写像の特殊性: 大数 × 小定数

コラッツ型写像は T(n) = (xn+1)/2^d であり、 x は 3, 5, 9 等の小さな定数である。 これは「大きな整数 × 小さな定数」という乗算パターンに該当し、 多倍長乗算の中でも最も単純なケースとなる。 BigUint × 定数は各 limb に対して MUL + ADC の2命令で済み、O(n) で完了する。 ペアscan も O(n) であるため、漸近的計算量は同一だが、定数倍で BigUint が常に有利となる。

3.3 sweep の実態: ほぼ全数が u128 内で完結

3n+1 の区間検証では、u64 範囲の入力の大多数が平均3–5ステップで初期値を下回り、 停止時間に到達する。この間、値は u128（128bit）を超えることがほとんどなく、 ペアscan（Phase 2）に遷移する数は極めて少ない。 つまり sweep を速くするということは u128 ループを速くするということであり、 packed scan の改善は sweep 速度にほぼ寄与しない。

4. 最適化の経緯

v0.1 から v0.2 にかけて、ペアscan 自体は大幅に改善されている。 しかしそれは sweep 速度の改善ではなく、構造解析の効率化としての改善である。

パックド化により、メモリ効率は8倍、ワード内キャリー解決は約10倍に改善された。 しかし sweep のホットパスは u128 Phase 1 であり、 これらの改善は Phase 2 到達時にのみ効果を発揮する。

4.1 GPK 統計収集の最適化

GPK ON/OFF の切替機構を導入し、統計不要時は Vec<u64> 確保・ストア・popcount・max_carry_chain ループを全スキップする設計とした。 これにより GPK OFF 時の 3n+1 sweep は u128 演算のみとなり、442M nums/s を達成した。 一方 GPK ON 時は accumulate_gpk_u128 のビット逐次ループがボトルネックとなり 22M nums/s に低下する。 この約20倍の差が示すのは、GPK 統計収集コスト自体が演算本体より圧倒的に重いという事実である。

5. クロスオーバーポイントの分析

ペア述語分解は乗算を使わないため、漸近的計算量において構造的優位性を持つ。 ビット幅が十分に大きくなると、直接乗算の超線形コストに対して ペアscan の線形コストが優位になるクロスオーバーが理論的に存在する。

6. ペア述語分解の本質的価値

6.1 構造の可視化: 2³³ 規模検証の GPK 統計

ペア述語分解は、コラッツ写像の1ステップを乗算ではなく 加算器のキャリー伝播として透明に分解する。 その副産物である GPK 分類（Generate/Propagate/Kill）は、 キャリーの生成・伝播・消滅を各ペア位置で定量化し、 数値の成長/縮小メカニズムを統計的に観測可能にする。

3n+1 写像について、3 から 9,999,999,999（≈ 2³³）の全奇数 49.9億個を検証した結果から得られた GPK 統計を示す。

キャリーチェーン長の分布:

G% > K% であるにもかかわらず全数が収束するのは、 G が1ビット高々1の寄与であるのに対し、 d（2^d での除算）が平均的に G の効果を上回るためである。 キャリーチェーン長の分布は 4–5 にピークを持ち、最大は 26 である。 これは、キャリー伝播が局所的に留まり、 長距離伝播が指数的に稀であることを示す。

この知見 — キャリーの局所性、G/K 比率の安定性、チェーン長の幾何分布 — は 乗算ベースのアプローチからは直接得られない構造情報であり、 ペア述語分解の固有の価値である。

6.2 回路化ポテンシャル

Kogge-Stone アルゴリズムは元来ハードウェア加算器の設計手法であり、 ペア述語分解を FPGA/ASIC で実装すれば、 乗算器を経由せずにコラッツ写像の1ステップを加算器の深さ O(log n) で完了できる。 固定幅に制約されない点も利点であり、回路設計上の自然な拡張性を持つ。

ただし、本論文の主張は「最速のコラッツ計算の実現」ではない。 回路化は本手法が加算器構造に直接写像されるという理論的整合性の一例として示すものであり、 ペア述語分解の計算論的意義をパフォーマンス比較に帰結させるものではない。

6.3 GPK 統計収集における実質的優位性

ペア述語分解の実用上の明確な利点は、GPK 統計の取得コストにある。 実測ベンチマーク（セクション2）から、GPK 統計収集の有無による速度差を比較する。

u128 直接演算では、GPK 統計を取得するために乗算とは別のパスで ビット分解を行う必要があり、これが約20倍の速度低下を引き起こす。 一方、ペアscan では GPK はスキャン過程の副産物として自然に得られるため、 追加コストは1.3倍に留まる。

GPK 統計が必要な場面（すなわち本論文の分類検証）での実質的な比較は：

ペアscan は「遅いが構造が見える」のではなく、 「構造を見るならば計算速度をほぼ欠損しない」手法である。

論文が示すのは写像の構造的性質であり、ソフトウェアベンチマークの勝敗ではない。 ペア述語分解は、コラッツ写像を加算器のキャリー伝播として透明に分解し、 GPK 統計という定量的解析手段を演算の副産物として提供する。 これが本ツールの存在意義であり、分類論文の検証基盤としての価値である。

7. 今後の展望

ペアscan の速度改善と、ペア述語分解の構造的価値を活用する方向の両面で展望を整理する。

7.1 sweep 高速化の最有力候補: 篩（ふるい）

GPK 分類に基づく剰余類解析により、 「この剰余類は必ず K 優勢 → 収束確定」という定理が導出できれば、 数学的にスキップ可能な数を事前に除外できる。 これはペア述語分解が速度にも直接貢献する唯一の経路であり、 ツールの存在意義を最も強く正当化する方向性である。

7.2 SIMD による packed scan 高速化

AVX2 (256bit) では4ワード、AVX-512 (512bit) では8ワードを同時処理でき、 Kogge-Stone のワード内演算を SIMD 化すれば理論的に4–8倍の改善が見込める。 ただし sweep のホットパスが u128 である限り、 packed scan の高速化は大きい数のトレース用途に限定される。

7.3 ワード間キャリーの並列化

現在の実装ではワード間キャリーは逐次伝播 （carry_out = carry_after >> 63 → 次ワードへ）である。 ワード間にも Kogge-Stone を適用すれば、k ワードのキャリー解決が O(log k) に改善される。 1000bit 以上の大きい数で有効だが、sweep の u64 入力範囲には影響しない。

7.4 FPGA 実装

ペア述語分解を FPGA 上の加算器回路として実装し、 乗算器なしでの1クロック/ステップ動作を実証することが、 本手法の回路的整合性の検証となる。 Kogge-Stone プリフィックスツリーを並列に配置し、 参照パターンの配線を固定すれば、 任意幅のコラッツステップが加算器の段数（O(log n)）で完了する回路を構成できる。

8. 結論

collatz-m4m6 v0.2.0 の実測速度は u128 直接演算に対して数桁劣る。 しかしこの差は「CPU 乗算器ハードウェア vs ソフトウェアビット演算」という 非対称な比較の結果であり、ペア述語分解のアルゴリズム的価値を否定するものではない。

ペア述語分解が提供するのは、コラッツ写像を加算器のキャリー伝播として透明に分解し、 GPK 統計という定量的解析手段を与えることである。 GPK 統計が必要な場面では、ペアscan のオーバーヘッドは1.3倍に留まり、 u128 演算の20倍のオーバーヘッドに対して実質的な優位性を持つ。

述語体系の話と速度は独立である。 本ツールの価値は、コラッツ写像の構造を可視化し、 分類論文の検証基盤を提供する点にある。 速度はその手段であって目的ではない。