Author: Fredrik Johansson
Advisor: Manuel Kauers
Second examiner: Paul Zimmermann
Submitted version (February 17, 2014): PDF
I successfully defended my thesis on March 25, 2014. Errata (and possibly a corrected version) will be published here in the future.
The problem of efficiently evaluating special functions to high precision has been considered by numerous authors. Important tools used for this purpose include algorithms for evaluation of linearly recurrent sequences, and algorithms for power series arithmetic.
In this work, we give new baby-step, giant-step algorithms for evaluation of linearly recurrent sequences involving an expensive parameter (such as a high-precision real number) and for computing compositional inverses of power series. Our algorithms do not have the best asymptotic complexity, but they are faster than previous algorithms in practice over a large input range.
Using a combination of techniques, we also obtain efficient new algorithms for numerically evaluating the gamma function $\Gamma(z)$ and the Hurwitz zeta function $\zeta(s,a)$, or Taylor series expansions of those functions, with rigorous error bounds. Our methods achieve softly optimal complexity when computing a large number of derivatives to proportionally high precision.
Finally, we show that isolated values of the integer partition function $p(n)$ can be computed rigorously with softly optimal complexity by means of the Hardy-Ramanujan-Rademacher formula and careful numerical evaluation.
We provide open source implementations which run significantly faster than previously published software. The implementations are used for record computations of the partition function, including the tabulation of several billion Ramanujan-type congruences, and of Taylor series associated with the Riemann zeta function.
Last updated March 27, 2014. Contact: fredrik.johansson@gmail.com.
Back to fredrikj.net