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 packageSourceAuthors
Translated routines: oracle_percentile and oracle_alert_level, the reference functions of the certlane testsPTF_AlertLevels.m in matPTFJ. 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.pyPTF_AlertLevels.m and the hazard-curve block of PTF_1_0.mThe 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 pyCSEPW. H. Savran, M. J. Werner, D. Schorlemmer, P. J. Maechling and co-authors
Translated routine: pvand in ling_onesided/double_unc.pypvand.m in the VANDERMONDE libraryJ. 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 testsWritten for BootLoopsCode by Claude
New code in mc: the batching, the multiplicity penalty and the Clopper–Pearson (exact binomial) intervalWritten for BootLoopsCode by Claude
New code: every other moduleWritten for BootLoopsCode 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.

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.

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:

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

CommandWhat 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 selftestThe 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.

RuleReported 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.

FunctionWhat 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.

ModuleWhat it holds
transport.pipe_transportTransport along a route of waypoints with recurrence-majorant tail bounds: configure, run_route, local_leg, mum_eval
transport.pipe_libThe exact recurrence layer under it: configure, build_phi, theta_tower
certify.pipe_vacKrawczyk and interval-Newton engine with forward-mode differentiation over complex balls: newton_center, krawczyk(y, r, prec, digits), class AD
quad.posq, quad.kernel_ioPOSQ's modules, imported from tools/posq/, not copied
contract.gate, contract.manifestWayfinder's digit-agreement check and checksummed input manifests, imported from tools/wayfinder/
contract.mcBatched 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.pyCertified 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.pyValidated 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

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.

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.

ReferenceWhat it supplies
F. Johansson, IEEE Trans. Comput. 66 (2017) 1281, arXiv:1611.02831Arb, the ball arithmetic library
W. Hart, F. Johansson, A. Ahlbäck and the FLINT developers, FLINTThe library that now holds Arb
F. Johansson, O. Benjamin and contributors, python-flintThe Python bindings to Arb
Krawczyk, Computing 4 (1969) 187; Moore, SIAM J. Numer. Anal. 14 (1977) 611; Rump, Acta Numerica 19 (2010) 287The 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; matPTFThe 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: pyCSEPThe 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.mThe solver pvand
Kolipakam, Jordan, Dunn, Greenhill, Bouckaert, Gray and Verkerk, DravLex v1.0, R. Soc. Open Sci. 5 (2018) 171504, doi:10.5281/zenodo.5121580The data from which the counts in QUARTET_COLLAPSE.json are derived

← back to the tools index