A gmp-based implementation of schönhage-strassen's large integer multiplication algorithm
| Autor: | Alexander Kruppa, Pierrick Gaudry, Paul Zimmermann |
|---|---|
| Přispěvatelé: | Curves, Algebra, Computer Arithmetic, and so On (CACAO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), C. W. Brown, Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP) |
| Rok vydání: | 2007 |
| Předmět: |
Modulo
Subroutine [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Mersenne prime 010103 numerical & computational mathematics 01 natural sciences Cache locality 010101 applied mathematics Strassen algorithm ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Integer multiplication 0101 mathematics Remainder Arithmetic Algorithm Mathematics |
| Zdroj: | ISSAC ISSAC 2007 ISSAC 2007, Jul 2007, Waterloo, Ontario, Canada. pp.167-174, ⟨10.1145/1277548.1277572⟩ |
| DOI: | 10.1145/1277548.1277572 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|