Implementation of the DKSS Algorithm for Multiplication of Large Numbers
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 2O(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} }