A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm

Pierrick Gaudry 1 Alexander Kruppa 1 Paul Zimmermann 1
1 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Schönhage-Strassen's algorithm is one of the best known algorithms for multiplying large integers. Implementing it efficiently 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^n+1$, improved cache locality, Mersenne transforms, Chinese Remainder Reconstruction, the $\sqrt{2}$ trick, Harley's and Granlund's tricks, improved tuning.
Type de document :
Communication dans un congrès
C. W. Brown. ISSAC 2007, Jul 2007, Waterloo, Ontario, Canada. ACM Press, pp.167-174, 2007, Proceedings of the 2007 international symposium on Symbolic and algebraic computation. 〈10.1145/1277548.1277572〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00126462
Contributeur : Pierrick Gaudry <>
Soumis le : mercredi 23 mai 2007 - 07:41:16
Dernière modification le : jeudi 11 janvier 2018 - 06:21:04
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:13:00

Fichier

fft.final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierrick Gaudry, Alexander Kruppa, Paul Zimmermann. A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm. C. W. Brown. ISSAC 2007, Jul 2007, Waterloo, Ontario, Canada. ACM Press, pp.167-174, 2007, Proceedings of the 2007 international symposium on Symbolic and algebraic computation. 〈10.1145/1277548.1277572〉. 〈inria-00126462v2〉

Partager

Métriques

Consultations de la notice

613

Téléchargements de fichiers

548