PaperlayerView exact revision on arXiv

Source-linked AI summary

Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic

Fredrik Johansson

arXiv:1611.02831v1cs.MScs.SCmath.NA

TL;DR

Arbitrary-precision interval arithmetic can suffer catastrophic bound growth and limited function coverage. Arb addresses this with midpoint-radius ball arithmetic, broad numerical support, and precision-aware error handling; the paper reports performance comparable to floating-point arithmetic, while noting limitations in extreme exponent handling and correct rounding.

  • Problem

    Interval bounds can blow up catastrophically, while existing arbitrary-precision interval libraries support only a small set of built-in functions.

  • Method

    Arb uses midpoint-radius intervals for real and complex arithmetic and builds support for special functions, polynomial operations, and precision-dependent error bounds.

  • Results

    Midpoint-radius interval arithmetic can be as performant as arbitrary-precision floating-point arithmetic, with efficiency maintained or improved for special functions and polynomial manipulation.

  • Takeaways & Limitations

    Automatic error tracking can support advanced algorithms while preserving rigorous output in arbitrary-precision computer algebra applications.

  • Takeaways & Limitations

    Arb uses precision-dependent exponent limits to absorb underflow and overflow information loss into error bounds, and its correct-rounding code is not optimized for some asymptotic cases.

Abstract

from arXiv · show

Arb is a C library for arbitrary-precision interval arithmetic using the midpoint-radius representation, also known as ball arithmetic. It supports real and complex numbers, polynomials, power series, matrices, and evaluation of many special functions. The core number types are designed for versatility and speed in a range of scenarios, allowing performance that is competitive with non-interval arbitrary-precision types such as MPFR and MPC floating-point numbers. We discuss the low-level number representation, strategies for precision and error bounds, and the implementation of efficient polynomial arithmetic with interval coefficients.

1 INTRODUCTION

Arb presents midpoint-radius interval arithmetic as an efficient alternative to endpoint intervals, targeting reliable arbitrary-precision computation with support for advanced mathematical operations. Its focus is narrow intervals and automatic error tracking, with performance approaching floating-point arithmetic.

  • Representation: Arb represents real numbers as midpoint-radius intervals [m±r], tracking the midpoint at full precision while using fewer digits for the radius.This representation is presented as an alternative to traditional endpoint-based intervals.
  • Efficiency: At high precision, midpoint-radius arithmetic costs (1+ε) as much as floating-point arithmetic, saving a factor two over endpoint intervals.
  • Motivation: Arb automatically tracks error bounds and aims to remain competitive with arbitrary-precision floating-point arithmetic in computer algebra contexts.The authors frame the overhead of error tracking as small enough to support more complex algorithms with confidence in the output.
  • Scope: Arb primarily targets narrow intervals arising from precise inputs, while wide function-image enclosures remain a secondary focus.Taylor approximations are identified as an alternative for wide intervals, and Taylor expansion support is presently limited to one variable.
  • Scope: The library supports rigorous evaluation of many elementary and higher special functions, including complex-variable implementations.Its purpose is to explain how the core arithmetic facilitates these implementations rather than to describe individual function algorithms.
  • Contribution: The paper substantially revises an earlier Arb report by rewriting the core arithmetic and adding many features.

2 FEATURES AND EXAMPLE APPLICATIONS

Arb provides a broad C-based numerical library built around arbitrary-precision real balls, with complex numbers, polynomials, matrices, and many documented methods. Its implementation includes extensive testing and multiple algorithmic alternatives.

  • Distribution: The library was distributed as portable, thread-safe C software with documentation, a public repository, and an extensive test suite.
  • Library structure: Arb depends on GMP or MPIR, uses MPFR for selected floating-point operations and testing, and extends FLINT’s numerical tower to real and complex numbers.
  • Core types: The core types include arbitrary-precision floats, unsigned floats, real and complex intervals, dense real and complex polynomials, and dense matrices.The real interval type uses midpoint-radius form, while complex numbers use Cartesian pairs of real intervals.
  • API: Each type provides methods that perform operations at a user-specified precision, such as addition of real balls at prec bits.
  • Library scope: The git version described approximately 1850 documented methods, including alternative algorithms for operations such as the Riemann zeta function.
  • Testing: Arb included around 650 test programs that generated 10^3 to 10^6 random inputs and checked consistency between independently computed results.

