Time and SpaceEfficient Evaluation of Some Hypergeometric Constants.pdf

INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUE 7 0 Time- and Space-Efficient Evaluation of Some 0 2 n Hypergeometric Constants a J 5 2 Howard Cheng — Guillaume Hanrot — Emmanuel Thomé — Eugene Zima — Paul ] C S Zimmermann . s c [ 1 v 1 5 1 1 0 N° ???? 7 0 / Janvier 2007 s c : v Thème SYM i X r a ap por t d e r e c h e r c h e Time- and Space-Efficient Evaluation of Some Hypergeometric Constants Howard Cheng∗ , Guillaume Hanrot , Emmanuel Thom´e , Eugene Zima† , Paul Zimmermann Th`eme SYM — Syst`emes symboliques Projet Cacao Rapport de recherche n° ???? — Janvier 2007 — 17 pages Abstract: The currently best known algorithms for the numerical evaluation of hyper- geometric constants such as ζ (3) to d decimal digits have time complexity O (M (d) log2 d) and space complexity of O (d log d) or O (d). Following work from Cheng, Gergel, Kim and Zima, we present a new algorithm with the same asymptotic complexity, but more efficient in practice. Our implementation of this algorithm improves slightly over existing programs for the computation of π , and we announce a new record of 2 billion digits for ζ (3). Key-words: Hypergeometric constants, binary splitting, sieve ∗ Department of Mathematics and Computer Science, University of Lethbridge, howard.cheng@uleth.ca † Wilfrid Laurier University, ezima@wlu.