×

Fast multiplication of large numbers. (Schnelle Multiplikation großer Zahlen.) (German) Zbl 0223.68007

In dieser Arbeit werden unter der Verwendung der schnellen Fouriertransformation FFT [vgl. J. W. Cooley and J. W. Tukey, Math. Comput. 19, 297–301 (1965; Zbl 0127.09002)] zwei Algorithmen zur Multiplikation \(N\)-stelliger Dualzahlen gegeben, die sowohl als Turingmaschinen wie auch als logische Netze so realisiert werden können, dass ihr Aufwand durch \(O(N\log N (\log \log N)^{1+\varepsilon})\) bzw. \(O(N\log N \log \log N)\) abgeschätzt werden kann.
Beim ersten Verfahren wird die FFT wie üblich im Körper \(\mathbb C\) benutzt, beim zweiten in den Restklassenringen \(\mathbb Z_{F_n}\) nach den Fermatzahlen \(F_n=2^{2^n}+1\). Darin ist nämlich \(2\) eine \(2^{n+1}\)-te primitive Einheitswurzel, deren Potenzreste extrem einfache Dualdarstellungen besitzen. (German original)
English translation: In this article using the fast Fourier transform FFT [see J. W. Cooley and J. W. Tukey, Math. Comput. 19, 297–301 (1965; Zbl 0127.09002)] two algorithms for the multiplication of \(N\)-digit binary numbers are given that can be realized as Turing machines as well as logical nets such that their steps can be estimated by \(O(N\log N (\log \log N)^{1+\varepsilon})\) resp. \(O(N\log N \log \log N)\).
In the first method FFT is used as usual in the field \(\mathbb C\), whereas in the second one it is used in the residue class rings \(\mathbb Z_{F_n}\) of the Fermat numbers \(F_n=2^{2^n}+1\). Therein \(2\) is a \(2^{n+1}\)st primitive unit root the power residues of which possess extremely simple representations.
Reviewer: A. Schönhage

MSC:

68W30 Symbolic computation and algebraic computation
11Y16 Number-theoretic algorithms; complexity
68M07 Mathematical problems of computer architecture
65T60 Numerical methods for wavelets

Citations:

Zbl 0127.09002
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cook, S. A.: On the Minimum Computation Time of Functions. Dissertation, Harvard Universität (1966). · Zbl 0207.31204
[2] Cook, S. A., andS. O. Aanderaa: On the Minimum Computation Time of Functions. Trans. AMS142, 291–314 (1969). · Zbl 0188.33402 · doi:10.1090/S0002-9947-1969-0249212-8
[3] Cooley, J. W., andJ. W. Tukey: An Algorithm for the Machine Calculation of ComplexFourier Series. Math. Comp.19, 297–301 (1965). · Zbl 0127.09002 · doi:10.1090/S0025-5718-1965-0178586-1
[4] Karacuba, A., (undJ. Ofman): Multiplikation vielstelliger Zahlen mit Rechenautomaten (russisch). Dokl. Akad. Nauk SSSR145, 293–294 (1962).
[5] Knuth, D. E.: The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, Chapter 4: Arithmetic. Addison-Wesley. 1969. · Zbl 0191.18001
[6] Schönhage, A.: Multiplikation großer Zahlen. Computing1, 182–196 (1966). · Zbl 0196.52104 · doi:10.1007/BF02234362
[7] Toom, A. L.: Die Komplexität eines logischen Netzes, das die Multiplikation ganzer Zahlen realisiert. Dokl. Akad. Nauk SSSR150, 496–498 (1963).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.