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 at any points in using an *average* time of 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 , 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 .

**[Ga]**W. Gabcke,*Neue Herleitung und explicite Restabschätzung der Riemann-Siegel-Formel.*Ph.D. Dissertation, Göttingen, 1979.**[G]**X. Gourdon,*The first zeros of the Riemann zeta function and zero computation at very large heights.*Available at: http://numbers.compuation.free.fr.**[L]**B. F. Logan,*Bounds for the tails of sharp-cutoff filter kernels*, SIAM J. Math. Anal.**19**(1988), no. 2, 372–376. MR**930033**, 10.1137/0519027**[O]**A.M. Odlyzko,*The -th zero of the Riemann zeta function and 175 million of its neighbors.**www.dtc.umn.edu/odlyzko***[OS]**A. M. Odlyzko and A. Schönhage,*Fast algorithms for multiple evaluations of the Riemann zeta function*, Trans. Amer. Math. Soc.**309**(1988), no. 2, 797–809. MR**961614**, 10.1090/S0002-9947-1988-0961614-2**[R]**Michael Rubinstein,*Computational methods and experiments in analytic number theory*, Recent perspectives in random matrix theory and number theory, London Math. Soc. Lecture Note Ser., vol. 322, Cambridge Univ. Press, Cambridge, 2005, pp. 425–506. MR**2166470**, 10.1017/CBO9780511550492.015**[R1]**M.O. Rubinstein home-page,*www.math.uwaterloo.ca/mrubinst*.

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

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.