Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computing Jacobi's theta in quasi-linear time

Author: Hugo Labrande
Journal: Math. Comp. 87 (2018), 1479-1508
MSC (2010): Primary 11-04, 14H42, 14K25; Secondary 14H81, 14H82
Published electronically: November 1, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Jacobi's $ \theta $ function has numerous applications in mathematics and computer science; a naive algorithm allows the computation of $ \theta (z,\tau )$, for $ z, \tau $ verifying certain conditions, with precision $ P$ in $ O(\mathcal {M}(P) \sqrt {P})$ bit operations, where $ \mathcal {M}(P)$ denotes the number of operations needed to multiply two complex $ P$-bit numbers. We generalize an algorithm which computes specific values of the $ \theta $ function (the theta-constants) in asymptotically faster time; this gives us an algorithm to compute $ \theta (z, \tau )$ with precision $ P$ in $ O(\mathcal {M}(P) \log P)$ bit operations, for any $ \tau \in \mathcal {F}$ and $ z$ reduced using the quasi-periodicity of $ \theta $.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11-04, 14H42, 14K25, 14H81, 14H82

Retrieve articles in all journals with MSC (2010): 11-04, 14H42, 14K25, 14H81, 14H82

Additional Information

Hugo Labrande
Affiliation: INRIA Lorraine – projet CARAMBA, 615 rue du jardin botanique, 54602 Villers-les-Nancy Cedex, France

Received by editor(s): November 13, 2015
Received by editor(s) in revised form: June 2, 2016, and November 22, 2016
Published electronically: November 1, 2017
Article copyright: © Copyright 2017 by Hugo Labrande

American Mathematical Society