Implementation of the DKSS Algorithm for Multiplication of Large Numbers

Christoph Lüders

In proceedings of Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, pages 267-274, 2015

Abstract

The Schönhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large integers. For N-bit numbers it has a time bound of O(N log N log log N). De, Kurur, Saha and Saptharishi (DKSS) presented an asymptotically faster algorithm with a better time bound of N log N 2^{O(log* N)}. For this paper, a simplified DKSS multiplication was implemented. Assuming a sensible upper limit on the input size, some required constants could be precomputed. This allowed to simplify the algorithm to save some complexity and run-time. Still, run-time is about 30 times larger than SSA, while memory requirements are about 2.3 times higher than SSA. A possible crossover point is estimated to be out of reach even if we utilized the whole universe for computer memory.

Images

Bibtex

@INPROCEEDINGS{Lueders2015,
     author = {L{\"u}ders, Christoph},
      pages = {267--274},
      title = {Implementation of the {DKSS} Algorithm for Multiplication of Large Numbers},
  booktitle = {Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation},
       year = {2015},
   abstract = {The Sch{\"o}nhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large
               integers. For N-bit numbers it has a time bound of O(N log N log log N). De, Kurur, Saha and
               Saptharishi (DKSS) presented an asymptotically faster algorithm with a better time bound of N log N
               2^{O(log* N)}. For this paper, a simplified DKSS multiplication was implemented. Assuming a sensible
               upper limit on the input size, some required constants could be precomputed. This allowed to
               simplify the algorithm to save some complexity and run-time. Still, run-time is about 30 times
               larger than SSA, while memory requirements are about 2.3 times higher than SSA. A possible crossover
               point is estimated to be out of reach even if we utilized the whole universe for computer memory.},
        url = {http://dl.acm.org/ft_gateway.cfm?id=2756643&ftid=1595978&dwn=1&CFID=524532575&CFTOKEN=52995227},
        doi = {10.1145/2755996.2756643}
}