Fast evaluation of modular functions using Newton iterations and the AGM
Régis Dupont · Mathematics of Computation · 2011
We present an asymptotically fast algorithm for the numerical evaluation of modular functions such as the elliptic modular function j j . Our algorithm makes use of the natural connection between the arithmetic-geometric mean (AGM) of complex numbers and modular functions. Through a detailed complexity analysis, we prove that for a given τ \tau , evaluating N N significative bits of j ( τ ) j(\tau ) can be done in time O ( M ( N ) log N ) O(\mathcal {M}(N)\log N) , where M ( N ) \mathcal {M}(N) is the time complexity for the multiplication of two N N -bit integers. However, this is only true for a fixed τ \tau and the time complexity of this first algorithm greatly increases as I m ( τ ) \mathrm {Im}(\tau ) does. We then describe a second algorithm that achieves the same time complexity independently of the value of τ \tau in the classical fundamental domain F \mathcal {F} . We also show how our method can be used to evaluate other modular forms, such as the Dedekind η \eta function, with the same time complexity.