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.
MSC (2010): Primary 11-04, 14H42, 14K25; Secondary 14H81, 14H82
DOI: https://doi.org/10.1090/mcom/3245
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
Email: hugo@hlabrande.fr

DOI: https://doi.org/10.1090/mcom/3245
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