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 com-plexity analysis, we prove that for a given , evaluating N signicative bits of j() can be done in time O(M(N) log N), where M(N) is the time complexity for the multiplication of two N-bit integers. However, this is only true for a xed and the time complexity of this rst algorithm greatly increases as Im() does. We then describe a second algorithm that achieves the same time complexity independently of the value of in the classical fundamental domain F. We also show how our method can be used to evaluate other modular forms, such as the Dedekind function, with the same time complexity. 1