Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

An amortized-complexity method to compute the Riemann zeta function


Author: Ghaith A. Hiary
Journal: Math. Comp. 80 (2011), 1785-1796
MSC (2000): Primary 11M06, 11Y16; Secondary 68Q25
Published electronically: January 25, 2011
MathSciNet review: 2785479
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A practical method to compute the Riemann zeta function is presented. The method can compute $ \zeta(1/2+it)$ at any $ \lfloor T^{1/4} \rfloor$ points in $ [T,T+T^{1/4}]$ using an average time of $ T^{1/4+o(1)}$ per point. This is the same complexity as the Odlyzko-Schönhage algorithm over that interval. Although the method far from competes with the Odlyzko-Schönhage algorithm over intervals much longer than $ T^{1/4}$, it still has the advantages of being elementary, simple to implement, it does not use the fast Fourier transform or require large amounts of storage space, and its error terms are easy to control. The method has been implemented, and results of timing experiments agree with its theoretical amortized complexity of $ T^{1/4+o(1)}$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11M06, 11Y16, 68Q25

Retrieve articles in all journals with MSC (2000): 11M06, 11Y16, 68Q25


Additional Information

Ghaith A. Hiary
Affiliation: Institute for advanced Study, 1 Einstein Drive, Princeton, New Jersey 08540
Address at time of publication: University of Waterloo, Department of Pure Mathematics, 200 University Avenue W, Waterloo, ON N2L 3G1, Canada
Email: hiaryg@gmail.com

DOI: http://dx.doi.org/10.1090/S0025-5718-2011-02452-X
PII: S 0025-5718(2011)02452-X
Keywords: Riemann zeta function, algorithms
Received by editor(s): February 11, 2010
Received by editor(s) in revised form: April 28, 2010
Published electronically: January 25, 2011
Additional Notes: This material is based upon work supported by the National Science Foundation under agreements No. DMS-0757627 (FRG grant) and No. DMS-0635607.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.