vvsandClaude Opus 5
de90c7a089
What the tables' totals hid: problem by problem the scheduled projection beats Chandrupatla on APS 87/24/42, exact sign test p = 9e-5, while trailing by 0.7% in total; on CHA Chandrupatla is genuinely better (26 to 9, p = 0.006). The earned projection ties him on APS problems (79/3/71, p = 0.57). Benchmark not yet switched to the library baseline - awaiting Valeri's decision together with the framing of the proposed method. Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
90 lines
3.4 KiB
Python
90 lines
3.4 KiB
Python
"""Audit: does Chandrupatla stop on the same bracket width as everybody else?
|
|
|
|
Found 2026-09-21 on Valeri's challenge "you made a mistake somewhere". Every method in
|
|
the benchmark stops when the bracket is at most xtol wide - ours, bisection, Brent,
|
|
Dekker, TOMS 748 (np.isclose with atol=xtol), SciPy's _chandrupatla (dx < xatol).
|
|
OUR implementation of Chandrupatla does not: it stops on tl = tol/span > 1/2 with
|
|
tol = xtol + 2 eps |x|, i.e. when the bracket is narrower than 2*xtol. The protocol
|
|
already corrects exactly this factor for ITP (epsilon = xtol/2) and did not for
|
|
Chandrupatla, and best_of takes, problem by problem, whichever of the two
|
|
implementations is cheaper - so the looser one wins.
|
|
|
|
Measured here, per implementation and combined, at the benchmark's charging rules:
|
|
ours @ xtol the implementation as benchmarked (stops below 2*xtol)
|
|
ours @ xtol/2 the same code given ITP's correction (stops below xtol)
|
|
scipy @ xtol the library, which already stops below xtol
|
|
best_of as benchmarked, and best_of with the correction.
|
|
Also the final bracket width each actually stops at, to confirm the factor directly.
|
|
|
|
python -u audit_chandrupatla_tolerance.py
|
|
"""
|
|
from __future__ import annotations
|
|
|
|
import math
|
|
|
|
from simroot.baselines import Counter, best_of, chandrupatla, chandrupatla_scipy
|
|
from stage12_validation import XTOL, load, per_problem, totals
|
|
|
|
|
|
def ours_half(f, a, b, xtol, maxfev):
|
|
return chandrupatla(f, a, b, 0.5 * xtol, maxfev)
|
|
|
|
|
|
def final_width_ratio(probs):
|
|
"""Max over problems of (final proven bracket width / xtol) for our implementation,
|
|
reconstructed from the signs it observed."""
|
|
worst = 0.0
|
|
for _s, _pid, f, a, b, _root in probs:
|
|
xs = []
|
|
|
|
def g(x, _f=f):
|
|
v = _f(x)
|
|
xs.append((x, v))
|
|
return v
|
|
try:
|
|
chandrupatla(g, a, b, XTOL, 200)
|
|
except Exception:
|
|
continue
|
|
if len(xs) < 2:
|
|
continue
|
|
(xa, fa), (xb, fb) = xs[1], xs[0]
|
|
lo, hi = min(xa, xb), max(xa, xb)
|
|
flo = fa if xa < xb else fb
|
|
for x, v in xs[2:]:
|
|
if not (lo < x < hi) or v == 0.0:
|
|
continue
|
|
if (v > 0.0) == (flo > 0.0):
|
|
lo, flo = x, v
|
|
else:
|
|
hi = x
|
|
worst = max(worst, (hi - lo) / XTOL)
|
|
return worst
|
|
|
|
|
|
def main():
|
|
probs = load()
|
|
runs = {
|
|
"ours @ xtol (as benchmarked)": chandrupatla,
|
|
"ours @ xtol/2 (ITP's correction)": ours_half,
|
|
"scipy @ xtol": chandrupatla_scipy,
|
|
"best_of, as benchmarked": best_of(chandrupatla, chandrupatla_scipy),
|
|
"best_of, corrected": best_of(ours_half, chandrupatla_scipy),
|
|
}
|
|
out = {}
|
|
print(f"{'Chandrupatla':<34} {'APS':>6} {'solved':>7} {'CHA':>6} {'solved':>7} {'both':>6}")
|
|
for name, m in runs.items():
|
|
p = per_problem(m, probs, 200)
|
|
t, ok = totals(p, probs)
|
|
out[name] = (t["APS"], ok["APS"], t["CHA"], ok["CHA"])
|
|
print(f"{name:<34} {t['APS']:6d} {ok['APS']:4d}/154 {t['CHA']:6d} {ok['CHA']:4d}/45 "
|
|
f"{t['APS'] + t['CHA']:6d}")
|
|
w = final_width_ratio(probs)
|
|
out["max_final_width_over_xtol"] = w
|
|
print(f"\nour implementation, largest final bracket width / xtol over all problems: {w:.3f}"
|
|
"\n(everyone else stops at <= 1; a value up to 2 confirms the looser rule)")
|
|
return out
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|