fredrikj.net / blog /

# Arb example programs, rigorous calculus

*September 26, 2013*

I have starting adding example programs to Arb. Right now the following programs are available:

- pi.c – computes $\pi$ to any precision (this is mandatory to have…)
- hilbert_matrix.c – computes determinants of huge Hilbert matrices with adaptive precision
- keiper_li.c – computes the Keiper-Li coefficients (see the previous post on testing Li’s criterion and my new paper)
- real_roots.c – rigorously isolates all single roots of a real analytic function on an interval

See the documentation page for more detailed descriptions and some sample output.

I will talk a bit more about the last example program. It is is based on the module fmprb_calc which I’ve just added to Arb. Quoting from the documentation page:

This module provides functions for operations of calculus over the real numbers (intended to include root-finding, optimization, integration, and so on). It is planned that the module will include two types of algorithms:

- Interval algorithms that give provably correct results. An example would be numerical integration on an interval by dividing the interval into small balls and evaluating the function on each ball, giving rigorous upper and lower bounds.
- Conventional numerical algorithms that use heuristics to estimate the accuracy of a result, without guaranteeing that it is correct. An example would be numerical integration based on pointwise evaluation, where the error is estimated by comparing the results with two different sets of evaluation points. Ball arithmetic then still tracks the accuracy of the function evaluations.

Right now, the *fmprb_calc* module contains a few algorithms for rigorously finding the roots of real analytic functions. I hope to find the time to add numerical integration soon. Expect a complex analysis module to appear in the future too (the complex counterpart should eventually be much more powerful, as it will be able to use the omnipotent Cauchy integral formula and other magic tricks).

For now, using the root-finding routines takes a bit of work. It’s quite difficult to write a black-box algorithm that does what the user expects: you’ll always have some tradeoffs (for example, if convergence seems slow, should it fail early and give the user the chance to try something else, or should it try hard to solve the problem but possibly waste a lot of time; should it be optimized for one type of input or the other?). So my philosophy here is to implement several algorithms that give precise control over what goes on, and let the user connect them in the most appropriate way for a given situation. The real_roots program shows one way to do this. I’m lazily copying its description from the documentation page:

This program isolates the roots of a function on the interval $(a,b)$ (where $a$ and $b$ are input as double-precision literals) using the routines in the *fmprb_calc* module. The program takes the following arguments:

real_roots function a b [-refine d] [-verbose] [-maxdepth n] [-maxeval n] [-maxfound n] [-prec n]

The following functions (specified by an integer code) are implemented:

* 0 – $Z(x)$ (Riemann-Siegel Z-function)

* 1 – $\sin(x)$

* 2 – $\sin(x^2)$

* 3 – $\sin(1/x)$

The following options are available:

`-refine d`: If provided, after isolating the roots, attempt to refine the roots to*d*digits of accuracy using a few bisection steps followed by Newton’s method with adaptive precision, and then print them.`-verbose`: Print more information.`-maxdepth n`: Stop searching after*n*recursive subdivisions.`-maxeval n`: Stop searching after approximately*n*function evaluations (the actual number evaluations will be a small multiple of this).`-maxfound n`: Stop searching after having found*n*isolated roots.`-prec n`: Working precision to use for the root isolation.

With *function* 0, the program isolates roots of the Riemann zeta function on the critical line, and guarantees that no roots are missed (there are more efficient ways to do this, but it is a nice example):

> build/examples/real_roots 0 0.0 50.0 -verbose interval: 25 +/- 25 maxdepth = 30, maxeval = 100000, maxfound = 100000, low_prec = 30 found isolated root in: 14.12353515625 +/- 0.012207 found isolated root in: 21.0205078125 +/- 0.024414 found isolated root in: 25.0244140625 +/- 0.024414 found isolated root in: 30.43212890625 +/- 0.012207 found isolated root in: 32.9345703125 +/- 0.024414 found isolated root in: 37.5732421875 +/- 0.024414 found isolated root in: 40.9423828125 +/- 0.024414 found isolated root in: 43.32275390625 +/- 0.012207 found isolated root in: 48.01025390625 +/- 0.012207 found isolated root in: 49.76806640625 +/- 0.012207 --------------------------------------------------------------- Found roots: 10 Subintervals possibly containing undetected roots: 0 Function evaluations: 3425 cpu/wall(s): 1.22 1.229 virt/peak/res/peak(MB): 20.63 20.66 2.23 2.23

Find just one root and refine it to approximately 75 digits:

