Time- and Space-Efficient Evaluation of Some Hypergeometric Constants

Howard Cheng; Guillaume Hanrot; Emmanuel Thomé; Eugene Zima; Paul Zimmermann

inria-00126428, version 2

Time- and Space-Efficient Evaluation of Some Hypergeometric Constants

Howard Cheng ()^a^, 1, Guillaume Hanrot ()^b^, 2, Emmanuel Thomé ()^b^, 2, Eugene Zima ()^c^, 3, Paul Zimmermann ()^b^, 2

N° RR-6105 (2007)

Abstract: The currently best known algorithms for the numerical evaluation of hypergeometric constants such as $\zeta(3)$ to $d$ decimal digits have time complexity $O(M(d) \log^2 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 $\pi$, and we announce a new record of 2 billion digits for $\zeta(3)$.

a – University of Lethbridge
b – INRIA
c – Wilfrid Laurier University
1: Department of Mathematics and Computer Science
University of Lethbridge
2: CACAO (INRIA Lorraine - LORIA)
CNRS : UMR7503 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
3: Department of physics and computer science
Wilfrid Laurier University

inria-00126428, version 2
http://hal.inria.fr/inria-00126428
oai:hal.inria.fr:inria-00126428
From: Rapport De Recherche Inria <>
Submitted on: Thursday, 25 January 2007 14:24:04
Updated on: Thursday, 25 January 2007 14:24:36

See detailed view

Associated documents

PS :

PDF :

arXiv: cs.SC/0701151

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00126428"><monogr>
<author><persName><forename>Howard</forename><surname>Cheng</surname></persName>
<affiliation>
<orgName type="team">Department of Mathematics and Computer Science</orgName>
<country>CA</country>
<orgName type="institution">University of Lethbridge</orgName>
</affiliation>
</author>
<author><persName><forename>Guillaume</forename><surname>Hanrot</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">CACAO</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Emmanuel</forename><surname>Thomé</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">CACAO</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Eugene</forename><surname>Zima</surname></persName>
<affiliation>
<orgName type="team">Department of physics and computer science</orgName>
<country>CA</country>
<orgName type="institution">Wilfrid Laurier University</orgName>
</affiliation>
</author>
<author><persName><forename>Paul</forename><surname>Zimmermann</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">CACAO</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="m">Time- and Space-Efficient Evaluation of Some Hypergeometric Constants</title><title type="main" level="m">Time- and Space-Efficient Evaluation of Some Hypergeometric Constants</title><imprint><biblScope type="publicationDate">2007-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00126428</idno><idno type="HALFile">http://hal.inria.fr/inria-00126428/PDF/RR-6105.pdf</idno></biblStruct>
</listBibl>
</listBibl>