ユーザー要望(2026-08-16): https://github.com/okumuralab/algo-c(奥村晴彦 『[改訂新版] C言語による標準アルゴリズム事典』全ソース)にあるような汎用アルゴリズムも Fullseye で実装できるようにしたい。
正直な現状認識: Fullseye は現在 画像アルゴリズム設計 AI(op レジストリ = image/region/ feature/contour/volume の sort、進化 + holdout gate + Python→C codegen)。汎用アルゴリズム (ソート/探索/グラフ/数論/暗号/圧縮)は画像 sort に載らないため、言語・型・codegen の拡張が要る。 これは複数セッションの作業。本 doc はその確定計画(次セッションが full context で実行する正本)。
※ 厳密な網羅は repo の /src を正本とする。
| 分野 | 代表アルゴリズム | Fullseye での受け皿 |
|---|---|---|
| 数値計算 | 方程式(二分法/Newton)、数値積分(Simpson/Romberg)、連立一次(Gauss/LU)、補間(spline)、FFT | 既存 dsp(FFT)+ 新 numeric op 族 |
| 乱数・統計 | Mersenne Twister、分布、統計量 | 新 rng/stat op(決定的 seed) |
| ソート | quick/heap/merge/shell/radix | 新 array sort + seq 型 |
| 探索 | 二分探索、ハッシュ、BST/AVL/B-tree | 新 array/map op |
| 文字列 | KMP/BM/Rabin-Karp、編集距離、正規表現 | 新 text 型 + op |
| グラフ | DFS/BFS、Dijkstra、Warshall-Floyd、MST、最大流 | 新 graph 型 + op |
| 幾何 | 凸包、線分交差、ボロノイ | 既存 pcseg/幾何 + 新 geom2d |
| 数論・暗号 | 素数、GCD、RSA、MD5/SHA、AES | 新 numtheory/crypto(教育用・honest 開示) |
| データ圧縮 | Huffman、LZ/LZW、算術符号化 | 新 compress op |
| DP/探索 | 8-queens、ナップサック、DP | fscript の制御フロー + array |
Fullseye の既存資産を汎用へ拡張する。画像 AI の焦点は薄めない(汎用 op は別 tier / opt-in)。
seq(1-D 配列)/text(文字列)/graph/scalar を追加(ops.py の sort・fslib 型)。docs/FSCRIPT_DECISION.md の A/B 分岐を再検討。engine.to_python/to_c)+ difftest(honest gate: Python が
oracle、C を差分検証)をそのまま流用 → 「C で実装できる」を実測で保証。difftest に食わせ、Fullseye codegen の C と
数値/ビット一致を検証(既存 gate の拡張)。元コードのライセンス(algo-c = 書籍付属、
利用条件を要確認)を尊重し、丸写しでなく仕様から再実装(公開開示ポリシー)。seq/scalar 型 + ソート 3 種(quick/heap/merge)を op 化 + C codegen + difftest。
= 「Fullseye は汎用アルゴリズムも C 生成できる」最小実証。text 型。graph 型。feedback_provenance_research_method)。
ライセンス確認前にコードを取り込まない。最小実証「Fullseye は汎用アルゴリズムも C 生成でき、C 一致を honest 実測できる」を達成。
algo.py。seq(1-D 数列)/scalar(単一実数)型を新設。
画像 ops.REGISTRY には一切触れないため、進化探索・Wave-0 champion pin は無影響(テストで実証)。quicksort(Hoare/median-of-three/Lomuto/明示スタック)・heapsort(Williams
1964 binary max-heap)・mergesort(von Neumann 1945 top-down stable)= seq→seq。加えて scalar
型に役割を与える reduction seq_max/seq_min(seq→scalar、順序非依存で exact)。全て仕様から
再実装(algo-c ソースは丸写しせず・各 op に provenance を明記)。algo.py_fn が同じ文字列を compile、algo_codegen は同じ文字列を standalone .py/.c に emit。
→ テストした oracle と出荷物が drift しない(テスト test_emitted_python_* で実証)。algo_codegen.py(emit_python/emit_c。C は関数 + バイナリ I/O driver = 完全に
compile 可能な単体プログラム)。algo_difftest.py(2 つの実測、deferred skip でない):
(1) Python 参照 == numpy oracle(np.sort/np.max/np.min)、(2) codegen C == Python を
bit 一致(holdout=edge cases 10 + random 40)。これらの op は既存 double を移動/選択するのみゆえ
正しい実装は bit 完全一致(tol=0.0)。zig cc = python -m ziglang cc, ziglang 0.16.0 を pip 導入):
全 5 op で python diff 0.00e+00 / C-vs-Python diff 0.00e+00 / passed=True(実 compile→実 run→bit
比較)。= 「C 一致を honest 実測」を deferred skip でなく本当の測定として達成。test_difftest_compile_error_fails_closed で実証)。fullseye.algo_ops()/run_algo()/algo_to_c()/algo_to_python()/algo_difftest()
(+ api.py)。skill = ~/.claude/skills/image-processing/SKILL.md に「General algorithms
(algo-c tier)」節を追記(サブエージェントから使用可)。tests/test_algo.py(42 件=registry 整合・Python==sorted/oracle・安定性・単一 source
of truth・C bit 一致[toolchain 有時]・compile-error fail-closed・画像 registry 非汚染・facade)。imgevolve.py algo ...)と Studio op ブラウザ tier 表示は次段(P1.5)。
④fscript の配列/procedure 言語化(設計 doc アーキ項 2)は P1 スコープ外(別 track)。本セッションの自作コードへ独立敵対レビュー(Workflow 4 レンズ=算法正しさ / codegen・C 安全 / gate 健全性 / 統合・焦点安全、22 findings)を実施。全件を私が一次コード検証(v11 規律)し、 真の欠陥を修正:
_max_diff_* が max(0.0, nan)=0.0 で NaN 差分を
握り潰し「bit 一致」と偽証していた(実測再現)→ (1)Python×oracle=値比較だが非有限で fail-closed
(inf、tol で通さない)、(2)C×Python=真の bit 比較(IEEE float64 生バイト=符号付きゼロ/NaN ペイロード
も検出) に分離。c_verified フィールドで「実 compile 検証済 pass」と「toolchain 無し unverified
pass」を区別。<= で全等値が片側に。二値=binary mask flatten
が現実的入力・実測 quadratic)→ 3-way(Dutch national flag)partition + median-of-three に Python/C
とも書換(全等値 O(n))。性能ガードテスト(20000 全等値 <2s)追加。heapsort が BSD <stdlib.h> の heapsort() と衝突(macOS/BSD で compile 不能。
zig cc -target x86_64-macos で実測)→ C シンボルを heapsort_asc に改名(mergesort_asc と統一)。
全 op の macOS cross-compile テストを追加(回帰ガード)。2*root+1 int overflow→long long 化 /
driver の len が 32-bit で size_t wrap→SIZE_MAX/sizeof(double) 上限チェック + <stdint.h>。<=不安定への退行を検出)に書換。no-mutation テスト(run(a) が呼び手の
list を破壊しない)も追加。sample_images(studio が runtime import)が pyproject.toml py-modules
欠落=非 editable wheel で消える → 追加(wheel 実ビルドで確認)。pyproject.toml の [tool.setuptools.package-data]
"*" glob が root-level flat の studio_assets/・data/ を wheel に載せられない(studio i18n/op-help/
sample 画像が installed wheel で欠落=既存・要 MANIFEST.in か package 化の設計変更)/ (b)fullseye.__all__
が api の pcseg 系 18 名を欠く(star-import で欠落=既存)。algo tier は無関係(algo* は py-modules で
確実に同梱・facade は整合)。imgevolve.py algo <list|run|emit-c|emit-py|difftest> サブコマンドを追加
(統一 CLI 入口。algo run quicksort --seq 3,1,2 / algo emit-c mergesort / algo difftest all)。
CLI 回帰テスト 2 件 + skill の CLI 例を更新。-ffp-contract=off で FMA 抑止)/ Python-vs-oracle は数値許容差(AlgoOp.tol)で
独立 oracle(simpson=scipy / 求根=残差 |p(root)| / gauss=np.linalg.solve)照合。fail-soft を honest 文書化。text 型は「コードポイント列を float64 で運ぶ」
規約(text_to_seq/seq_to_text)で既存 float64 harness に載せ、新 wire 型を足さずに実現。graph は
[n, m, (u,v,w)*m] パックで既存 harness に載せた(新 wire 型不要)。graph-loop-engineering)文字列アルゴリズム 3 種を algo tier に追加。 「文字列 = コードポイント列を float64 で運ぶ」(Unicode スカラーは < 2^53 ゆえ厳密)で 既存の float64 バイナリ harness に無改造で載る(新 wire 型不要)。値は等値比較のみ(整数コードで 厳密)・位置/距離は厳密整数 → C-vs-Python bit 一致 かつ Python-vs-oracle は EXACT(tol 0)。
strfind(Knuth-Morris-Pratt=失敗関数プレフィックスオートマトン。入力 [m, pattern(m), text] → 全出現
開始位置の昇順リスト・重複出現含む=可変長 KIND_MAP、gauss で作った可変長 wire を再利用) / edit_distance
(Wagner-Fischer/Levenshtein 2 行 DP=KIND_REDUCE・厳密整数) / lcs_length(最長共通部分列長 2 行 DP=
KIND_REDUCE)。全て仕様から再実装(provenance 明記)。fail-soft=空パターン/切詰/パターン>テキストは []、
na<0/切詰は 0.0。text_to_seq(s)/seq_to_text(seq)(コードポイント↔float64)を追加。algo_gate ゲートノードを積む=1 op=1 ノード。3 op を
raptor-worklog add --capability tool → run-once --available tool:command で 無人 done(gate_ok.json 生成)。tests/test_algo.py に strfind/edit_distance/lcs_length のテスト群(既知解・random×独立 oracle・fail-soft・
可変長出力・no-mutation・python exact・C bit 一致)。全スイート 4669 passed / 0 failed(P2 後 4649 から +20)・
ruff clean・mypy 回帰 0。commit + push はこのセッションで実施(ユーザー承認 2026-08-16 就寝時=push ゲート開放)。独立敵対レビュー Workflow(4 レンズ・各 finding を検証エージェントが実コード/実 compile で確認)= 3 findings 全 CONFIRMED(うち 2 件は同一根本原因を別レンズが報告)。一次検証の上で全修正:
int(a[0]) を範囲チェックの前に実行 → C と非一致: edit_distance/lcs_length の Python は
na = int(a[0]) を先に評価(truncation)、C は raw double を先にガード。a[0] ∈ (-1.0, 0.0)(例 -0.5)で
Python は na=0(有効な空文字列)で続行し実距離を返す一方、C は raw guard で拒否し 0.0 → bit 一致契約違反
(ziglang cc で実測: [-0.5,65,66] = Python 2.0 vs C 0.0)。holdout は非負整数 na のみゆえゲートが未検出。int(nan) が ValueError を送出し、op docstring の
fail-soft 約束に反する(C は NaN-false ガードで 0.0/[])。※NaN は「NaN-free 前提」で契約外だが同じガード順序の欠陥。int() の前に移動(not (x >= lo and x <= hi)=
NaN-false)=C を厳密に鏡写し。gauss は元から raw guard で正しかった(同型に統一)。test_string_c_python_parity_on_bad_headers)+ Python fail-soft
no-crash テスト。algorithm-correctness/c-safety の中核指摘は 0(KMP/DP/メモリ安全はクリーン)。graph-loop-engineering)連立一次方程式 Gauss 消去(部分ピボット)を追加し、P2 数値計算を完遂。 ユーザー指示どおり
graph-loop-engineering スキルで raptor work-graph にノード化し、tool driver に無人実行させた(二層方針=
breadth は work-graph の difftest ゲート、敵対 findings 採否・push はセッションの human checkpoint)。
KIND_MAP(map_varlen)= 可変長 seq→seq: 既存 op は sort(入力長=出力長)/ reduce(→1 値)
のみで、連立解(入力 [n, 拡大係数行列 n×(n+1) row-major] → 解ベクトル長 n)は入力長≠出力長。C 境界=
int f(const double* a, int n, double* out) が out に out_len(≤ n)個書き out_len を返す(fail-soft=0)。algo_codegen ドライバに可変長出力モード: KIND_MAP 分岐が {int32 out_len, out_len*float64} を書く
(sort と同じ wire だが out_len≠入力長)。out バッファは入力長で確保(契約 out_len≤n が上界を保証)+
out_len ∈ [0,len] に fail-closed clamp(暴走 op が読み手を over-read させない)。algo.py): Python 参照(stdlib のみ・index-by-index で C を鏡写し)と C 参照を単一 source。
前進消去(部分ピボット=最大 |要素| 行を選択)+ 後退代入。特異(ピボット 0 残存)/ malformed は [] / 0 で
fail-soft(例外なし)。Python/C の FP 演算順を厳密一致(同一除算・subtract-then-multiply・被消去要素を
exact 0.0 代入・abs は inline 符号反転で math.h/-lm 非依存)ゆえ bit 一致。int overflow は n≤46340 +
long long need で防止。np.linalg.solve(独立 oracle・良条件 holdout 34 ケース=対角
優位 + 行置換 + ピボット必須ケース[exact-zero(0,0)・微小(0,0)・3×3 ゼロ対角])→ max abs diff 3.55e-15
(tol 1e-9)。(2)codegen C == Python bit 一致(ziglang cc・-ffp-contract=off)→ diff 0.0 / c_verified=true。
特異/malformed の C fail-soft は Python と完全一致を別テストで直接検証(oracle 非対応領域ゆえ holdout でなく
C-vs-Python 直接比較)。tools/algo_gate.py(再利用可能な gated-stage runner): work-graph の CommandWorker は produces 生成 or
exit0 で done 判定するため、difftest が FAIL 時も JSON を書く現状では fail-open(失敗ゲートが done)になる。
これを塞ぐ = pass 時のみマーカー gate_ok.json を書き、exit code=判定。ノードの produces をマーカーに
向けると失敗ゲートが fail-closed でノード失敗になる。P3 以降の op 波(1 op=1 ノード)にそのまま使える。raptor-worklog add --capability tool --project imgevolve --priority 0(spec=
tools/algo_gate.py --op gauss_solve --out <OUT>、produces=<OUT>/gate_ok.json)→ run-once --available
tool:command で 無人実行 → status=done(exit0・c_verified=true・bit 一致マーカー生成)。tests/test_algo.py に gauss + algo_gate + C fail-soft + require_c テスト群を追加(算法テスト
93 passed)、全スイート 4649 passed / 0 failed(レビュー前 4637 から +12)。私の全ファイル ruff clean・
mypy 回帰 0(既存 baseline=scipy/ziglang stub 欠如と difftest 署名の既存 quirk のみ、私の追加行由来 0)。全
local commit・未 push=human-gate。自作 gauss コードへ独立敵対レビュー Workflow(4 レンズ=numeric 正しさ / C 安全 / gate 健全性 / 統合・被覆、 各 finding を検証エージェントが実行再現)。5 findings 中 4 CONFIRMED を一次コード検証の上で全修正:
find_algo の SystemExit が marker.unlink() より前に
あり、旧 pass の gate_ok.json が残存 → CommandWorker が produces 存在で done 誤判定(op 改名/typo の
再実行で顕在)。→ mkdir + stale-marker unlink を registry チェックの前へ移動(どの早期 exit でも旧 pass を
引き継がない)。回帰テスト追加。np.linalg.solve と 2.2e-14 で一致し PASS(pytest は捕捉するが work-graph が走らせる
algo_gate は difftest holdout ゆえ捕捉しない)。→ ピボット必須ケース(exact-zero(0,0)=[[0,1],[1,0]]・
微小(0,0)=[[1e-14,1],[1,1]]・3×3 ゼロ対角)を holdout に追加=no-pivot mutant を構造不一致→inf→FAIL で
falsify(自前実測確認済)。誤解を招くコメントも訂正。res["passed"] だけでマーカーを書き、graph はマーカー存在のみ読む → 未 compile の C を certify。→
require_c(既定 True)を追加=未検証 pass は gate_ok.json を書かず(gate_unverified.json に diagnostic)
fail-closed。--allow-unverified-c で明示 opt-out、--no-c は Python-only の意図的弱ゲート。test_gauss_c_fail_soft_matches_python
が実 C を compile/run して被覆済 → 検証エージェントが mutation で健全性を確認し 棄却。残る macOS
cross-compile guard の軽微 nit(_ALL→_ALL_OPS で numeric/gauss も被覆)のみ採用。
レビュー後も gauss difftest = python 3.55e-15 / C bit 一致 / c_verified=true・work-graph ノード(hardened)= done。op ブラウザに general(algo)tier を表示。 画像フォーカスを薄めない設計 = general op は seq/scalar の別 計算モデルゆえ read-only(画像パイプラインに入れない)。
api.list_ops(include_algo=False) に opt-in パラメータ + api.algo_rows()(backend=”general”・category “algo:*“・
tier “z_algo” で末尾ソート・halcon None・provenance 付き)。既定は不変(既存 caller は画像 op のみ=焦点維持)。all_ops = list_ops(include_algo=True) で browser に表示 / _op_row が algo フォールバック /
op_signature_detail・op_tooltip が general 分岐(「seq/scalar op・not an image op・run via CLI」+ provenance)/
on_op_selected が general 選択時に Insert・Run once・Help・a/b ノブを無効化 / add_op・run_op_once・
palette が general を flash 拒否。多重防御 = PipelineModel.add_stage が画像 REGISTRY で KeyError fail-closed。op_names を
list_ops(include_algo=True) から導出していたため general 名がコードパーサ/補完/Help ピッカーに伝播 →
apply_program が model.stages= 直書きで add_stage backstop を迂回 → general op がパイプライン侵入。
→ op_names を画像限定に(backend != "general" で除外。browser 表示 all_ops は general 保持)+
apply_program に general stage 拒否ガード(多重防御)。op_names 画像限定化で Help ピッカーからも除外(root fix が両方を解消)。_op_row/signature/tooltip の general 分岐、offscreen で browser が general を表示しつつ Insert 等が
無効・win._op_names が general 除外・コードパーサが general 行を拒否。全スイート緑・ruff net-new 0(新規テストは
clean、studio.py の flash は file の %-format idiom に一貫)・mypy 回帰 0。候補 (d) op 波も実演=全 12 algo op を
work-graph に 1 op=1 ノードで載せ run-once で無人 done。グラフアルゴリズム 3 種を algo tier に追加(候補外だがユーザー「全部進めて」+7-8h 自律に沿うボーナス)。グラフを
入力 seq にパック([n, m, (u,v,w)*m]、無向; dijkstra は src 前置 [n, m, src, ...])し既存 float64 harness に載せる。
graph_components(union-find・連結成分数=KIND_REDUCE 厳密整数)/ graph_mst_weight(Kruskal・最小
全域森の総重み=KIND_REDUCE)/ graph_dijkstra(単一始点最短距離=KIND_MAP・-1.0=到達不可)。決定的 union 則 +
(weight,index) ソート + 最小距離·最小 index の settle 順で C==Python bit 一致。f(a,n,NULL) で out_len 上界を問い、その分だけ確保
してから実書き込みする 2 段プロトコルに変更(gauss/strfind/dijkstra に if(!out) return <bound>)。sd < nd → 小数 nd で src==n が通り out[n] OOB → 整数 n で束縛(sd < n)。1 REFUTED
(到達不可ノード未検証←known-answer/sparse テストで被覆)。numeric/oracle 各レンズの他指摘なし。graph-loop-engineering)汎用アルゴリズム 5 種を algo tier に追加し、algo-c ロードマップ(P1→P5)を完遂。 整数を float64 で運ぶ
(exact < 2^53)ため新 wire 型不要。ビット/整数演算は C 側で unsigned long long/unsigned int に cast して行い、
double へ戻す(結果は < 2^53 で exact)。全 5 op が exact(C==Python bit 一致 かつ Python==独立 oracle tol 0)。
gcd_seq(KIND_REDUCE): 非負整数列の GCD(Euclid・列に fold)。oracle=math.gcd。sieve_primes(KIND_MAP): エラトステネスの篩。入力 [n](長さ 1)→ n 以下の素数昇順=出力が入力長を
大きく超える代表例。size-probe 上界 π(n) ≤ n/2 + 1(2 と奇数の数、log 不要=math.h 非依存)。oracle=試し割り(独立経路)。pow_mod(KIND_REDUCE): モジュラー冪 base^exp mod m(square-and-multiply=RSA/DH の primitive・教育用)。oracle=builtin pow。crc32(KIND_REDUCE): CRC-32(IEEE 802.3・reflected・poly 0xEDB88320)。c_func は crc32_ieee(zlib/BSD の
crc32 シンボル衝突を防御的に回避、cf. heapsort_asc)。oracle=zlib.crc32(zlib C ライブラリ=完全独立)。rle_encode(KIND_MAP): 連長圧縮 →[value, count, ...](出力最大 2×入力、全異なると 2n)。可逆・oracle=itertools.groupby。x == float(int(x)) / x == (double)(long long)x をrange チェックの後に short-circuit(NaN/超過値では cast に到達せず
int(nan) クラッシュ・C の (long long)nan UB を回避)。header 系(sieve の n)は既存 gauss/dijkstra と同じ切り捨て規約。if(!out) return <上界> で
driver が上界を問い→確保→実書き込み。専用テストで C 出力が入力長を超えても heap OOB しないことを実 compile/run で固定。zlib.crc32 と全バイト値・”Hello”・全 256 バイトで一致確認。algo_gate ゲートノード化(1 op=1 ノード・priority 0・tool capability)→
run-once --available tool:command で 5 ノード無人 done(各 gate_ok.json=c_verified/bit 一致マーカー生成)。
= 全 algo op 20 が work-graph ゲート化(15→20)。tests/test_algo.py に P5 テスト群(既知解・独立 oracle 照合 over-random・fail-soft・整数性・
2 段 probe の出力超過・bad-input C-vs-Python parity・no-mutation・python exact・C bit 一致)。全スイート
4700 → 4736 passed / 0 failed(+36)・私の新規ファイル ruff clean・mypy 新規エラー 0(既存 baseline のみ)。自作 P5 コードへ独立敵対レビュー Workflow(4 レンズ=algorithm-correctness / C-safety-codegen / gate-honesty / integration-focus、各 finding を検証エージェントが実 compile/実行で再現、18 agents)。14 raw → 9 CONFIRMED / 5 REFUTED。全 CONFIRMED を私が一次再現(自分で ziglang compile・実行)した上で修正。特筆すべきは「gate が自作の guard を falsify できるか」への深い突き:
passed=False。x >= 0.0 の NaN 棄却が省かれ (long long)NaN UB が実行(自己再現: gcd_seq([NaN,6]) が -ffinite-math-only で 2.0、
gate 既定 -ffp-contract=off では 0.0)。修正=algo_codegen.emit_c に #if __FAST_MATH__ || __FINITE_MATH_ONLY__ →
#error を注入(artifact が silent miscompile せずビルド拒否=fail-closed)+ C コメントの「UB 到達不可」を IEEE 前提と
honest 訂正 + fast-math ビルド拒否テスト追加。n<3 / sieve n_in<1)が falsify 不能 → 全 holdout が固定長ゆえガード削除で
OOB heap read を admit しても全テスト緑。修正=holdout / parity テストに空・短小配列を追加し境界パスを exercise。
honest 開示: black-box 値比較は safety-guard 削除を決定的には捕捉できない(OOB 読み取り値が非決定的)。本来は
ASan が正攻法だが ziglang の ASan は本 Windows 環境でリンク不能(__asan_shadow_memory_dynamic_address 未定義)。
Python 側ガードは決定的に falsify 可能・C 側は境界 exercise + サニタイザで捕捉可(環境制約で自動化は保留)。1 % mod 特殊分岐が falsify 不能(exp==0 かつ mod==1 の同時ケースがどこにも無い)→ holdout に
[7,0,1]・[0,0,1] 追加 + 既知解 assert(再現確認: 1%mod→1 変異が passed=False)。_int_in で op の宣言域を鏡写し→域外は op の fail-soft 値 0.0/[] を返す=クラッシュ回避)。これで
gate 自体が guard 発散を falsify 可能に(再現確認: crc integrality 削除・gcd guard 縮小の各変異が passed=False)。op_help_html フォールスルーは未ガード・全 20 algo op に波及)→ op_help_html に general 分岐追加
(provenance + packed-input 契約 + CLI 実行を表示)+ _op_row/api.algo_rows に desc(op.doc)追加 + 回帰テスト。graph-loop-engineering)幾何アルゴリズム 3 種を algo tier に追加(algo-c ロードマップ P1→P5 完遂後の拡張=P6。当初 TOC の「幾何=凸包/ 線分交差」に対応)。画像 tier の輪郭/領域処理への橋渡しでもある。2-D 点を入力 seq にパックし、整数座標 (各 [-100000, 100000])で全ての向き判定/靴紐和を厳密な整数にする(浮動小数除算を一切使わない)=C bit 一致 かつ Python==独立 oracle tol 0。
polygon_area2(KIND_REDUCE): 靴紐公式で多角形の 2×符号付き面積(符号=巻き方向)。oracle=numpy ベクトル化靴紐
(dot+roll=別コード経路)。honest 域: 座標 ≤1e5・n ≤1e5 で和は最大 2e15 < 2^53(box 周回スパイラルで実測=exact)。point_in_polygon(KIND_REDUCE): 交差数(レイキャスティング)で内外判定。整数の外積で交差を決める(除算なし)。
oracle=巻き数アルゴリズム(交差数とは別手法・両者は単純多角形の厳密内外で一致)。凹多角形も正しい(notch=outside を検証)。
境界(辺上)の点は実装依存と開示し holdout から除外(交差 vs 巻き数が境界で分岐しうるため)。convex_hull(KIND_MAP): Andrew の monotone chain で凸包。出力=lex-min 頂点から CCW 順の頂点列(共線点は除外
=strict hull・scipy と一致)。oracle=scipy.spatial.ConvexHull の頂点集合比較(順序は C-vs-Python bit 一致で別途担保)。
退化(3 未満の distinct / 全共線)は両者 [] で fail-soft。2000 ランダム点集合で scipy と mismatch 0を事前実測。algo_gate ノード化(1 op=1 ノード)→ run-once で無人 done(全 algo op 23 が gate 化)。tests/test_algo.py に幾何テスト群(既知解・scipy/numpy/matplotlib/巻き数の複数独立 oracle 照合・凸性/CCW/点内包の
構造検証・fail-soft・退化・no-mutation・python exact・C bit 一致)。全スイート 4742 → 4765 passed / 0 failed(+23)・ruff clean・mypy 新規 0。2 本の独立敵対レビュー Workflow(各 finding を検証エージェントが実 compile/実行/ストレスで再現)を並行実施:
<=0 monotone-chain pop + hv<3 後置チェックで既に保証される防御的冗長
(両 backend で削除しても等価=200,000 重複多点集合で divergence 0)。検証エージェントが独立に確認=2n size-probe はタイト
非超過上界(放物線入力で out_len=2n)/ ASan+UBSan が 1104 hostile cases でクリーン(out[] 書込 OOB なし・long long 外積
overflow なし)/ C==Python bit 一致・Python==scipy 頂点集合 全一致 / CCW-from-lex-min 順序も test で担保 / qsort 不安定性は
(x,y) 全順序比較子 + 隣接 dedup で無影響(=sorted(set()))。→ dedup が防御的冗長である旨の説明コメントのみ追記(挙動不変)。24bc8ad)。幾何ツールキットを 1 op 拡張: segments_intersect(KIND_REDUCE)= 2 閉線分 [x1,y1,x2,y2,x3,y3,x4,y4] が交差するか
(1.0/0.0)。画像の直線/輪郭解析への橋渡し。CLRS 33.1 の整数 orientation 法(proper crossing = 端点が相手の線を厳密に
またぐ + 4 つの共線 on-segment 特殊ケース)。整数座標 [-100000,100000] で外積は厳密(|cross| ≤ 8e10 が long long に収まる)=
C bit 一致。oracle = sympy.geometry の Segment 交差(記号計算=orientation とは全く別手法)。実測: 固定 8 ケース正解 +
sympy と 2970 ランダム整数線分ペアで mismatch 0(共線重複/T 字/端点共有/near-miss を含む)。退化(点)線分は sympy が
Segment を作れないため holdout から除外(op は一般 orientation ロジックで動くが未 gate=開示)。difftest passed(python exact /
C bit 一致 / c_verified)、work-graph ノード無人 done(全 algo op 24 が gate 化)。
3 レンズ敵対レビュー(検証エージェントが実 compile/実行で再現)= 1 raw → 1 CONFIRMED(MED・gate-honesty)。op 自体は
正しい(sympy と全一致)が、difftest holdout が d1/d3/d4 の on-segment 特殊ケース(端点が相手線分の内部に乗る=共有端点なし)
を単独理由の 1.0 判定として一度も駆動せず、その分岐を落とした wrong op を gate が通す(50 holdout の判定が 1 つも変わらない)。
自己再現で確定(d3+d4 drop 変異が passed=True・[0,0,10,0,3,0,3,5]→0.0 誤り)。修正=各 on_seg 分岐(d1/d2/d3/d4)を単独理由と
する固定 holdout ケース(端点が相手内部・軸並行 4 + 対角 2)を追加 → 各分岐を落とすと difftest が FAIL(d1/d2/d3/d4 すべて
passed=False)を自前確認。既知解テストにも端点-内部 4 ケースを追加。全スイート 4765 → 4772 passed / 0 failed(+7)・ruff clean・
mypy 新規 0。
探索/選択アルゴリズム 2 種を algo tier に追加(幾何から別ドメインへ移り tier を均等化)。比較ベースで任意の (NaN-free)double を扱う=結果は index or 既存要素ゆえ exact(tol 0)・C bit 一致。
binary_search(KIND_REDUCE): sorted 列 [target, v0..v_{n-1}] の target の最左 index(lower bound)、無ければ
-1.0。oracle=bisect_left + 存在確認(独立)。 / kth_smallest(KIND_REDUCE): [k, v0..] の k 番目に小さい値(0-indexed order
statistic)を quickselect(median-of-three pivot・Lomuto)。k 番目の値は順序非依存ゆえ pivot 順が違っても C==Python bit
一致。oracle=sorted()[k](Timsort=別アルゴリズム)。median-of-three で sorted 入力も O(n)(n=40001 が <2s)。algo_gate ノード無人 done(全 algo op 26 が gate 化)。回帰=tests/test_algo.py に P8 群(既知解・
bisect/sorted 照合・O(n²)ガード・fail-soft・no-mutation・python exact・C bit 一致)。ruff clean・mypy 新規 0。2 レンズ敵対レビュー(実 compile/実行検証)= 1 raw → 1 CONFIRMED(LOW・correctness)。正しさ不変だが性能欠陥: kth_smallest の quickselect が単一 pivot Lomuto ゆえ all-equal/低カーディナリティ大入力で O(n²)(median-of-three は重複を 保護しない・n=40000 all-equal で 7.44s、sorted/reverse は高速)。テストは holdout n≤30・計時テストが sorted のみで未捕捉。 姉妹 quicksort は既に 3-way(Dutch flag)partition を使用。修正=kth_smallest を 3-way(Dutch national flag)partition に 書換(equal-band で重複を畳む→all-equal を O(n) に・比較のみ+順序非依存で C==Python==sorted()[k] parity 維持)。自己再現で 確認=all-equal n=40000 が 7.44s → 0.0019s(O(n) 化)・correctness 5000 cases mism 0・difftest bit 一致。計時テストを sorted/reverse/all_equal/few_distinct に拡張(退行を実際にガード)。
統計 op 2 種を algo tier に追加: count_distinct(distinct 値数=整数 count)/ mode_value(最頻値・小さい方が tie 勝ち)。
比較ベース(任意 NaN-free double)・結果は count or 既存要素ゆえ exact(tol 0)。両 op とも copy を sort → run 走査(結果は
順序非依存で C の qsort と Python の sorted が違っても bit 一致)。oracle=len(set()) / collections.Counter(独立機構)。
★proactive 堅牢化: mode_value のゼロ mode で ±0.0 混在時、C の unstable qsort と Python の stable sort で返り値の符号が食い違い
bit 不一致になりうる → + 0.0 で −0.0→+0.0 正準化(他値は不変)で C==Python を堅牢に(rle_encode の signed-zero 開示と同系)。
実測: 各 5000 ランダムケースで oracle mismatch 0・difftest passed(python exact / C bit 一致 / c_verified)。全 algo op 28 が gate 化。
ruff clean・mypy 新規 0。
2 レンズ敵対レビュー(実 compile/実行/変異検証)= 1 raw → 1 CONFIRMED(MED・gate-safety)。正しさ不変だが gate coverage gap:
mode_value の +0.0 正準化を落とす変異を holdout が falsify できない(唯一の signed-zero ケース [0.0,-0.0,0.0] が両 backend で
+0.0-last にソート → 正準化削除でも bit 一致)。コメントが担保と主張する bit-check が正準化を一度も実際に駆動しない。修正=
-0.0 が run 末尾に来ない [0.0,-0.0]・[-0.0,0.0] を holdout に追加(両順序=qsort tie 順に依らず片方は必ず発散)。自己再現で
確認=正準化削除変異が difftest FAIL・現行(正準化済)コードは追加ケースで bit 一致 pass。全スイート 4787 → 4796 passed / 0 failed。
数論 op 2 種を追加(P5 の整数機構の上に・category numtheory を共有)。整数を float64 で運ぶ(exact <2^53)・honest 域で全 モジュラー積が uint64/long long に収まる=C bit 一致 かつ Python==独立 oracle tol 0。
is_prime(KIND_REDUCE): 決定的 Miller-Rabin(witness {2..37})。honest 域 0≤n≤2^32−1(a·a mod n が uint64 に
収まり witness set が決定的=n<3.3e24 まで primality 証明)。oracle=sympy.isprime。★Carmichael 数(561/1105/1729/2465…)を
正しく合成判定。 / modular_inverse(KIND_REDUCE): 拡張ユークリッドで a^−1 mod m(gcd≠1 は −1.0)。域 a≤2^53・m≤2^53(Bezout
係数は不変量 |q·s|=|old_s−new_s|≤2m で long long に収まる)・m=1→0。C の truncated mod を [0,m−1] に正規化(+m)して Python の
floor mod と一致。oracle=builtin pow(a,−1,m)。2 レンズ敵対レビュー(実 compile/実行/変異検証)= 1 raw → 1 CONFIRMED(MED・c-safety-gate)。op 自体は正しく overflow-safe
(353 敵対ケースで検証)だが、modular_inverse の holdout が宣言域 2^53 を駆動せず(in-domain m が ~1e9 止まり)、C の
long long→int 幅縮小変異(2^53 域を壊す)が gate を bit 一致で通過。姉妹 pow_mod(base=exp=2^53 をピン)/ gcd_seq(2^53 ガード端)/
is_prime(near-2^32)は同種変異を捕捉するのに modular_inverse だけ未対応。修正=2^53 端ケース([2, 2^53−1] coprime→inverse・
large coprime near 2^53・[2^52, 2^53] both even→−1)を holdout に追加(Bezout 演算が |q·s|~2m~2^54 を駆動)。自己再現で確認=
long long→int 変異が difftest FAIL・baseline は bit 一致 pass。oracle(pow)は既に対応済ゆえ holdout のみ追加。全スイート緑。
ビット操作 op 2 種を追加: xor_reduce(全要素の bitwise XOR)/ popcount_total(全要素の 1 ビット総数=Kernighan)。
非負整数を float64 で運び、域 [0, 2^53−1] で全値を 53 ビットに収める(XOR 結果も < 2^53=exact・popcount は小さい整数)=
C bit 一致 かつ Python==独立 oracle(functools.reduce(operator.xor) / builtin int.bit_count()=Kernighan とは別機構)tol 0。
両 op passed=True・python exact / C bit 一致 / c_verified。各 3000 ランダムケースで oracle mism 0 を事前実測。fail-soft=負/非整数/≥2^53→0.0。
全 algo op 32 が gate 化。ruff clean(FURB161 で bin().count('1')→.bit_count() 化)・mypy 新規 0。
2 レンズ敵対レビュー Workflow(correctness + gate-safety、wf_7d130631-c0f)= findings 0(欠陥なし)。レビュアー1 は
{findings:[]}、レビュアー2 は「ゲート mutation testing(実装を壊してゲートが捕まえるか)」の最中に window 圧縮で中断
(結果未産出)。規律に従い、死んだ background を蘇生せず、私が同じ mutation test を一次検証で完遂: xor_reduce/popcount_total
の代表 7 変異(空初期化 acc=1 / OR 誤用 / 2^53 域境界 off-by-one / 負ガード除去 / Kernighan→shift[popcount≠bitlength] /
+2 誤り / 2^53 admit)を holdout に対し実行 → 全 7 変異を独立 oracle が捕捉(oracle_err > 0)。結論=P11 ゲートは
falsifying・確定欠陥なし(fed093a は正当・follow-up commit 不要)。
数論 op 1 種を追加(P5 の整数機構 + P10 の Bezout 不変量の上に・category numtheory を共有=P5+P10+P12)。
extended_gcd(KIND_MAP): 入力 [a, b](非負整数 ≤ 2^53)→ 出力 [g, x, y](厳密 3 値、a·x + b·y = g = gcd(a,b))、
域外は [] fail-soft。反復版 two-variable sweep で係数を計算。係数は厳密(不変量 |q·s| = |old_s − new_s| ≤ 2·max(a,b) ≤ 2^54
が C の long long に収まる)ゆえ C == Python bit 一致。domain は [0, 2^53] inclusive(2^53 は exact・係数 |x|,|y| ≲ 2^52 も
float64 で exact)。
a·x+b·y==g」の恒等式検証では符号/正準形の食い違いを
gate が falsify できない。→ oracle は独立な再帰版拡張ユークリッド _ext_gcd_rec(別コード経路)で (g,x,y) を計算し要素一致。
反復版と再帰版は同一 canonical 係数を返す(再帰を展開すると反復になる=数学的に一致、[0,b]/[a,0]/[0,0]/等値の全端も一致確認)。a·x+b·y==g==math.gcd(a,b) 恒等式(bignum で独立検算)失敗 0。fail-soft=短小/非整数/負/NaN/>2^53 → []。[35,15]→(5,1,-2) 等 + coprime/非 coprime + 等値 [7,7] + 片方 0
([0,5]/[5,0]/[0,0])+ a=1 + 2^53 域端([2, 2^53−1] coprime・large coprime near 2^53・[2^52, 2^53] gcd 2^52・
[2^53, 6] inclusive 上端)+ 域外 fail-soft(短小/>2^53=[2^53+2,3]/非整数/負/NaN)+ random 48。algo_difftest --op ゲートノード化(1 op=1 ノード・priority 0・tool capability・
produces=gate JSON)→ run-once --available tool:command で 無人 done(passed:true・c_verified・bit 一致マーカー生成)。
= 全 algo op 33 が work-graph ゲート化(32→33)。tests/test_algo.py に P12 群(既知値・Bezout 恒等式 random×5000・独立再帰 oracle 一致 random×5000・fail-soft・
category grouping[numtheory=P5+P10+P12]・difftest python exact・C bit 一致)。全スイート 4827 passed / 0 failed(test_algo.py
単体 260)・私の全変更 ruff clean・mypy 新規 0(origin/master=15 と同数=net-new 0)。3 レンズ敵対レビュー Workflow(correctness / c-safety+gate-honesty / integration、各 finding を検証エージェントが実 compile/
実行の mutation で再現、5 agents・125 tool uses)= 2 raw(同一根本原因)→ 1 CONFIRMED(MED・gate-cannot-falsify)。op 自体は
正しい(200k + 全端で検証・再帰 oracle と非発散・in-domain で long long overflow なし)が、difftest holdout の域外ケースが全て
operand a 側([2^53+2,3]/[2.5,7]/[-1,7])で、唯一の bad-b ケース [7,NaN] は NaN が bd>=0.0 で短絡し b の 3 ガード節を
一つも単独駆動しない → b 側ガードの片側退行(a/b はコピペ対称ゆえ plausible)が両ゲート半分を通過(P5/P7/P9/P10 と同じ gate-coverage
教訓)。自己再現で確定: bd>=0 / bd<=2^53 / bd==int を _PY/_C 両方から削除 → 全て passed=True(MISSED)、対称な a 側削除は
全て passed=False(CAUGHT・a の域端が holdout にあるから)。修正=[valid_a, finite_bad_b] ケース([3, 2^53+2]・[7,-1]・[7,2.5])
を holdout と fail-soft テストに追加 → 再実測で b 側 3 削除が全て CAUGHT(passed=False, pydiff=inf)・baseline は 70 cases で bit 一致
pass。★検証エージェントの honest 訂正を採用(finding の過剰主張を却下): 「bd<=2^53 削除は b=2^62 で C long long overflow UB」は
不正確 — b=2^62 で C(long long)と Python(bignum)は bit 一致(overflow なし)。真の誤りは出力の精度損失(Bezout 係数が > 2^53 で
float64 に厳密表現できず a·x+b·y==g が破れる)であり、b<=2^53 上限はこの精度を守る。機構は誤りだが欠陥と remedy は成立=採用。
計算幾何を 1 op 拡張(P6/P7 に続く geometry 第2弾): closest_pair(KIND_REDUCE)= 2-D 整数点群の最小 2 乗距離を
分割統治(CLRS 33.4)で求める。入力 [x0,y0,x1,y1,...](2n 個・整数座標 [-1e5,1e5])→ 出力=最小 2 乗ユークリッド距離
(整数厳密)。2 乗距離のみ(sqrt なし)ゆえ long long/整数 float64 に閉じ、C==Python bit 一致。最大 2 乗距離 = (2e5)²×2 = 8e10
< 2^53=exact。fail-soft=点 <2(n<4)/ 奇数長 / 座標が非整数・[-1e5,1e5] 域外 → -1.0。
(yj−yi)²<d の間だけ=7 近傍上界)。base(m≤3)は総当り。重複点(dist 0)は
同一 x が隣接ソートされ、分割線跨ぎでもストリップが拾う。C は CpPt 構造体 + cp_rec 再帰 + cp_cmp_x/cp_cmp_y(qsort)を
op.c_code 内に定義(codegen は c_code を verbatim 挿入するため static helper 可)。ストリップバッファは 1 本を再帰間で共有
(子が先に完了=post-order ゆえエイリアス無し)。再帰深さ ~log2(n)(n=1e5 で 17)=スタック安全。algo_difftest --op ゲートノード化(1 op=1 ノード)→ run-once で無人 done。
= 全 algo op 34 が work-graph ゲート化(33→34)。tests/test_algo.py に P13 群(既知値・総当り一致 random×4000・fail-soft[両座標スロット]・category grouping
[geometry=P6+P7+P13]・difftest python exact・C bit 一致)。全スイート 4834 passed / 0 failed(+7)・ruff clean・mypy
新規 0(origin/master=15 と同数)。敵対レビュー結果=下記(1 CONFIRMED を自己再現・修正)。3 レンズ敵対レビュー Workflow(correctness / c-safety+gate-honesty / integration、各 finding を検証エージェントが実 compile/
実行の mutation で再現)= 3 レンズが同一根本原因に収束 → 1 CONFIRMED(severity=私の初期評価 MED / 検証エージェントは HIGH
=gate-honesty 失敗[gate が誤 op を green-light]を重く見た。honest 開示として両論併記・修正内容は同一)。op 自体は正しい(30k+16k
敵対ケースで総当りと mism 0)が、difftest holdout が strip の y-scan を immediate neighbor(j==i+1)より先へ駆動しない →
strip 前方走査を j==i+1 のみに切り詰める regression を gate が falsify できない(7 近傍定理は「高々 7」であって「1」ではないため、
y 順で非隣接な最近ペアが実在しうる)。自己再現で確定: 走査を range(i+1, min(i+2, sc)) に切り詰めた mutation を _PY/_C 両方に
適用 → passed=True(MISSED)。falsify する最小ケースを整数格子で探索し発見(例 [0,-6,-2,-2,4,-3,-5,3]= 最近ペアが y 順で
2 つ離れる → full/総当り 20 だが j==i+1-only は 25)。修正=strip 内で最近ペアが y-sorted で非隣接になる 3 ケース
([0,-6,-2,-2,4,-3,-5,3]→20 / [-4,5,-1,-3,0,-1,3,-3]→5 / [-1,-6,-1,0,-5,-4,1,-4,4,4]→8)を holdout と既知値テストに追加 →
再実測で j==i+1-only mutation が CAUGHT(passed=False, pydiff=12)・baseline は 61 cases で bit 一致 pass・他 5 mutation も回帰
なし。既存の 6 mutation(strip 省略/sq y 無視/座標上下限/整数性/空 strip)に加え strip 走査深度も falsify 可能に(P12 の gate-coverage
教訓を geometry の strip 走査へ拡張)。
データ圧縮を 1 op 拡張(P5 rle_encode に続く compress 第2弾): huffman_cost(KIND_REDUCE)= 記号頻度 [f0,f1,...]
(非負整数 ≤2^40)に対する最適プレフィックス(Huffman)符号の最小総コスト=全内部ノードの結合重みの和(=Σ freq×符号長)。
★核心=最適コストは tie 不変(記号ごとの符号長は tie 破りで変わるが、総コストは頻度多重集合で一意)ゆえ C と Python が等重み要素を
違う順で取り出しても総和は同一=bit 一致が綺麗に成立。整数を long long で運ぶ(域ガードで < 2^54 に束縛=overflow なし)。
[2^40]×1024(合計 2^50<2^53 で上流通過・コスト~2^53.3 で merge bail)が単独駆動=falsify 可能。[2^40]×1024 が
falsify) / マージが x2 を落とす / n==1 が 1.0 を返す の 6 値分岐変異を全て捕捉(passed=False)。algo_difftest --op ゲートノード化(1 op=1 ノード)→ run-once で無人 done。
= 全 algo op 35 が work-graph ゲート化(34→35)。tests/test_algo.py に P14 群(既知値・heapq 一致 random×5000・fail-soft/overflow・category grouping[compress=P5+P14]・
difftest python exact・C bit 一致)。全スイート 4841 passed / 0 failed(+7)・ruff clean・mypy 新規 0(origin/master=15 と同数)。3 レンズ敵対レビュー Workflow(correctness / c-safety+gate-honesty / integration、各 finding を検証エージェントが実 mutation で再現)= 3 CONFIRMED(いずれも overflow bail 境界の gate-coverage・op 自体は正しく tie 不変も 50k+4k+20k で確定済)。correctness 系の指摘 0 (tie 不変 claim・two-queue の最適性は堅牢)。CONFIRMED は全て「merge-total>2^53 の fail-soft 境界」の網羅:
[2^40]×837(cost 8997303650091008 ≈ 2^52.998・VALID・厳密返却)+ [2^40]×838(cost > 2^53 → -1.0)を
holdout に追加し閾値を 2^53 の ±~1e13 にタイト固定 → 再実測で threshold 絞り変異(2^53→2^50・→8e15)が全て CAUGHT。既知値テストにも
837/838 を追加。>→>= off-by-one 未捕捉 → WITNESS で修正: 当初「freq ≤ 2^40 では cost が正確に
2^53 にならない」と開示しかけたが、検証エージェントが construction を発見=2^16 個 × freq 2^33(= 2^33 ≤ 2^40)は各深さ 16 で
cost = 2^16 · 2^33 · 16 = ちょうど 2^53。2^53 は表現可能ゆえ VALID(2^53 を返す)で、>= 変異はこれを誤って -1.0 に落とす。自分で
一次検証(bignum で cost==2^53 確認・op が 2^53 返却・total_freq=2^49<2^53 で上流通過)の上、この witness ケースを holdout と既知値
テストに採用 → >→>= off-by-one が falsify 可能に(この 1 値境界を単独で pin)。敵対レビューが gap だけでなく fix そのものを
発見した好例(私の当初の「到達不能」判断を反証)。total_freq > 2^53 guard branch が未駆動/非 falsify = honest 開示: これは「頻度合計自体が long long を溢れさせる極端
n(>~4M 記号)」への safety guard。現実的 n では merge bail が同じ -1.0 を返す(削除しても long long overflow せず結果不変)ため値比較で単独
falsify できない(P5 の OOB ガード開示と同型)。極端 n の holdout は非現実的に遅いので追加しない。探索/選択を 1 op 拡張(P8 binary_search/kth_smallest に続く search 第2弾・DP/patience sorting の新アルゴリズム族):
lis_length(KIND_REDUCE)= 任意の NaN-free double 列の最長狭義増加部分列(LIS)の長さを patience sorting で求める。
比較のみ(値に算術を施さない)ゆえ長さは配列固有で一意=C==Python bit 一致。tails[k] に長さ k+1 の増加部分列の最小末尾を持ち、
各要素で tails[mid] < x(bisect_left・狭義)位置を置換 or 末尾拡張(O(n log n))。空→0.0、NaN 混在→-1.0 fail-soft(x != x で検出)。
dp[i]=1+max(dp[j]|j<i,a[j]<a[i])
=patience sorting と別コード経路)diff 0.0(exact) / codegen C==Python bit 一致 diff 0.0。事前実測=40k ランダム(整数+float・
小レンジで tie を大量発生=狭義比較を駆動)で DP と mism 0。<→<=(非減少=別答)/ NaN ガード削除 / 二分探索方向反転 の 3 変異を全て捕捉
(passed=False)。全同一 [2,2,2,2]→1 と重複交互ケースが狭義比較を単独駆動、NaN holdout がガードを駆動。[3,1,2,4]→3・[5,4,3,2,1]→1・全増加→n・空→0・単一→1)+ 全同一→1(狭義で重複非伸長) + 重複交互 +
-0.0/+0.0 等値 + ±inf + float の tie + NaN を先頭/中央/末尾で fail-soft + ランダム(整数 tie 多め + float)。algo_difftest --op ゲートノード化(1 op=1 ノード)→ run-once で無人 done。
= 全 algo op 36 が work-graph ゲート化(35→36)。tests/test_algo.py に P15 群(既知値・DP 一致 random×5000・NaN fail-soft[3 位置]・category grouping[search=P8+P15]・
difftest python exact・C bit 一致)。全スイート 4848 passed / 0 failed(+7)・ruff clean・mypy 新規 0(origin/master=15 と同数)。3 レンズ敵対レビュー Workflow(correctness / c-safety+gate-honesty / integration、mutation 検証)= findings 0(全レンズ指摘なし)。
patience sorting の狭義比較・NaN ガード・tails バッファ安全・O(n²) DP oracle の独立性・holdout の狭義単独駆動を検証し、falsify 可能な
欠陥は検出されず。事前の mutation 3/3 捕捉(狭義 <→<=/NaN ガード/二分探索方向)と 40k DP 一致で gate は堅牢。
統計を 1 op 拡張(P9 count_distinct/mode_value に続く stat 第2弾): count_inversions(KIND_REDUCE)= 任意の NaN-free double 列の
転倒数(i<j かつ a[i] > a[j] の狭義ペア数)を計数マージソートで O(n log n)。比較のみ(値に算術なし)ゆえ count は配列固有で一意
=C==Python bit 一致。マージ時に右列を先取りするたび残りの左列数を加算(古典)。count は非負整数ゆえ -1.0 が safe sentinel: NaN→-1.0
fail-soft、空/単一→0.0。等値は転倒でない(tie で左を先取り=arr[i] <= arr[j])。
<=→<(等値を転倒に誤計上)/ inv 計数 off-by-one / NaN ガード削除 / 非計数(inv=0)
の 4 変異を全て捕捉(passed=False)。全同一 [2,2,2]→0 と重複ケースが狭義比較を単独駆動。[2,1,3]→1・[3,1,2]→2・空/単一→0)+ 全同一→0(狭義) + 重複(sorted→0・
[2,1,2,1]→3)+ -0.0/+0.0 等値(両順)+ ±inf + NaN を先頭/中央/末尾で fail-soft + ランダム(整数 tie 多め + float)。algo_difftest --op ゲートノード化(1 op=1 ノード)→ run-once で無人 done。
= 全 algo op 37 が work-graph ゲート化(36→37)。tests/test_algo.py に P16 群(既知値・総当り一致 random×5000・NaN fail-soft[3 位置]・category grouping[stat=P9+P16]・
difftest python exact・C bit 一致)。全スイート 4855 passed / 0 failed(+7)・ruff clean・mypy 新規 0(origin/master=15 と同数)。
敵対レビューは worktree 隔離で実行(P14 で
レビューエージェントが対象 repo の algo.py を mutate した教訓=commit 後に隔離 worktree でレビュー→結果は follow-up)。★worktree 隔離レビューの初適用が成功: 3 レンズ × 隔離 git worktree(各エージェントが cd76da0 から自分専用の copy を作り mutation) → 本 repo の algo.py は終始 clean(検証エージェントも「real repo は read only・隔離 worktree で mutation・後始末済」と明記)。P14 の 汚染問題を構造的に解消。結果=2 CONFIRMED(両 LOW)・correctness 系 0(op は正しい):
long long→int に縮小する変異が gate を通過(shipped は正しく long long)。自己再現で確定(int 縮小変異が passed=True・
n=65537 の狭義降順で真値 2147516416 > INT_MAX を int が -2147450880 に wrap)。修正=(1) 独立 Fenwick(BIT)版オラクル
_fenwick_inversions(O(n log n)・マージソートと別アルゴリズム=O(n²) 総当りが遅すぎる大 n を検算可)を追加、(2) 狭義降順
witness(n=65537, 転倒数 2147516416 > INT_MAX) を holdout+既知値テストに追加 → 再実測で int 縮小変異が CAUGHT(passed=False)。[inf,1,-inf] に -> 2 と注記していたが実際は 3(全 3 ペアが転倒)。gate は oracle と比較(3 で
一致)ゆえ誤実装は通さない=注記のみの不正確。修正=コメントを -> 3 に訂正(op/oracle/Fenwick すべて 3 で一致を確認)。検索/最適化を 1 op 拡張(P8 binary_search/kth_smallest・P15 lis_length に続く search 第3弾): max_subarray(KIND_REDUCE)= 整数値 double 列の
連続部分列の最大和を Kadane の O(n) リセット走査(cur = max(0, cur+x); best = max(best, cur))で。空部分列を許容(和 0)ゆえ答は常に ≥ 0
(全負→0.0)=-1.0 が safe sentinel。整数域(各 |x| ≤ 2^52 かつ絶対値の走行和 ≤ 2^52)で全ての部分和を厳密整数 < 2^53 に保つ → 答は厳密・
C==Python bit 一致。独立オラクル(全 O(n²) 部分列の総当り最大)は整数加算の結合律ゆえ Kadane と厳密一致。fail-soft -1.0 = NaN / inf / 非整数 /
|x| > 2^52 / 走行和オーバーフロー。
>→>=(exact-2^52 witness で誤 bail)→CAUGHT、(2) リセット if cur<0: cur=0 削除
(接尾和化=誤り)→CAUGHT、(3) 域ガード削除(inf で int() クラッシュ)→CAUGHT、(4) 真の非空 Kadane(空オプション無し)→ 全負 holdout
[-1,-2,-3](正解 0.0)でCAUGHT(err=5.0)、(5) best 更新 >→>=(等価)→ 想定どおり not-caught。[-1,-2,-3] で最大要素 -1.0 を返す=fail-soft sentinel -1.0 と衝突。「空許容ゆえ答 ≥ 0 →
-1.0 が安全」という設計が、まさにこの衝突回避として機能することを mutation test が実証(空許容 = sentinel の健全性の前提)。[-2,1,-3,4,-1,2,1,-5,4]→6・中央ドロップでリセット・
0/-0.0 符号ゼロ・overflow 境界を 2^52 で pin([2^52]=走行和 2^52 → valid(> vs >= を単独 pin)/ [2^52,1]=2^52+1 → -1.0 /
[2^51,2^51]=2^52 → valid / 単一 [2^52+1] > 2^52 → -1.0)・非整数/±inf(先頭/中央)/NaN(先頭/中央/末尾)を fail-soft・ランダム整数。x >= -LIM && x <= LIM が(long long) キャストの前に NaN/inf/巨大を弾く(NaN→int は UB)。累算は long long、走行和 ≤ 2^52
ゆえ全部分和 < 2^63(オーバーフロー無し)、返却 double は best < 2^53 で厳密。algo_difftest --op ゲートノード化(1 op=1 ノード)→ run-once --available tool:command で無人 done
(gate JSON passed=True・c_verified=true)。= 全 algo op 38 が work-graph ゲート化(37→38)。tests/test_algo.py に P17 群(registered_kind・既知値・総当り一致 random×5000・fail-soft/overflow・difftest python exact・C bit 一致)。
honest: 初回フル実行で test_search_ops_registered_kinds が 1 failed(search カテゴリ集合の更新を 2 箇所のうち片方[test_categories_grouping]しか
直していなかった)→ 検知し即修正、再実行で test_algo.py 295 passed / 0 failed・ruff clean・mypy 新規 0(origin/master=15 と同数)。
敵対レビューは worktree 隔離で実行(P16 で確立)。worktree 隔離レビュー(4 エージェント・3 レンズ + 敵対 verify)= 1 CONFIRMED(LOW・gate-honesty)/ refuted 0。検証エージェントは
隔離 worktree で全再現し、本 repo の algo.py 無汚染(status --porcelain は auto の SESSION_SUMMARY のみ)を明記。correctness/integration 系 0(op は正しい):
-O2 -std=c99 -ffp-contract=off(UBSan 無し)でしか
compile しない。C の域ガードを De Morgan 書換 if (!(x>=-LIM && x<=LIM)) → if (x<-LIM || x>LIM)(NaN で両比較 false=NaN がすり抜け)
にすると、次行 x != (double)(long long)x の (long long)NaN が UB で、-O2 では偶然 -1.0 相当に落ちて Python と bit 一致 → gate が passed=True。
だが同じ変異は UBSan/ReleaseSafe build で hard-trap(panic: nan is outside the range of representable values of type 'long long')。
出荷 op は正しい(ガード !(x>=-LIM && x<=LIM) はキャスト前に NaN 拒否)= gate-coverage の穴(production バグではない)。Python 半分は
pin 済(域ガード除去で int(nan) が ValueError → gate は通さず error)= C 側だけ非対称に未 pin。-O2 -std=c99 -ffp-contract=off で: 出荷 guard=NaN→-1.0 正常 / De Morgan+UBSan=
(long long)NaN で trap(finding の panic と一致)/ 出荷 guard+UBSan=trap 無し(NaN をキャスト前に弾く=UBSan-clean)。honest な差分: 私の
standalone は De Morgan+-O2 が exit3 で落ちたが、実ゲート(algo_difftest --op)では検証エージェント報告どおり passed 通過を確認 = -O2 の UB 挙動は
不定でどちらにせよ「-O2 だけでは reject-before-cast を確実には pin できない」。run_c_backend に UBSan pass 追加 — -O2 bit 比較の後に同 C を -fsanitize=undefined -fno-sanitize-recover=all で
再 compile+同 holdout 再 run。NaN/inf/域外値が整数キャストに到達すれば trap → gate fail(UBSan 非対応 toolchain は "unsupported"=neutral で誤検出しない)。
事前実測: 全 38 op が UBSan-clean(trap 0)= 誤 fail 無しで安全に採用可能。修正後実測: 出荷 op=passed=True/ubsan=ok、De Morgan 変異=
passed=False/ubsan=trap(bit は -O2 で True なのに UBSan で捕捉)、他 op 回帰無し。= 「reject-before-cast」を C でも load-bearing に(Python の
int(nan) raise と対称)。回帰 pytest test_ubsan_pass_catches_nan_slip_through_cast 追加。全スイート 295→296 passed / 0 failed・ruff clean・mypy 新規 0。unsharp(sharpen)が [0,1] クリップを欠き、後段の op が Python と乖離(unsharp→gaussian 最大差 6.6e-2、
unsharp→threshold(1.0) で 512 px 反転)。sharpen 出口でクランプ + codegen.py が clip 対象 sort の各 stage 後に
clamp01() を出力(二重の保険)。修正後 ≤ 3e-7。difftest.py が gcc/cc/clang しか探さず この環境では C ゲートが黙って skip していた(= 上の乖離が見えなかった)。
algo_difftest.find_c_compiler()(ziglang fallback)を共用。結果 dict に compiler を記録。n が int32 上限まで無制限(graph_components([2147483000,0]) で 17 GB 確保)→ n ≤ 5,000,000(sieve と同じ
明示上限)、m ≤ 2147483000、Python/C とも。(int) キャストしてから範囲検査(float→int overflow UB、UBSan トラップ)→ 生の double で範囲・整数性を先に検査。
UBSan トラップ 3 → 0、39/39 ビット一致。is_prime / segments_intersect / edit_distance / point_in_polygon / lcs_length(P13〜P18 と同じ規約)。
例: is_prime([4294967311])(定義域外)は 0.0「合成数」でなく −1.0。未変更(衝突の可能性あり、要検討):
pow_mod / gcd_seq / popcount_total / polygon_area2。run_algo が 2^53 超の int を float() で丸めてから定義域検査していた → wire_float() で |x|>2^53 の整数入力は
ValueError(fail-closed)。box の偶数 k が k+1 タップ / k で割っていた(gain 1.25)→ scipy uniform_filter と同じ origin で k タップ。difftest の NaN が max(0.0, nan)=0.0 で合格していた → 非有限は inf として不合格。tests/test_imgops_c.py(新設 11)ほか 35 件追加、5 ファイル 355 passed(C テストはすべて ziglang で実行)。