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

Résumé

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 2n+12^n+12n+1, improved cache locality, Mersenne transforms, Chinese Remainder Reconstruction, the sqrt2\sqrt{2}sqrt2 trick, Harley's and Granlund's tricks, improved tuning.

Domaines

Connectez-vous pour contacter le contributeur

https://inria.hal.science/inria-00126462

Soumis le : mercredi 23 mai 2007-07:41:16

Dernière modification le : mercredi 18 mars 2026-11:52:02

Archivage à long terme le : mardi 21 septembre 2010-13:13:00

Dates et versions

inria-00126462 , version 1 (25-01-2007)

inria-00126462 , version 2 (23-05-2007)

Licence

Identifiants

Citer

Pierrick Gaudry, Alexander Kruppa, Paul Zimmermann. A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm. ISSAC 2007, Jul 2007, Waterloo, Ontario, Canada. pp.167-174, ⟨10.1145/1277548.1277572⟩. ⟨inria-00126462v2⟩

1264 Consultations

6006 Téléchargements

Altmetric