Arb 2.3.0 with faster elementary functions

September 25, 2014

Arb 2.3.0 is now available. The major news is that the core elementary functions (arb_exp, arb_expm1, arb_log, arb_atan, arb_sin, arb_cos, arb_sin_cos) have been rewritten to greatly improve speed at low-to-medium precision (up to a few thousand bits). In this precision range, these functions now all use lookup tables combined with a new Taylor series evaluation method, all implemented using GMP/MPIR mpn arithmetic to keep overhead at a minimum (see the previous writeup about arctangents for details).

Until now, Arb mainly used MPFR for evaluating the elementary functions. The new implementations are up to 3-25 times faster (depending on the function) at very low precision, evening out with the MPFR versions around 4000 bits. At precision higher than about 4000 bits, Arb still falls back to MPFR, with the exception of the exponential function which is computed using an Arb-native implementation of the bit-burst algorithm (the same algorithm as MPFR). Similar higher-precision implementations in Arb for the remaining elementary functions are planned for the future.

Here is a benchmark comparison between Arb 2.3.0 and MPFR 3.1.2 for elementary functions (as well as the gamma and zeta functions), measured on an Intel i7-2600S CPU. The input is $x = \sqrt{2}+1$. The Arb timings include the overhead of computing a propagated error bound based on the error bound of the input variable.

Notably, all the Arb elementary functions have very similar performance to each other, as expected since they use variations of the same algorithm. There is a significant difference between the fastest MPFR function (cos) and the slowest MPFR function (atan). Around double (53-bit) or double-double (106-bit) precision, the cost of evaluating an elementary function in Arb is now down to a few hundred nanoseconds. Obviously, speed at such low precision can still be improved a lot further. Some improvements are also possible between approximately 128 and 4096 bits (perhaps another factor two can be saved in general).

On a few computations I've tested that depend heavily on elementary functions, Arb 2.3 is about twice as fast as Arb 2.2. The difference can naturally be even bigger: a trivial example is the demo program for isolating roots of $\sin(x^2)$, which has gotten five times faster.

Here is a more complete changelog for Arb 2.3.0:

removed most of the legacy (Arb 1.x) modules
updated build scripts, hopefully fixing various issues
new implementations of arb_sin, arb_cos, arb_sin_cos, arb_atan, arb_log, arb_exp, arb_expm1, much faster up to a few thousand bits
ported the bit-burst code for high-precision exponentials to the arb type
speeded up arb_log_ui_from_prev
added mag_exp, mag_expm1, mag_exp_tail, mag_pow_fmpz
improved various mag functions
added arb_get/set_interval_mpfr, arb_get_interval_arf, and improved arb_set_interval_arf
improved arf_get_fmpz
prettier printing of complex numbers with negative imaginary part
changed some frequently-used functions from inline to non-inline to reduce code size

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