UDC 519.6
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 zvk140@ukr.net
|
2 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
teramidi@ukr.net
|
CALCULATING THE SUM OF MULTIDIGIT VALUES IN A PARALLEL
COMPUTATIONAL MODEL
Abstract. The authors propose a new method for implementing the operation of finding the sum of two or more multidigit values in a parallel computational model. The method reduces finding the sum of a large number of multidigit values to the sum of two multidigit values by carry-save addition, which can be efficiently implemented in a parallel computational model based on carry-lookahead addition of groups of words. The algorithms for implementing the operation of the sum of values on one processor and using k processors are proposed. The complexity analysis is carried out for the proposed algorithms.Keywords: multidigit arithmetic, multidigit addition, carry sign, parallel computational model.
Keywords: multidigit arithmetic, multidigit addition, carry sign, parallel computational model.
FULL TEXT
REFERENCES
- Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 1978. Vol. 21, N 2. P. 120–126. https://doi.org/ 10.1145/359340.359342.
- Anisimov A.V. Algorithmic theory of large numbers. Modular arithmetic of large numbers [in Russian]. Kyiv: Akademperiodyka, 2001. 153 с. URL : http://books.zntu.edu.ua/book_info.pl?id=21106.
- Zadiraka V., Oleksyuk O. Computer arithmetic of multi-bit numbers [in Ukrainian]. Kyiv: Nauk. vydannya, 2003. 263 p.
- Zadiraka V.K. The theory of calculating the Fourier transform [in Russian]. Kyiv: Nauk. dumka, 1983. 213 p.
- Zadiraka V.K., Tereshchenko A.M. Computer arithmetic of multi-bit numbers in serial and parallel computational models [in Ukrainian]. Kyiv: Nauk. dumka, 2021. 136 p.
- Nykolaychuk Y.M., Kasyanchuk M.M., Yakimenko I.Z., Ivasev S.V. An effective method of modular multiplication in the Rademacher–Crestenson theoretical-numerical basis. Visn. Nat. Lviv Polytechnic University. Computer systems and networks. 2014. N 806. P. 195–199. URL: http://nbuv.gov.ua/UJRN/VNULPKSM_2014_806_31.
- Khimich O.M., Sidoruk V.A. Use of mixed bit in mathematical modeling. Matematychne ta komp’yuterne modelyuvannya. Series: Phys.-Math. science. Coll. Science. work. 2019. Iss. 19. P. 180–187. https://doi.org/10.32626/2308-5878.2019-19.180-187.
- Anisimov A.V. Addition without units of transfer. Kibernetika i sistemnyj analiz. 1996. N 2. P. 3–15.
- Floyd R., Knuth D. Addition machines. SIAM Journal on Computing. 1990. Vol. 19, N 2. P. 329–340. https://doi.org/10.1137/0219022.
- McGeoch C. Parallel addition. The American Mathematical Monthly. 1993. Vol. 100, N 9. P. 867–871. URL: http://www.jstor.org/stable/2324666.
- Tereshchenko A.N., Zadiraka V.K. Parallel addition based on vector operations. Iskusstvennyy intellekt. 2018. N 2. P. 122–137. URL: http://dspace.nbuv.gov.ua/handle/123456789/162381.
