Large integer multiplication on hypercubes (Q1200131)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Large integer multiplication on hypercubes |
scientific article |
Statements
Large integer multiplication on hypercubes (English)
0 references
17 January 1993
0 references
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.
0 references
Schönhage-Strassen algorithm
0 references
large integer multiplication
0 references
Fermat number transform
0 references
hypercube architecture
0 references