2.1 Software and language issues

Arb uses C for speed, portability, memory control, and interoperability, but C’s lack of higher-level safety and abstraction increases usability and testing demands. Higher-level interfaces and memory-cleanup conventions address some practical concerns.

  • Advantages: C supports Arb’s speed, fine-grained memory management, fast compilation, portability, and interfacing with other languages.
  • Usability: C’s lack of operator overloading and generic data types makes Arb cumbersome for many users, motivating interfaces for SageMath, Python, and Julia.
  • Safety: C provides poor protection against simple programming errors, so Arb relies on stringent unit testing and Valgrind/Memcheck.Memcheck is used to detect leaks, uninitialized variables, out-of-bounds accesses, and similar mistakes.
  • Concurrency: Arb avoids global state and is thread-safe, but thread-local caches require calling flint_cleanup() before a thread exits to prevent memory leaks.Some methods can use multiple internal threads, although one thread is used by default.

2.2 Numerical evaluation with guaranteed accuracy

Arb evaluates functions with guaranteed accuracy by increasing precision until interval widths or rounding conditions meet the requested goal. Its arbitrary-precision implementations are generally competitive with existing software, while correct rounding remains difficult in degenerate cases.

  • Precision control: Precision-increasing loops repeatedly double working precision until the computed interval reaches the requested relative accuracy.The example targets 53-bit relative accuracy and starts at 64 bits.
  • Performance and accuracy: Its C99 double-complex wrapper is not competitive with optimized double-complex implementations but is highly competitive with arbitrary-precision libraries and computer algebra systems.The wrapper targets accurate results across the whole complex domain.
  • Correct rounding: Arb-based implementations can guarantee correct rounding to a variable number of bits across MPFR-supported rounding modes.A termination test checks whether rounding the interval midpoint produces the correct result.
  • Correct rounding: Correct rounding requires special handling for values extremely close to exact floating-point numbers, such as tanh(10000), which is within 28852 bits of 1.Except for such degenerate cases, the Arb-based functions generally run faster than MPFR’s built-in transcendental functions.
  • Validation: Random testing found incorrect results in MPFR 3.1.3 for square roots, Bessel functions, and the Riemann zeta function at normal precisions and inputs.The reported bugs involved mantissa manipulation and error analysis.

2.3 Exact computing

Arb enables exact discrete conclusions from high-precision numerical computations by enclosing results in rigorous intervals. Applications include partition numbers, Hilbert class polynomials, and high-order zeta-related quantities, with major speedups reported for partition computation.

  • General principle: Interval arithmetic can certify discrete results by verifying positivity, negativity, or that an interval encloses exactly one integer.This makes rigorous numerical approximation useful in computational number theory and computational geometry.
  • The partition function: The Hardy-Ramanujan-Rademacher formula computes partition numbers from an infinite series whose sufficiently precise truncation can be rounded to p(n).Past Maple versions incorrectly computed some partition values, illustrating the need for careful evaluation.
  • The partition function: Reimplementing the partition algorithm in Arb made floating-point error analysis nearly trivial and improved speed by a factor two.The improvement partly came from faster transcendental functions and partly from more aggressive optimizations.
  • The partition function: Arb computes the 111 391-digit number p(10^10) in 0.3 seconds and has been used to compute p(10^20), an integer with more than 11 billion digits.The p(10^20) computation took 110 hours and used 130 GB peak memory.
  • The partition function: Partition evaluation exercises arbitrary-precision software across scales, from a few terms at billions of digits to over a billion terms at low precision.For n = 10^20, Arb spends roughly half its time computing π and sinh(x) in the first term to full precision.
  • The partition function: Computing the full partition value before reducing modulo m is the only known practical approach for obtaining residues at huge n.The last digit must be correct, so the full computation requires rigorous accuracy.
  • Class polynomials: Hilbert class polynomials can be constructed by numerically evaluating modular j-functions at algebraic arguments and expanding the resulting product.The polynomial degree is O(|D|), making efficient and precise function evaluation and polynomial arithmetic important.
  • Class polynomials: Arb matches a state-of-the-art floating-point implementation for Hilbert class polynomials while certifying each coefficient by checking that its interval contains a unique integer.The coefficients support applications including elliptic-curve primality proving and cryptographic curve generation.

