Computing Jacobi's in quasi-linear time
2016
Jacobi’s θ function has numerous applications in mathematics and computer science; a naive algorithm allows the computation of θ(z, τ), for z, τ verifying certain conditions, with precision P in O(M(P ) √ P ) bit operations, where 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 θ function (the theta-constants) in asymptotically faster time; this gives us an algorithm to compute θ(z, τ) with precision P in O(M(P ) logP ) bit operations, for any τ ∈ F and z reduced using the quasi-periodicity of θ.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
3
Citations
NaN
KQI