Large integer multiplication on hypercubes

DOI10.1016/0743-7315(92)90080-7MaRDI QIDQ1200131zbMATH OpenOpenAlexFDO

Authors Barry S. Fagin

Publication date 17 January 1993

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0743-7315(92)90080-7

zbMATH Keywords

Fermat number transformhypercube architecturelarge integer multiplicationSchönhage-Strassen algorithm

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Numerical methods for discrete and fast Fourier transforms (65T50) Numerical algorithms for specific classes of architectures (65Y10)

Review text

The known algorithm of \textit{A. Schönhage} and \textit{V. Strassen} for large integer multiplication [Computing 7, 281-292 (1971; Zbl 0223.68007)] is mainly based on the Fermat number transform (FNT). Now this algorithm is realized on a connection machine with parallel hypercube architecture. Using such a computer it is possible to overcome the word-length restrictions of the FNT. Thus this technique makes the FNT more attractive for applications. The results show multiplication times of 2 s for 8-Mbit integers, an improvement of about 5 times over previous work.

Recommendations

• Fast multiplication of large numbers
• Integer multiplication in time \(O(n\log n)\)
• More on squaring and multiplying large integers
• A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm
• Faster integer multiplication

Cited in

(11)

• Complexity analysis of algorithm for multiplication of superlarge numbers based on Walsh coefficients
• Performance analysis of the parallel Karatsuba multiplication algorithm for distributed memory architectures
• Schönhage-Strassen algorithm with MapReduce for multiplying terabit integers
• A New Algorithm for Long Integer Cube Computation with Some Insight into Higher Powers
• Arithmetic with very large integers using parallel processing
• A Parallel Algorithm for Multiple-Precision Division by a Single-Precision Integer
• Discrete Weighted Transforms and Large-Integer Arithmetic
• More on squaring and multiplying large integers
• A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm
• Research on large integer multiplication Schönhage-Strassen algorithm's multi-core parallelization
• Parallel implementation of multiple-precision arithmetic and 2,576,980,370,000 decimal digits of calculation

This page was built for publication: Large integer multiplication on hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1200131)