> build/examples/real_roots 0 0.0 50.0 -maxfound 1 -refine 75 interval: 25 +/- 25 maxdepth = 30, maxeval = 100000, maxfound = 1, low_prec = 30 refined root: 14.134725141734693790457251983562470270784257115699243175685567460149963429809 +/- 8.4532e-81 --------------------------------------------------------------- Found roots: 1 Subintervals possibly containing undetected roots: 8 Function evaluations: 992 cpu/wall(s): 0.41 0.415 virt/peak/res/peak(MB): 20.76 20.76 2.23 2.23

Find roots of $\sin(x^2)$ on $(0,100)$. The algorithm cannot isolate the root at $x = 0$ (it is at the endpoint of the interval, and in any case a root of multiplicity higher than one). The failure is reported:

> build/examples/real_roots 2 0 100 interval: 50 +/- 50 maxdepth = 30, maxeval = 100000, maxfound = 100000, low_prec = 30 --------------------------------------------------------------- Found roots: 3183 Subintervals possibly containing undetected roots: 1 Function evaluations: 34058 cpu/wall(s): 0.26 0.263 virt/peak/res/peak(MB): 20.73 20.76 1.72 1.72

This does not miss any roots:

> build/examples/real_roots 2 1 100 interval: 50.5 +/- 49.5 maxdepth = 30, maxeval = 100000, maxfound = 100000, low_prec = 30 --------------------------------------------------------------- Found roots: 3183 Subintervals possibly containing undetected roots: 0 Function evaluations: 34039 cpu/wall(s): 0.26 0.266 virt/peak/res/peak(MB): 20.73 20.76 1.70 1.70

Looking for roots of $\sin(1/x)$ on $(0,1)$, the algorithm finds many roots, but will never find all of them since there are infinitely many:

> build/examples/real_roots 3 0.0 1.0 interval: 0.5 +/- 0.5 maxdepth = 30, maxeval = 100000, maxfound = 100000, low_prec = 30 --------------------------------------------------------------- Found roots: 10198 Subintervals possibly containing undetected roots: 24695 Function evaluations: 202587 cpu/wall(s): 1.73 1.731 virt/peak/res/peak(MB): 21.84 22.89 2.76 2.76

Arbitrary-precision ball arithmetic is not ideal for root-isolation: most of the time double precision interval arithmetic would be much faster. But it does work, even if you really try to push it. For example, if you increase the default termination bounds, it will find all the 318309 roots of $\sin(x^2)$ on the interval $1 < x < 1000$ (proving that no others exist) in 25 seconds:

> build/examples/real_roots 2 1.0 1000.0 -maxeval 10000000 -maxfound 1000000 -maxdepth 40 -prec 53 interval: 500.5 +/- 499.5 maxdepth = 40, maxeval = 10000000, maxfound = 1000000, low_prec = 53 ————————————————————— Found roots: 318309 Subintervals possibly containing undetected roots: 0 Function evaluations: 3230804 cpu/wall(s): 25.23 25.256 virt/peak/res/peak(MB): 31.56 38.64 12.54 12.54

Finally, very high precision is no problem (computing a million digits of $\sqrt{\pi}$ as a root of $\sin(x^2)$ finishes in less than 20 seconds):

> build/examples/real_roots 2 1.0 2.0 -refine 1000000 -verbose interval: 1.5 +/- 0.5 maxdepth = 30, maxeval = 100000, maxfound = 100000, low_prec = 30 found isolated root in: 1.875 +/- 0.125 after bisection 1: 1.76953125 +/- 0.0039062 after bisection 2: 1.7723388671875 +/- 0.00012207 newton initial accuracy: 12 newton step: wp = 18 + 10 = 28 newton step: wp = 31 + 10 = 41 newton step: wp = 56 + 10 = 66 newton step: wp = 107 + 10 = 117 newton step: wp = 208 + 10 = 218 newton step: wp = 411 + 10 = 421 newton step: wp = 817 + 10 = 827 newton step: wp = 1628 + 10 = 1638 newton step: wp = 3250 + 10 = 3260 newton step: wp = 6494 + 10 = 6504 newton step: wp = 12982 + 10 = 12992 newton step: wp = 25958 + 10 = 25968 newton step: wp = 51911 + 10 = 51921 newton step: wp = 103816 + 10 = 103826 newton step: wp = 207626 + 10 = 207636 newton step: wp = 415247 + 10 = 415257 newton step: wp = 830489 + 10 = 830499 newton step: wp = 1660973 + 10 = 1660983 newton step: wp = 3321941 + 10 = 3321951 1.77245385[omitting huge string of digits]3729443 +/- 3.9829e-1000007 --------------------------------------------------------------- Found roots: 1 Subintervals possibly containing undetected roots: 0 Function evaluations: 46 cpu/wall(s): 18.3 18.322 virt/peak/res/peak(MB): 35.12 48.81 16.30 29.85

fredrikj.net | Blog index | RSS feed | Follow me on Twitter | Become a sponsor