Tsz-Wo Sze
ABSTRACT
We present MapReduce-SSA, an integer multiplication algorithm using the ideas from Schönhage-Strassen algorithm (SSA) on MapReduce. SSA is one of the most commonly used large integer multiplication algorithms. MapReduce is a programming model invented for distributed data processing on large clusters. MapReduce-SSA is designed for multiplying integers in terabit scale on clusters of commodity machines. As parts of MapReduce-SSA, two algorithms, MapReduce-FFT and MapReduce-Sum, are created for computing discrete Fourier transforms and summations. These mathematical algorithms match the model of MapReduce seamlessly.
- F. Bellard. Pi computation record, 2009. http://bellard.org/pi/pi2700e9/announce.html.Google Scholar
- F. Bellard. Tachuspi, 2009. http://bellard.org/pi/pi2700e9/tpi.html.Google Scholar
- D. J. Bernstein. Multidigit multiplication for mathematicians, 2001. Available at http://cr.yp.to/papers/m3.pdf.Google Scholar
- D. J. Bernstein. Fast multiplication and its applications. Number 44 in Mathematical Sciences Research Institute Publications, pages 325--384. Cambridge University Press, 2008.Google Scholar
- J. M. Borwein, P. B. Borwein, and D. H. Bailey. Ramanujan, modular equations, and approximations to pi or how to compute one billion digits of pi. 96(3):201--219, 1989. Google ScholarDigital Library
- R. P. Brent and P. Zimmermann. Modern Computer Arithmetic. Number 18 in Cambridge Monographs on Computational and Applied Mathematics. Cambridge University Press, Cambridge, United Kingdom, 2010. Google ScholarDigital Library
- D. Chudnovsky and G. Chudnovsky. The computation of classical constants. In Proc. Nat. Acad. Sci. USA, volume 86, pages 8178--8182. Academic Press, 1989.Google Scholar
- R. Crandall and C. Pomerance. Prime Numbers: A Computational Perspective. Springer-Verlag, New York, NY, 2001.Google Scholar
- A. De, P. P. Kurur, C. Saha, and R. Saptharishi. Fast integer multiplication using modular arithmetic. In Proceedings of the 40th annual ACM Symposium on Theory of Computing, pages 499--506. ACM, 2008. Google ScholarDigital Library
- J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. In Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, pages 137--150. USENIX Association, 2004. Google ScholarDigital Library
- M. Fürer. Faster integer multiplication. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 57--66. ACM, 2007. Google ScholarDigital Library
- P. Gaudry, A. Kruppa, and P. Zimmermann. A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm. In Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, pages 167--174. ACM, 2007. Google ScholarDigital Library
- D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, 1997. Google ScholarDigital Library
- O. O'Malley and A. C. Murthy. Winning a 60 second dash with a yellow elephant, 2009. Available at http://sortbenchmark.org/Yahoo2009.pdf.Google Scholar
- A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7:281--292, 1971.Google ScholarCross Ref
- K. Shvachko, H. Kuang, S. Radia, and R. Chansler. The Hadoop Distributed File System. In 26th IEEE Symposium on Massive Storage Systems and Technologies, 2010. Google ScholarDigital Library
- D. Takahashi, 2010. Personal communication.Google Scholar
- D. Takahashi. Parallel implementation of multiple-precision arithmetic and 2,576,980,370,000 decimal digits of π calculation. Parallel Comput., 36:439--448, August 2010. Google ScholarDigital Library
- A. J. Yee, 2010. Personal communication.Google Scholar
- A. J. Yee. y-cruncher -- a multi-threaded pi-program, 2010. http://www.numberworld.org/y-cruncher/.Google Scholar
- A. J. Yee and S. Kondo. 5 trillion digits of pi - new world record, 2010. http://www.numberworld.org/misc_runs/pi-5t/announce_en.html.Google Scholar
Index Terms
- Schönhage-Strassen algorithm with MapReduce for multiplying terabit integers
Recommendations
A gmp-based implementation of schönhage-strassen's large integer multiplication algorithm
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computationSchönhage-Strassen's algorithm is one of the best known algorithms for multiplying large integers. Implementing it ef?ciently is of utmost importance, since many other algorithms rely on it as a subroutine. We present here an improved implementation, ...
Implementation of the DKSS Algorithm for Multiplication of Large Numbers
ISSAC '15: Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic ComputationThe 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 ...
The Fast Hartley Transform Algorithm
The fast Hartley transform (FHT) is similar to the Cooley-Tukey fast Fourier transform (FFT) but performs much faster because it requires only real arithmetic computations compared to the complex arithmetic computations required by the FFT. Through use ...
Comments