Fast Multiple-Precision Evaluation of Elementary Functions

TLDR

Efficient evaluation of elementary functions such as exp, log, sin, and cosh is sought, with complexity measured by the number of single‑precision operations required to multiply n‑bit integers. The authors design fast algorithms by applying elliptic integral theory, specifically the arithmetic‑geometric mean iteration and ascending Landen transformations. They prove that any elementary function can be evaluated to relative error O(2⁻ⁿ) in O(M(n) log n) operations, which, using the Schönhage–Strassen bound, reduces to O(n log² n log log n) operations, enabling rapid computation of constants such as π, e, and e^π.

Abstract

Let ƒ( x ) be one of the usual elementary functions (exp, log, artan, sin, cosh, etc., ), and let M ( n ) be the number of single-precision operations required to multiply n -bit integers. It is shown that ƒ( x ) can be evaluated, with relative error Ο (2 - n ), in Ο ( M ( n )log ( n )) operations as n → ∞, for any floating-point number x (with an n -bit fraction) in a suitable finite interval. From the Schönhage-Strassen bound on M ( n ), it follows that an n -bit approximation to ƒ( x ) may be evaluated in Ο ( n log 2 ( n ) log log( n )) operations. Special cases include the evaluation of constants such as π, e , and e π . The algorithms depend on the theory of elliptic integrals, using the arithmetic-geometric mean iteration and ascending Landen transformations.