{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T08:03:45Z","timestamp":1791273825705,"version":"4.1.0"},"reference-count":16,"publisher":"American Mathematical Society (AMS)","issue":"275","license":[{"start":{"date-parts":[[2012,3,4]],"date-time":"2012-03-04T00:00:00Z","timestamp":1330819200000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We present an asymptotically fast algorithm for the numerical evaluation of modular functions such as the elliptic modular function\u00a0\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"j\">\n                        <mml:semantics>\n                          <mml:mi>j<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">j<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . 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\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"tau\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u03c4\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\tau<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , evaluating\u00a0\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper N\">\n                        <mml:semantics>\n                          <mml:mi>N<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">N<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    significative bits of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"j left-parenthesis tau right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>j<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>\n                              \u03c4\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">j(\\tau )<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    can be done in time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis script upper M left-parenthesis upper N right-parenthesis log upper N right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi class=\"MJX-tex-caligraphic\" mathvariant=\"script\">M<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(\\mathcal {M}(N)\\log N)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , where\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script upper M left-parenthesis upper N right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi class=\"MJX-tex-caligraphic\" mathvariant=\"script\">M<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathcal {M}(N)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is the time complexity for the multiplication of two\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper N\">\n                        <mml:semantics>\n                          <mml:mi>N<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">N<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -bit integers. However, this is only true for a\n                    <italic>fixed<\/italic>\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"tau\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u03c4\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\tau<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and the time complexity of this first algorithm greatly increases as\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal upper I normal m left-parenthesis tau right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"normal\">I<\/mml:mi>\n                              <mml:mi mathvariant=\"normal\">m<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>\n                              \u03c4\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathrm {Im}(\\tau )<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    does. We then describe a second algorithm that achieves the same time complexity independently of the value of\u00a0\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"tau\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u03c4\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\tau<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    in the classical fundamental domain\u00a0\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script upper F\">\n                        <mml:semantics>\n                          <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                            <mml:mi class=\"MJX-tex-caligraphic\" mathvariant=\"script\">F<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathcal {F}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . We also show how our method can be used to evaluate other modular forms, such as the Dedekind\u00a0\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"eta\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u03b7\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\eta<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    function, with the same time complexity.\n                  <\/p>","DOI":"10.1090\/s0025-5718-2011-01880-6","type":"journal-article","created":{"date-parts":[[2011,3,4]],"date-time":"2011-03-04T09:54:19Z","timestamp":1299232459000},"page":"1823-1847","source":"Crossref","is-referenced-by-count":14,"title":["Fast evaluation of modular functions using Newton iterations and the AGM"],"prefix":"10.1090","volume":"80","author":[{"given":"R\u00e9gis","family":"Dupont","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2011,3,4]]},"reference":[{"issue":"1","key":"1","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1080\/10586458.2003.10504716","article-title":"How to compute the coefficients of the elliptic modular function \ud835\udc57(\ud835\udc67)","volume":"12","author":"Baier, Harald","year":"2003","journal-title":"Experiment. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1058-6458","issn-type":"print"},{"key":"2","series-title":"Canadian Mathematical Society Series of Monographs and Advanced Texts","isbn-type":"print","volume-title":"Pi and the AGM","author":"Borwein, Jonathan M.","year":"1987","ISBN":"https:\/\/id.crossref.org\/isbn\/0471831387"},{"key":"3","first-page":"151","article-title":"Multiple-precision zero-finding methods and the complexity of elementary function evaluation","author":"Brent, Richard P.","year":"1976"},{"issue":"3-4","key":"4","first-page":"275","article-title":"The arithmetic-geometric mean of Gauss","volume":"30","author":"Cox, David A.","year":"1984","journal-title":"Enseign. Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0013-8584","issn-type":"print"},{"key":"5","series-title":"Enzyklop\\\"{a}die der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, Band I 2, Heft 10, Teil I","volume-title":"Die Klassenk\\\"{o}rper der komplexen Multiplikation","author":"Deuring, M.","year":"1958"},{"key":"6","unstructured":"R. Dupont. Borchardt\u2019s mean, theta constants in genus 2 and applications, 2005. In preparation."},{"issue":"266","key":"7","doi-asserted-by":"publisher","first-page":"1089","DOI":"10.1090\/S0025-5718-08-02200-X","article-title":"The complexity of class polynomial computation via floating point approximations","volume":"78","author":"Enge, Andreas","year":"2009","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"8","unstructured":"A. Enge. The complexity of modular polynomial computation via floating point evaluation and interpolation, 2005. In preparation."},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/3-540-45455-1_21","article-title":"Comparing invariants for class fields of imaginary quadratric fields","author":"Enge, Andreas","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540438637"},{"key":"10","unstructured":"A. Enge and P. Zimmermann. mpc \u2013 Multiprecision Complex arithmetic library version 0.4, 2004. Available at http:\/\/www.loria.fr\/~zimmerma\/free\/."},{"key":"11","unstructured":"C. F. Gauss. Werke. Dieterich, G\u00f6ttingen, 1866\u20131933."},{"key":"12","unstructured":"T. Granlund et al. gmp \u2013 GNU Multiprecision library version 4.1, 2002. Available at http:\/\/www.swox.com\/gmp\/."},{"key":"13","unstructured":"G. Hanrot, V. Lef\u00e8vre, P. P\u00e9lissier, and P. Zimmermann. mpfr \u2013 Multiple Precision Floating point computations with exact Rounding library version 2.1.0, 2004. Available at http:\/\/www.mpfr.org."},{"key":"14","series-title":"Progress in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-2843-6","volume-title":"Tata lectures on theta. I","volume":"28","author":"Mumford, David","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/3764331097"},{"key":"15","series-title":"Die Grundlehren der mathematischen Wissenschaften, Band 203","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-65663-7","volume-title":"Elliptic modular functions: an introduction","author":"Schoeneberg, Bruno","year":"1974"},{"key":"16","unstructured":"H. Weber. Lehrbuch der Algebra, volume III. Chelsea Publishing Company, New York, 1902."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2011-80-275\/S0025-5718-2011-01880-6\/S0025-5718-2011-01880-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2011-80-275\/S0025-5718-2011-01880-6\/S0025-5718-2011-01880-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T16:53:34Z","timestamp":1776790414000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2011-80-275\/S0025-5718-2011-01880-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,4]]},"references-count":16,"journal-issue":{"issue":"275","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["S0025-5718-2011-01880-6"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2011-01880-6","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2011,3,4]]}}}