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
|
PARALLEL METHODS OF REPRESENTING MULTIDIGIT NUMBERS
IN NUMERAL SYSTEMS FOR TESTING MULTIDIGIT OPERATIONS
Abstract. The paper proposes methods for representing a multidigit number in a numeral system
with a different base when using parallel processors. Representation of numbers in numeral systems based
on multidigit operations of division and subtraction or multidigit operations of multiplication and addition is considered.
The algorithm with the split of multidigit numbers into groups of digits, taking into account the length of the machine word,
allows calculations involving parallel processors. The complexity by the number of operations and the amount
of additional memory for the algorithms based on the iterative and recursive methods are analyzed.
Keywords: numeral system, multidigit arithmetic, multidigit addition, multidigit multiplication, parallel computing 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. doi.org/10.1145/359340.359342 .
- Zadiraka V.K., Oleksyuk O.S. Computer arithmetic of multi-bit numbers [in Ukrainian]. Kyiv, 2003. 264 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 computing models [in Ukrainian]. Kyiv: Nauk. Dumka, 2021. 136 p.
- Khimich O.M., Sydoruk V.A. The use of mixed bit rate in mathematical modeling. Mathematical and computer modeling. Ser. Phys.-Math. science. 2019. Iss. 19. P. 180–187.
- Anisimov A.V. Algorithmic theory of large numbers. Modular arithmetic of large numbers [in Ukrainian]. Kyiv: Akademperiodika, 2001. 153 p.
- Nikolaichuk Ya.M., Kasyanchuk M.M., Yakimenko I.Z., Ivasiev S.V. Effective method of modular multiplication in the number-theoretic basis of Rademacher–Chrestenson. Bull. National un-ty “Lvivska Polytechnica”. Computer systems and networks. 2014. N 806. P. 195–199. URL: http://nbuv.gov.ua/UJRN .
- Knuth D. The art of computer programming. Vol. 2. Seminumerical Аlgorithms. 3rd ed. Ch. 4. Arithmetic. “Positional Number Systems.” Reading, Massachusetts: Addison–Wesley, 1997. Р. 194–213.
- Floyd R., Knuth D. Addition machines. SIAM Journal on Computing. 1990. Vol. 19, N 2. P. 329–340. doi.org/10.1137/0219022 .
- Anisimov A.V. Addition without units of transfer. Kibernetika i sistemnyj analiz. 1996. N 2. P. 3–15.
- Tereshchenko A.N., Zadiraka V.K. Parallel addition based on vector operations. Shtuchniy íntelekt. 2018. N 2. P. 122–137. URL: http://dspace.nbuv.gov.ua/handle .