- Tytuł:
-
Aspekty algorytmiczne organizacji układu do mnożenia długich operandów
Algorithmic aspects of long-digit multiplier organization - Autorzy:
-
Gliszczyński, M.
Tariov, A. - Powiązania:
- https://bibliotekanauki.pl/articles/158113.pdf
- Data publikacji:
- 2010
- Wydawca:
- Stowarzyszenie Inżynierów i Techników Mechaników Polskich
- Tematy:
-
systemy komputerowe
wskazówkowe przyrządy pomiarowe
kreślenie podziałek
computer systems
indicating analogue measuring instruments
drawing of the scales - Opis:
-
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.
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. - Źródło:
-
Pomiary Automatyka Kontrola; 2010, R. 56, nr 10, 10; 1130-1132
0032-4140 - Pojawia się w:
- Pomiary Automatyka Kontrola
- Dostawca treści:
- Biblioteka Nauki
Artykuł