Aspekty algorytmiczne organizacji układu do mnożenia długich operandów

• Autorzy: Gliszczyński M. , Tariov A.

Warianty tytułu

EN

Algorithmic aspects of long-digit multiplier organization

• Języki publikacji: PL

Abstrakty

PL

W pracy została zaprezentowana zracjonalizowana struktura algorytmiczna do obliczania iloczynu dwóch operandów N-elementowych ze zredukowaną liczbą układów mnożących i sumatorów dla dowolnej dużej wartości. Pozwala to przy implementacji zmniejszyć nakłady obliczeniowe lub zapotrzebowanie na zasoby sprzętowe oraz stworzyć dogodne warunki do efektywnej realizacji operacji mnożenia dużych liczb w dowolnym sprzętowo-programowym środowisku implementacyjnym.

EN

In the paper the fast algorithm for two long, N-digits numbers multiplication with reduced number of multipliers and adders for any large value is presented. In the first paragraph a theoretical problem with known solutions is presented. While naive N-bits numbers multiplication requires N×N fragmentary, one-bit multiplications, the Karatsuba approach using simple transformations (1-3) and recursion provides smaller complexity. There are also described other, faster algorithms of more complicated structure (Toom-3, Schönhage-Strassen). The algorithm presented in this paper is based on the Karatsuba method because of its simplicity. In the second paragraph there is given the synthesis of a matrix-based, tensor product algorithm for large operand multiplications with no recursion needed. All matrix constructions are predefined. Next, the graph-structural models of the algorithm with time/space flow of data for N=2 and N=4 are shown (Figs. 1, 2). At the end, estimation of the number of multipliers and adders according to the operands length, supported by Table 1, is discussed (11, 12). The advantages of the new algorithm are simple and clear matrices-based construction, easy implementation, no need of recursion, possibility of parallel execution and reduced number of multipliers. Next problem to consider is profitability of the proposed approach in multi-core hardware implementation depending on N value.

Słowa kluczowe

PL

systemy komputerowe; wskazówkowe przyrządy pomiarowe; kreślenie podziałek

EN

computer systems; indicating analogue measuring instruments; drawing of the scales

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 10
• Strony: 1130--1132
• Opis fizyczny: Bibliogr. 13 poz., rys., tab., wzor

Twórcy

autor

Gliszczyński M.

autor

Tariov A.

• Zachodniopomorski Uniwersytet Technologiczny, Wydział Informatyki, ul. Żołnierska 49, 71-126 Szczecin,

Bibliografia

• [1] Biernat J., Arytmetyka Komputerów, Wydawnictwo Naukowe PWN, 1996.
• [2] Bodrato M., Toward Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0, WAIFI’07, Springer, 2007.
• [3] Burrus C. S., Parks T. W., Potts J. F., DFT/FFT and Convolution Algorithms and Implementation, John Willey & Sons, 1985.
• [4] Cesari G. and Maeder R., Performance analysis of the parallel Karatsuba multiplication algorithm for distributed memory architectures. J. Symb. Comput., 21 (4-6):467–473, 1996.
• [5] Cook S. A., On the minimum computation time of functions, Harvard University - PhD thesis, 1966.
• [6] Dagman E. E., Kukharev. G. A., Szybkie dyskretne transformaty ortogonalne, Wydawnictwo Nauka, 1983.
• [7] Fürer M., Faster integer multiplication, STOC’07: Proceedings of the thirty-ninth annual, ACM symposium on Theory of computing (New York, NY, USA), ACM, 2007, pp. 57-66.
• [8] Karatsuba A., Ofman Y., Multiplication of Many-Digital Numbers by Automatic Computers. Doklady Akad. Nauk SSSR Vol. 145, 1962, pp. 293–294. Translation in Physics-Doklady 7, 1963, pp. 595–596.
• [9] Liu C. -B., Huang C. -H., Design and Implementation of Long-Digit Karatsuba’s Multiplication Algorithm Using Tensor Product Formulation, In The Ninth Workshop on Compiler Techniques for High Performance Computing, 2003, pp. 23-30.
• [10] Schönhage A., Strassen V., Schnelle Multiplikation großer Zahlen, Computing 7, 1971, pp. 281–292.
• [11] Toom A. L., The complexity of a scheme of functional elements simulating the multiplication of integers, Dokl. Akad. Nauk SSSR 150 (1963), 496{498, (in Russian). English translation in Soviet Mathematics 3, 714-716, 1963.
• [12] Ţariov A., Modele algorytmiczne i struktury wysokowydajnych procesorów cyfrowej obróbki sygnałów, Szczecin, Informa, 2001.
• [13] Ţariov A., Strategie racjonalizacji obliczeń przy wyznaczaniu iloczynów macierzowo-wektorowych. Metody Informatyki stosowanej, Nr 1, 2008, str. 147-158.