Baller
Baller is the BootLoops package for calculations in ball arithmetic, where every number is stored as a midpoint together with a radius guaranteed to contain the true value. It evaluates expressions, iterations and integrals, continues linear differential equations along a path and tests candidate solutions of systems of equations, returning an enclosure (a ball proven to contain the answer) or an error. The arithmetic is done by Arb, the library of Fredrik Johansson, through the python-flint bindings; Baller adds driver routines, certification tests, consistency checks and source checks around it.
Where it comes from
Fredrik Johansson wrote Arb, which does all the arithmetic and is now part of FLINT. Three parts of vendor/ come from other authors' code. J. Selva and co-authors wrote matPTF, INGV's Matlab code for tsunami forecasting; certlane is a port, into ball arithmetic, of the alert layer of matPTF. W. H. Savran and co-authors wrote pyCSEP; mc follows pyCSEP's simulation code, keeping its sampling statement. pvand is the Björck–Pereyra Vandermonde solver as coded in John Burkardt's VANDERMONDE library. Claude wrote certlane and mc with the authors' code open.
| Part of the package | Source | Authors |
|---|---|---|
Translated routines: oracle_percentile and oracle_alert_level, the reference functions of the certlane tests | PTF_AlertLevels.m in matPTF | J. Selva, S. Lorito, M. Volpe, F. Romano, R. Tonini, P. Perfetti, F. Bernardi and co-authors |
Routines that follow their code: the percentile and alert-level routines of certlane/primitives.py | PTF_AlertLevels.m and the hazard-curve block of PTF_1_0.m | The same authors |
Routines that follow their code: sim_ll_fixed_n, sim_ll_poisson_n and obs_ll in mc | _simulate_catalog and _poisson_likelihood_test in pyCSEP | W. H. Savran, M. J. Werner, D. Schorlemmer, P. J. Maechling and co-authors |
Translated routine: pvand in ling_onesided/double_unc.py | pvand.m in the VANDERMONDE library | J. Burkardt, after A. Björck and V. Pereyra |
New code in certlane: the enclosures, the treatment of comparisons that the balls cannot decide, and the tests | Written for BootLoops | Code by Claude |
New code in mc: the batching, the multiplicity penalty and the Clopper–Pearson (exact binomial) interval | Written for BootLoops | Code by Claude |
| New code: every other module | Written for BootLoops | Code by Claude |
Please cite the authors' papers when you use these parts of the package. These parts are not affiliated with or endorsed by INGV, the pyCSEP developers or John Burkardt.
What it does
Floating-point code can converge to a wrong answer with no warning. The standard demonstration is Muller's recurrence $x_{n+1} = 111 - 1130/x_n + 3000/(x_n x_{n-1})$ with $x_0 = 2$, $x_1 = -4$. The true limit is 6, but in double precision the sequence settles on exactly 100. In ball arithmetic the radius grows until the result reads "unknown". The three top-level routines build on that.
- Run.
runexecutes an expression or an iteration in ball arithmetic at a working precision you choose. - Solve.
solvereruns at doubled precision until the number of digits you asked for is certified. At its precision cap it raisesSolveRefused, which reports the digits it did achieve. - Render.
renderprints only the digits the radius certifies. A value with none comes back as the marked stringUNCERTIFIED[~mid +/- rad].
One convention differs from Arb's. When an iteration divides by a ball containing zero, the radius becomes infinite and the midpoint continues as the plain fixed-precision value. You still see where floating point would have gone, and the result stays marked uncertified.
Five modules sit below the top level.
baller.quadcomputes definite integrals with a proven error bound through Arb's rigorous integrator, and exposes POSQ asquad.posq.baller.transportcontinues the solution vector of a linear differential equation with polynomial coefficients from point to point in short Taylor steps, each with a proven bound on the truncated tail.baller.certifyturns a numerical candidate into a proven statement with the Krawczyk test: if a certain interval image of a box lies strictly inside the box, the box contains exactly one zero of the system.block_krawczyk, insideballer.certify, handles Jacobiansmatrices of first derivatives of the system of block-arrow shape (many uncoupled diagonal blocks plus a shared border, as in hierarchical statistical models) at a cost linear in the number of blocks. It can also certify the Hessianthe matrix of second derivatives positive definite over the box, which together proves a strict local minimum. Clinch is built on it.
baller.contractis for quantities computed by two routes.dualreturns the primary value only if the two agree to the number of digits you set; otherwise it raises an error carrying both values, and nothing is averaged. The mutation tester edits scratch copies of a source file and confirms that your acceptance command passes on the untouched copy and fails on every edited one.baller.hygieneholds source checks for precision mistakes that recur inmpmathandpython-flintcode, such as a working precision written as a fixed literal. The checks read a Python file and report risky patterns without running it. Beside them are runtime helpers for watching radii and restoring precision.
The largest source check, dps_lint, is for programs that use mpmath. An mpmath number keeps the precision it was created with. Python evaluates module-level assignments, default arguments, decorators and class bodies at import time, usually before the line that raises mp.mp.dps from its default of 15 digits. A constant such as T = mp.mpf(-1)/3 built there feeds a 15-digit value into a 100-digit calculation, and the answer is wrong from about the seventeenth digit with no warning.
The package has these limits:
- Enclosures from
run,solve,quad,transportandcertifyare rigorous provided the functions you pass in are themselves evaluated in ball arithmetic (arb/acbvalues throughout). - The source checks are advisory. A clean report is not a proof.
- The modules under
vendor/are copies of code written for specific studies, included with recorded checksums.baller.verify()raisesVendorTamperErroron any mismatch, so call it first. certlaneis research code for studying the numerical certification of a published hazard computation. It is not a tsunami-warning system and must not be used operationally.- In
python-flint0.8,x**2of anarbball containing zero returns NaN, so writex*xin functions evaluated over a box. - Baller does not do Taylor-model enclosures (see ERAS) and does not wrap or rename Arb's functions (see Arb and mpmath).
The engines in baller.transport and baller.certify were written for the flux vacua study, where the periods are continued in ball arithmetic and the Krawczyk test proves that a box holds exactly one critical point.
Examples
Run Muller's recurrence at a fixed precision, then with the adaptive driver. With the dependencies in place (see Requirements), put the package directory tools/baller/ on the path. The lines are the package's documented quick start:
import sys; sys.path.insert(0, "<your-checkout>/tools/baller")
import baller
baller.verify()
from baller import quad, transport, certify, contract, hygiene
r = baller.run(lambda xp, x: 111 - 1130/x + 3000/(x*xp), x0=(2, -4),
n=100, dps=50)
res = baller.solve(lambda xp, x: 111 - 1130/x + 3000/(x*xp), 16,
x0=(2, -4), n=100)
print(baller.render(res, digits=17)) # -> 6.0000000160995649
r.values holds $x_0$ through $x_{100}$ as balls at 50 digits, and baller.render(r.values[30]) prints 6.0056 because the radius at step 30 is about $10^{-5}$. A few steps later a divisor ball contains zero (r.blown_at records where), and baller.render(r.values[100]) returns a string beginning UNCERTIFIED whose midpoint is near 100. solve tries 30, 60, 120 and 240 digits (res.attempts) and certifies 6.0000000160995649 at 240; with max_dps=60 it raises SolveRefused with achieved_digits == 0.
Compute a definite integral with a proven error bound. From the self-test suite:
from baller import quad r = quad.integral_certified(lambda x, _: 4/(1+x**2), 0, 1, prec_dps=60) right = quad.integral_certified(lambda x, a: x.sqrt(analytic=a), 1, 4, prec_dps=40)
r is a dictionary with 'mid_str', 'rad', 'certified_digits' (at least 50 here; the integral is $\pi$) and 'ball'. An integrand with a branch point, such as the square root in the second call, must forward Arb's analyticity flag, its second argument; a version that ignores the flag returns a finite but wrong ball. Pass max_rad= to make an over-wide result raise BallBlown.
Compare a quantity computed two ways. From the self-test suite:
from baller.contract import dual, Tripwire, DualPathDisagreement v, cert = dual(lambda: 1.2345678901234, lambda: 1.2345678901239, digits=10) dual(lambda: 1.0, lambda: 1.001, digits=6)
The first call returns the primary value unchanged with a record of the digits of agreement. The second raises DualPathDisagreement (three digits of agreement against a threshold of six); the exception carries both values, and neither should be used.
Check an mpmath program for precision set too late. The case from the checker's own documentation: a constant and a default argument built before the precision is raised.
# evaluator.py
import mpmath as mp
T = mp.mpf(-1)/3
def f(x=mp.mpf('0.02')):
mp.mp.dps = 100
return x + T
python3 <your-checkout>/tools/baller/baller/dps_lint.py evaluator.py
It prints two findings, one per line in the form file:line: [where] what :: source line: evaluator.py:3: [module-level] mp.mpf :: T = mp.mpf(-1)/3 and evaluator.py:4: [default-arg in f()] mp.mpf :: def f(x=mp.mpf('0.02')):. A count goes to standard error and the exit status is 1. The repair is to set mp.mp.dps at the top of the module, or to build T inside the function and fill the default at call time.
Routines
| Command | What it does |
|---|---|
python3 tools/baller/baller/dps_lint.py FILE_OR_DIR [FILE_OR_DIR ...] | Checks .py files, and directories recursively, without running them |
python3 -m baller.hygiene lint FILE_OR_DIR [...] | The same checker through the package, with tools/baller on PYTHONPATH |
dps_lint.py --selftest or python3 -m baller.hygiene selftest | The checker's self-test; prints dps_lint selftest: N pass, M fail |
python3 baller/purity_scan.py <list-of-abs-paths.txt> <out.json> | Sorts the numeric literals of the listed Python or C files into a JSON report for a person to review |
dps_lint exits with status 0 when clean, 1 on any finding, and 2 on a nonexistent path, a file that is not .py, an unknown option or no arguments. A clean run prints dps_lint: clean (N file(s)) to standard error. Pass a program together with the modules it imports, because the cross-file rules apply only to files given in the same call.
| Rule | Reported when |
|---|---|
[module-level], [default-arg in f()], [decorator on ...], [class-body ...] | An mpmath constructor, numeric function or lazy constant such as pi is evaluated before the first module-level precision assignment |
[imported-sets-dps] | An import resets the importer's precision |
[import-frozen-const] | A constant in an imported module is frozen at import |
[pre-main-const] | The precision is set only under if __name__ == '__main__': |
[mpdiff-real-branched] | Complex-step mp.diff is applied to a function that branches on real comparisons; a heuristic that can report false positives |
Fixed-literal working precision inside function bodies is outside these rules; lint_fixed_wdps covers part of it.
| Function | What it returns |
|---|---|
verify() | Nothing; raises VendorTamperError if a bundled engine file differs from its recorded checksum |
run(f, x0, n, dps) | A RunResult with .values, .value, .blown_at and .render(); f is an expression, or a step map iterated from x0 to index n |
solve(f, target_digits, x0, n, max_dps) | A SolveResult with .ball, .dps, .attempts and .render(), or raises SolveRefused |
render(x, digits, strict) | The certified digits; an over-request is clamped, or raises RenderRefused with strict=True |
certified_digits(x) | The number of decimal digits the radius certifies |
quad.integral_certified(func, a, b, prec_dps, max_rad) | A dictionary with mid_str, rad, certified_digits and ball; raises BallBlown |
transport.march_lib.step(NUMP, DENP, RK, z0, v0, h, r, K) | One certified Taylor step of $\mathrm{den}(s)\,s\,v'(s) = A(s)\,v(s)$ |
transport.configure_all(...) | Configures pipe_lib and pipe_transport in the required order |
certify.block_krawczyk.block_krawczyk(oracle, center, radius, prec) | The verdict of the Krawczyk test on a block-arrow system; a refusal gives the failing block or border and the margin |
certify.block_krawczyk.certify_local_min(oracle, center, radius, prec) | The same with the positive-definite test, from one evaluation |
contract.dual(primary, oracle, digits) | The primary value and a record of agreement, or raises DualPathDisagreement |
contract.Tripwire(oracle, digits, every) | The same comparison on a deterministic sample of the calls in a loop, called as tw(primary_fn, *args); .certificate() reports the worst agreement |
contract.run_mutation_gate(source_path, mutants, gate_cmd) | A mutation test of an acceptance command; raises MutationHarnessError |
hygiene.lint_files(paths) | The findings of lint_fixed_wdps, lint_ambient_conv, lint_unkeyed_cache and lint_ctx_restore; an empty result means clean |
hygiene.RadiusWatch(bar_digits) | A watcher whose .check(ball) raises RadiusBlowup when the relative radius crosses the digit threshold |
hygiene.ctx_guard(prec, cap) | A context that restores flint's global precision after a block |
Step sizes for step are float, int, arb, acb or fmpq, not Fraction or strings. The first argument of the block_krawczyk functions is your model object with dims, F(x) and H(x) returning ball enclosures; a malformed one raises BlockArrowContractError. In run_mutation_gate, mutants is a list of (old, new) substring edits and the argv list gate_cmd must contain {FILE}.
The four source checks report a working precision written as a fixed literal, an mpf conversion outside a precision block, a cache not keyed on precision, and a change to ctx.prec that is never restored.
| Module | What it holds |
|---|---|
transport.pipe_transport | Transport along a route of waypoints with recurrence-majorant tail bounds: configure, run_route, local_leg, mum_eval |
transport.pipe_lib | The exact recurrence layer under it: configure, build_phi, theta_tower |
certify.pipe_vac | Krawczyk and interval-Newton engine with forward-mode differentiation over complex balls: newton_center, krawczyk(y, r, prec, digits), class AD |
quad.posq, quad.kernel_io | POSQ's modules, imported from tools/posq/, not copied |
contract.gate, contract.manifest | Wayfinder's digit-agreement check and checksummed input manifests, imported from tools/wayfinder/ |
contract.mc | Batched Monte Carlo log-likelihood simulation with Clopper–Pearson intervals on quantiles: sim_ll_fixed_n, sim_ll_poisson_n, obs_ll, quantile_ci |
vendor/certlane/primitives.py | Certified enclosures of lognormal survival probabilities, survival sums, percentile brackets of hazard curves and an alert-level ladder |
vendor/ling_onesided/ | Certified lower and upper bounds on evidence integrals with a positive integrand over quartet pattern counts; data file QUARTET_COLLAPSE.json |
vendor/lgf_monodromy/valmono.py | Validated Taylor-series transport of an order-5 linear differential equation around a closed loop, returning the 5-by-5 monodromy matrix as balls |
The three vendor/ modules in the last rows are used by adding the directory to sys.path and importing. The certlane functions are cert_lognormal_survival, cert_weighted_survival_sum, cert_normalized_weighted_sum, cert_percentile_bracket and cert_alert_level. In certlane, an enclosure that cannot be bounded comes back as the indeterminate ball (INDET(), test with is_indet), never as a number. In valmono.py, call transport_loop with an explicit waypoints list: the loop-geometry helper behind the default is not included and raises ImportError. The monodromy matrix is the linear map that the solutions undergo around the loop.
MANUAL.md in the package directory gives the contract of each module; GUIDE.md beside it gives the Python entry points of dps_lint.
Requirements
- Runs on: Python 3 with
python-flint(Arb),mpmath,numpy,scipy(formc),sympy(for the exact part ofpipe_vac) andpytest(for thecertlanepart of the self-tests). - Install: there is no installer; a clone of the repository is the installation. POSQ and Wayfinder are imported from the same
tools/directory, as laid out in the repository; setBALLER_TOOLS_ROOTif they live elsewhere. - Standard library only:
dps_lintandpurity_scan. The code they check is parsed, never executed, sompmathneed not be installed to rundps_lint.
Self-test. Change to a scratch directory outside tools/ (the script refuses to run inside the source tree) and run
python3 <your-checkout>/tools/baller/battery/battery.py
The script prints PASS or FAIL for each of its 21 parts and one OVERALL line, which begins OVERALL PASS on success. It takes about two minutes and writes BALLER_BATTERY_SUMMARY.json in the current directory.
- POSQ part: it reports a named SKIP if POSQ's C kernel cannot be built on your machine. The kernel is compiled from source at first use, which needs a C compiler and the FLINT development headers.
- Bundled modules: the modules under
vendor/write to the current directory (variables such asVALMONO_OUTandSD_ENGINE_OUToverride it), never intovendor/, where an extra file makesballer.verify()fail.
Source and references
The code is tools/baller/ in the BootLoops repository. Arb is part of FLINT (flintlib.org) and is used unmodified. A longer write-up is available as a PDF.
| Reference | What it supplies |
|---|---|
| F. Johansson, IEEE Trans. Comput. 66 (2017) 1281, arXiv:1611.02831 | Arb, the ball arithmetic library |
| W. Hart, F. Johansson, A. Ahlbäck and the FLINT developers, FLINT | The library that now holds Arb |
F. Johansson, O. Benjamin and contributors, python-flint | The Python bindings to Arb |
| Krawczyk, Computing 4 (1969) 187; Moore, SIAM J. Numer. Anal. 14 (1977) 611; Rump, Acta Numerica 19 (2010) 287 | The interval tests of baller.certify |
| J.-M. Muller and co-authors, Handbook of Floating-Point Arithmetic, Birkhäuser (2010) | The recurrence of the first example |
| J. Selva, S. Lorito, M. Volpe, F. Romano, R. Tonini, P. Perfetti, F. Bernardi and co-authors, Nat. Commun. 12 (2021) 5677; matPTF | The alert computation that certlane ports |
| W. H. Savran, M. J. Werner, D. Schorlemmer, P. J. Maechling and co-authors, J. Open Source Softw. 7(69) (2022) 3658; code: pyCSEP | The simulation for the Poisson L-test, a consistency test of earthquake forecasts, which mc follows |
A. Björck and V. Pereyra, Math. Comp. 24 (1970) 893; J. Burkardt, VANDERMONDE library, pvand.m | The solver pvand |
| Kolipakam, Jordan, Dunn, Greenhill, Bouckaert, Gray and Verkerk, DravLex v1.0, R. Soc. Open Sci. 5 (2018) 171504, doi:10.5281/zenodo.5121580 | The data from which the counts in QUARTET_COLLAPSE.json are derived |