A gmp-based implementation of schönhage-strassen's large integer multiplication algorithm

ABSTRACT

Schönhage-Strassen's algorithm is one of the best known algorithms for multiplying large integers. Implementing it ef?ciently is of utmost importance, since many other algorithms rely on it as a subroutine. We present here an improved implementation, based on the one distributed within the GMP library. The following ideas and techniques were used or tried: faster arithmetic modulo 2ⁿ + 1, improved cache locality, Mersenne transforms, Chinese Remainder Reconstruction, the √2 trick, Harley's and Granlund's tricks, improved tuning.

REFERENCES

• 1: Arndt, J. Algorithms for programmers (working title). Draft version of 2007-January-05, http://www.jjj.de/fxt/
• 2: Bailey, D. The computation of Π to 29,360,000 decimal digits using Borwein's quartically convergent algorithm. Math. Comp. 50 (1988),283--296.
• 3: D. H. Bailey, FFTs in external or hierarchical memory, The Journal of Supercomputing, v.4 n.1, p.23-35, Mar. 1990 [doi>10.1007/BF00162341]
• 4: Bernstein, D. J. Multidigit multiplication for mathematicians. http://cr.yp.to/papers.html#m3 2001.
• 5: Bernstein, D. J. Fast multiplication and its applications. http://cr.yp.to/papers.html#multapps 2004.
• 6: Bernstein, D. J. Removing redundancy in high-precision Newton iteration. http://cr.yp.to/fastnewton.html 2004.
• 7: Brent, R. P. Multiple-precision zero-finding methods and the complexity of elementary function evaluation. In Analytic Computational Complexity (1975), J. F. Traub, Ed., Academic Press, pp. 151--176.
• 8: Brent, R. P., and Pollard, J. M. Factorization of the eighth Fermat number. Math. Comp. 36 (1981), 627--630.
• 9: Brockmeyer, E., Ghez, C., D'Eer, J., Catthoor, F., and Man, H. D. Parametrizable behavioral IP module for a data-localized low-power FFT. In Proc. IEEE Workshop on Signal Processing Systems (SIPS) (1999), IEEE Press, pp. 635--644.
• 10: Richard Crandall , Barry Fagin, Discrete weighted transforms and large-integer arithmetic, Mathematics of Computation, v.62 n.205, p.305-324, Jan. 1994 [doi>10.2307/2153411]
• 11: Crandall, R., and Pomerance, C. Prime Numbers: A Computational Perspective. Springer-Verlag, 2000.
• 12: Granlund, T. Personal communication, Dec. 2006.
• 13: Harley, R. Personal communication, Jan. 2000.
• 14: Alan H. Karp , Peter Markstein, High-precision division and square root, ACM Transactions on Mathematical Software (TOMS), v.23 n.4, p.561-589, Dec. 1997 [doi>10.1145/279232.279237]
• 15: Knuth, D. The analysis of algorithms. In Actes du Congrès International des Mathématiciens de 1970 (1971), vol. 3, Gauthiers-Villars, pp. 269--274.
• 16: Moenck, R., and Borodin, A. Fast modular transforms via division. In Proceedings of the 13th Annual IEEE Symposium on Switching and Automata Theory (Oct. 1972), pp. 90--96.
• 17: Colin Percival, Rapid multiplication modulo the sum and difference of highly composite numbers, Mathematics of Computation, v.72 n.241, p.387-395, 01 January 2003 [doi>10.1090/S0025-5718-02-01419-9]
• 18: Schönhage, A. Schnelle Berechnung von Kettenbruchentwicklungen. Acta Inform.1 (1971), 139--144.
• 19: Schönhage, A., and Strassen, V. Schnelle Multiplikation großer Zahlen.Computing 7 (1971), 281--292.
• 20: Steel, A. Magma V2.12-1 is up to 2.3 times faster than GMP 4.1.4 for large integer multiplication. http://magma.maths.usyd.edu.au/users/allan/intmult.html July 2005.
• 21: Steel, A. Reduce everything to multiplication. Computing by the Numbers: Algorithms, Precision, and Complexity, Workshop for Richard Brent's 60th birthday, Berlin, July 2006. http://www.mathematik.hu-berlin.de/~gaggle/EVENTS/2006/BRENT60/
• 22: Joris van der Hoeven, The truncated fourier transform and applications, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.290-296, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005327]
• 23: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 24: Woltman, G., and Kurowski, S. The Great Internet Mersenne Prime Search. http://www.gimps.org/
• 25: Zimmermann, P., and Dodson, B. 20 years of ECM. In Proceedings of the 7th Al gorithmic Number Theory Symposium (ANTS VII)(2006), F. Hess, S. Pauli, and M. Pohst, Eds., vol. 4076 of Lecture Notes in Comput. Sci., Springer-Verlag, pp.525--542.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms, Performance

Keywords:
integer multiplication, multiprecision arithmetic