3 LOW-LEVEL NUMBER TYPES

Arb separates arbitrary-precision midpoints from fixed-precision radii, using dynamic representations and unbounded exponents to support efficient, reliable interval computation.

  • 3.1 Midpoints: Since version 2.0, Arb stores midpoints in arf_t and error radii in fixed-precision mag_t, enabling factor-two speedups at low precision.This specialization improves performance up to several hundred bits despite requiring more code.
  • 3.1 Midpoints: The arf_t representation uses dynamically sized mantissas, so exact dyadic numbers and integers can grow until rounding becomes necessary.Working precision can be changed during an algorithm without modifying each variable.
  • 3.1.2 Exponents: Arb permits arbitrarily large exponents, preventing underflow and overflow while simplifying asymptotic evaluations of special functions and combinatorial numbers.Large exponentials and gamma-function quotients can be evaluated directly without logarithmic rewrites or case distinctions.
  • 3.1.2 Exponents: Precision-dependent exponent limits absorb information loss into interval error bounds when exponents would otherwise consume excessive memory or computation time.This bounds the practical cost of supporting unbounded exponents.
  • 3.1.3 Feature simplifications: Arb avoids global or thread-local numerical state, returning exactness flags and propagating NaNs for domain errors to support referentially transparent library use.The paper characterizes statelessness as a library-design feature, while omitted IEEE 754 or MPFR features could be added through wrappers.

4 ARITHMETIC BENCHMARKS

Arb’s midpoint-radius intervals achieve competitive performance across basic real and complex arithmetic, with especially strong multiplication and transcendental-function results.

  • Benchmark setup: The benchmarks compare Arb with MPFR, MPFI, and MPC on an Intel i5-4300U using normalized operation times for real and complex arithmetic.Table 2 covers real intervals, Table 3 covers complex intervals, and further measurements include recursive factorial products.
  • Real intervals: Arb multiplication is about as fast as MPFR and twice as fast as MPFI for interval arithmetic.Only the midpoint product requires full floating-point work; remaining error-bound operations use cheaper mag_t arithmetic.
  • Real intervals: Arb addition is slower than MPFR at high precision, but fused multiply-add is about as fast as multiplication at low to medium precision.The fused operation benefits matrix multiplication and basecase polynomial multiplication.
  • Real intervals: Although division and square root have high low-precision overhead, Arb’s relaxed mag_t error computations remain cheaper than MPFI’s doubled endpoint evaluations.The comparison concerns the cost of bounding propagated error rather than only the central arithmetic operation.
  • Transcendental operations: Arb’s transcendental pow operation shows a large speedup up to about 4600 bits and remains around 20% faster than MPFR and MPC at higher precision.The paper attributes these results to fast elementary-function and optimized binary-splitting algorithms.

5 PRECISION AND BOUNDS

Arb designs interval extensions around precision-dependent error bounds, prioritizing fast, sufficiently tight enclosures and stable evaluation across difficult input ranges. It uses midpoint evaluation, propagated-radius bounds, functional decompositions, and cutoffs to control cancellation, overflow, and excessive work.

  • Generic error bounds: Arb evaluates the midpoint at the requested precision, bounds propagated error, and adds a tight rounding-error bound to the radius.For addition, the radius is r1 + r2 + εround, with upward-rounded radius operations.
  • Generic error bounds: For complicated operations, Arb chooses interval functions according to evaluation speed and convenience when determining the smallest enclosure is difficult.The design accepts “good enough” bounds until an application demands further optimization.
  • Generic error bounds: A first-order error-propagation strategy evaluates f(m) to p-bit accuracy and bounds variation over the input radius, assuming a suitable derivative bound.For large radii, a direct bound on |f| can also be included.
  • Function evaluation: Arb composes simpler interval operations when derivative bounds are difficult to compute or direct composition remains numerically stable.The implementation aims to capture asymptotic ill-conditioning in elementary prefactors and uses case distinctions over different domain regions.
  • Function evaluation: For large imaginary parts, alternative tangent formulas avoid quotients of large exponentials by using small exponentials added to unit-magnitude numbers.This prevents error-bound blowup and overflow in the relevant regime.
  • Large values and evaluation cutoffs: Arb limits internal evaluation parameters to O(poly(p)) work independent of input value, enabling precision-increasing black-box evaluation loops with controllable termination.Cutoffs scale with precision; trigonometric and exponential evaluations may return crude bounds when arguments become too large.
  • Branch cuts: Arb follows principal-branch conventions for complex functions, representing branch-cut crossings with images that include the jump discontinuity.Users must rewrite formulas when continuity across a branch cut is required, and higher special functions have limited non-principal-branch support.

6 POLYNOMIALS, POWER SERIES AND MATRICES

Arb supports polynomial, power-series, and matrix operations, with polynomial multiplication optimized to balance speed, coefficient-wise accuracy, and changing coefficient magnitudes. Its block-based methods preserve accuracy for difficult power-series inputs while retaining strong performance at high degree and precision.

  • Data structures and operations: Arb provides matrices, univariate polynomials, truncated power series, and associated algebraic, analytic, differentiation, evaluation, and root-isolation operations.Matrix functionality includes multiplication, powering, LU factorization, solving, inversion, determinants, characteristic polynomials, and matrix exponentials.
  • Data structures and operations: Matrix support is rudimentary: most operations use naive algorithms, and eigenvalue-finding support is absent.Characteristic-polynomial roots remain feasible when matrices are not too large.
  • Polynomial and power-series algorithms: Arb switches between O(n2) basecase recurrences for short inputs and Newton-iteration methods based on O(1) multiplications for long inputs.Polynomial composition uses divide-and-conquer, while power-series operations use asymptotically faster algorithms when appropriate.
  • Polynomial multiplication: Schoolbook multiplication gives nearly best-possible coefficient-wise error bounds, whereas Karatsuba and FFT can perform poorly when coefficient magnitudes vary.The problem is pronounced for decaying power-series coefficients, where FFT error is roughly uniform across output coefficients and Karatsuba can amplify errors iteratively.
  • Polynomial multiplication: Arb combines numerical stability with FFT performance using interval-to-floating-point transformations, trimming, coefficient scaling, block splitting, and exact block multiplication.The interval product AB ± (|A|b + a(|B| + b)) is computed using three floating-point polynomial multiplications.
  • Polynomial multiplication: For degrees n < 16, Arb uses the O(n2) schoolbook algorithm; at higher degrees, heuristic scaling and block decomposition accommodate coefficient-height variation.The scaling transformation is particularly effective for power series sharing a finite radius of convergence.
  • Polynomial multiplication: Arb’s tree multiplication achieves nearly 64-bit accuracy for all coefficients at 64-bit precision, while remaining much faster than sequential expansion when n ≫ 10^2.At large n, Arb is about as fast as FLINT for exact computation; 4096-bit precision takes 1.8 s at n = 10^4 and 174 s at n = 10^5.
  • Applications: Arb computes derivatives of nested and special functions to 1000 digits in 0.0006–1.9 seconds and isolates 6710 Airy-function roots in 0.4 seconds.It refines all those roots to 1000 digits in 16 seconds, illustrating the use of fast polynomial arithmetic with automatic differentiation.

7 CONCLUSION

The paper concludes that midpoint-radius interval arithmetic can combine rigorous error tracking with arbitrary-precision performance and low overhead. Arb’s core arithmetic supports efficient higher-level algorithms, while its pragmatic design accepts that no behavior standard currently exists.

  • Conclusion: Arb demonstrates performance comparable to floating-point arithmetic in arbitrary-precision settings while combining asymptotic efficiency with low overhead.The conclusion extends this claim from basic arithmetic to some special-function evaluation and polynomial manipulation tasks.
  • Conclusion: Arb’s efficiency relative to non-interval software is maintained or can improve for higher operations because its core arithmetic supports advanced algorithms.The stated scope includes special functions and polynomial manipulation.
  • Conclusion: There is no accepted standard for midpoint-radius interval arithmetic behavior, so Arb adopts a pragmatic approach that the authors report works well in practice.The paper argues that post-computation interval validation reduces the importance of fine-grained determinism compared with floating-point arithmetic.
Loading 1611.02831v1…