Remember Me
Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:

OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]openaire.eu

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Enge , Andreas; Hart , William; Johansson , Fredrik (2018)
Publisher: University of Waterloo
Languages: English
Types: Article
Subjects: [ MATH.MATH-NT ] Mathematics [math]/Number Theory [math.NT], Mathematics - Number Theory
International audience; The main step in numerical evaluation of classical Sl2 (Z) modular forms and elliptic functions is to compute the sum of the first N nonzero terms in the sparse q-series belonging to the Dedekind eta function or the Jacobi theta constants. We construct short addition sequences to perform this task using N + o(N) multiplications. Our constructions rely on the representability of specific quadratic progressions of integers as sums of smaller numbers of the same kind. For example, we show that every generalised pentagonal number c 5 can be written as c = 2a + b where a, b are smaller generalised pentagonal numbers. We also give a baby-step giant-step algorithm that uses O(N/ log r N) multiplications for any r > 0, beating the lower bound of N multiplications required when computing the terms explicitly. These results lead to speed-ups in practice.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] Paul T. Bateman and Roger A. Horn. A heuristic asymptotic formula concerning the distribution of prime numbers. Mathematics of Computation, 16(79):363-367, 1962.
    • [2] Karim Belabas et al. PARI/GP. Bordeaux, 2.7.5 edition, November 2015. http://pari.math. u-bordeaux.fr/.
    • [3] Daniel J. Bernstein. Fast multiplication and its applications. Algorithmic Number Theory, 44:325-384, 2008.
    • [4] D. V. Chudnovsky and G. V. Chudnovsky. Approximations and complex multiplication according to Ramanujan. In Ramanujan Revisited, pages 375-472. Academic Press, 1988. Proceedings of the Centenary Conference, University of Illinois at Urbana-Champaign, June 1-5, 1987.
    • [5] Henri Cohen. Advanced Topics in Computational Number Theory, volume 193 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2000.
    • [6] Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete mathematics and its applications. Chapman & Hall/CRC, Boca Raton, 2006.
    • [7] David A. Cox. Primes of the Form x2 + ny2 - Fermat, Class Field Theory, and Complex Multiplication. John Wiley & Sons, New York, 1989.
    • [8] David Dobkin and Richard J. Lipton. Addition chain methods for the evaluation of specific polynomials. SIAM Journal on Computing, 9(1):121-125, 1980.
    • [9] Peter Downey, Benton Leong, and Ravi Sethi. Computing sequences with addition chains. SIAM Journal on Computing, 10(3):638-646, August 1981.
    • [10] Régis Dupont. Fast evaluation of modular functions using Newton iterations and the AGM. Mathematics of Computation, 80(275):1823-1847, 2011.
    • [11] Andreas Enge. The complexity of class polynomial computation via floating point approximations. Mathematics of Computation, 78(266):1089-1107, 2009.
    • [12] Andreas Enge. Computing modular polynomials in quasi-linear time. Mathematics of Computation, 78(267):1809-1824, 2009.
    • [13] Andreas Enge. CM - Complex multiplication of elliptic curves. INRIA, 0.2.1 edition, March 2015. Distributed under GPL v2+, http://cm.multiprecision.org/.
    • [14] Andreas Enge and François Morain. 164(4):309-341, 2014.
    • [15] Andreas Enge and Reinhard Schertz. Constructing elliptic curves over finite fields using double eta-quotients. Journal de Théorie des Nombres de Bordeaux, 16:555-568, 2004.
    • [16] Andreas Enge and Reinhard Schertz. Singular values of multiple eta-quotients for ramified primes. LMS Journal of Computation and Mathematics, 16:407-418, 2013.
    • [17] Leonhard Euler. Evolutio producti infiniti (1 − x)(1 − xx)(1 − x3)(1 − x4)(1 − x5)(1 − x6) etc. in seriem simplicem. Acta Academiae Scientiarum Imperialis Petropolitanae, 1780:47-55, 1783.
    • [18] Carl Friedrich Gauß. Disquisitiones Arithmeticae. Gerh. Fleischer Jun., Leipzig, 1801.
    • [19] Emil Grosswald. Representations of Integers as Sums of Squares. Springer-Verlag, New York, 1985.
    • [20] William Hart. MPIR - Multiple Precision Integers and Rationals, 2.7.2 edition, 2015. http: //mpir.org/.
    • [21] Michael D. Hirschhorn. The number of representations of a number by various forms involving triangles, squares, pentagons and octagons. In Nayandeep Deka Baruah, Bruce C. Berndt, Shaun Cooper, Tim Huber, and Michael Schlosser, editors, Ramanujan Rediscovered, volume 14 of RMS Lecture Notes Series, pages 113-124, Mysore, 2009. Ramanujan Mathematical Society.
    • [22] Fredrik Johansson. Evaluating parametric holonomic sequences using rectangular splitting. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pages 256-263, New York, NY, USA, 2014. ACM.
    • [23] Fredrik Johansson. Arb - C library for arbitrary-precision ball arithmetic. INRIA, 2.8.1 edition, 2015. http://github.com/fredrik-johansson/arb/.
    • [24] Donald Knuth. The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, 3rd edition, 1998.
    • [25] A. M. le Gendre. Essai sur la théorie des nombres. Duprat, Paris, 1797. http://gallica. bnf.fr/ark:/12148/btv1b8626880r.
    • [26] David Mumford. Tata Lectures on Theta I. Birkhäuser, Boston, 1983.
    • [27] David Mumford. Tata Lectures on Theta II - Jacobian theta functions and differential equations. Birkhäuser, Boston, 1984.
    • [28] David Mumford. Tata Lectures on Theta III. Birkhäuser, Boston, 1991.
    • [30] Hans Rademacher. The Fourier coefficients of the modular invariant j(τ ). American Journal of Mathematics, 60(2):501-512, 1938.
    • [32] Reinhard Schertz. Weber's class invariants revisited. Journal de Théorie des Nombres de Bordeaux, 14(1):325-343, 2002.
    • [33] David M. Smith. Efficient multiple-precision evaluation of elementary functions. Mathematics of Computation, 52:131-134, 1989.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Funded by projects


Cite this article

Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok