Fast evaluation of modular functions using Newton iterations and the AGM

Abstract:

We present an asymptotically fast algorithm for the numerical evaluation of modular functions such as the elliptic modular function $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$ significative bits of $j(\tau )$ can be done in time $O(\mathcal {M}(N)\log N)$, where $\mathcal {M}(N)$ is the time complexity for the multiplication of two $N$-bit integers. However, this is only true for a fixed $\tau$ and the time complexity of this first algorithm greatly increases as $\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 $\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.