Algorithm for Calculation the Carry and Borrow Signs in Multi-digit Operations in the Parallel Computational Model

Authors

  • Andrii Tereshchenko
  • Valeriy Zadiraka

DOI:

https://doi.org/10.47839/ijc.22.1.2875

Keywords:

multi-digit arithmetic, multi-digit addition, multi-digit subtraction, multi-digit comparison, carry sign, borrow sign, parallel computational model

Abstract

The fast algorithm to calculate carry signs and borrow signs for implementation of fast multi-digit operations in the parallel computational model is proposed. The proposed algorithm also makes it possible to predict carry signs in the case of an addition operation and predict borrow signs for a subtraction operation. It is shown how the sign prediction algorithm is implemented in operations in which each parallel processor proceeds the separate group of words into which multi-digit numbers are divided. The iterative calculations of carry signs of grouped words are described. The sign calculation algorithm as component of new modifications of multi-digit addition, subtraction, comparison, the sum of three or more numbers in the parallel computational model is presented. The sign calculation algorithm provides general approach to the implementation of multiplication, division, multiplication by modulo, exponentiation by modulo in the parallel computational model. In the form of a table, a general analysis of the complexity of algorithms and an analysis of the complexity by the number of single-word operations per processor are given.

References

R. K. Richards, Arithmetic Operations in Digital Computers. New York: Van Nostrand, 1955.

O. L. MacSorley, “High-speed arithmetic in binary computers,” Proc. IRE, vol. 49, Jan., pp. 67–91, 1961. https://doi.org/10.1109/JRPROC.1961.287779.

M. Flynn, S. Oberman, Advanced Computer Arithmetic Design. Wiley, 2001, 344 p.

J. E. Robertson, Theory of Computer Arithmetic Employed in the Design of the New Computer at the University of Illinois, Urbana: Digital Computer Lab., University of Illinois, June 1960.

I. Koren, Computer Arithmetic Algorithms, AK Peters Ltd, 2001, 296 p.

V. Kumar, et al., “A unified architecture for BCD and binary adder/subtractor,” Proceedings of the 14th Euromicro Conference on Digital System Design. Architectures, Methods and Tools. (DSD 2011), Oulu, pp. 426–429, 2011. https://doi.org/10.1109/DSD.2011.58.

V. S. Knyazkov, K. S. Isupov, “Parallell multiple-precision arithmetic based on residue number system,” Program Syst. Theor. Appl., vol. 7, issue 28, pp. 61–97, 2016. https://doi.org/10.25209/2079-3316-2016-7-1-61-97.

P. Montgomery, “Modular multiplication without trial division,” Mathematics of Computation, vol. 4, no. 170, pp. 519–521, 1985. https://doi.org/10.1090/S0025-5718-1985-0777282-X.

G. Jaberipur, A. Kaivani, “Improving the speed of parallel decimal multiplication,” IEEE Transactions on Computers, vol. 58, issue 11, pp. 1539–1552, 2009. https://doi.org/10.1109/TC.2009.110.

A. Schonhage and V. Strassen, “Schnelle Multiplication grosser Zahlen,” Computing, vol. 7, no. 3–4, pp. 281–292, 1971. https://doi.org/10.1007/BF02242355.

W. Diffie and M. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. IT-22, pp. 472–492, 1976. https://doi.org/10.1109/TIT.1976.1055638.

B. Schneier, Applied Cryptography. John Wiley & Sons, New York, 1996. 467 p.

T. Elgamal, “A public-key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Trans. Inform. Theory, vol. IT-31, no. 4, pp. 469–472, 1985. https://doi.org/10.1109/TIT.1985.1057074.

S. R. Dusse and B. S. Kalisky, “A cryptographic library for the Motorola DSP 56000,” Advances in Cryptology, Eurocrypt’90, Lect. Notes Comput. Sci., pp. 230–244, 1990. https://doi.org/10.1007/3-540-46877-3_21.

B. Arazi, “On primality testing using purely divisionless operations,” The Computer Journal, vol. 37, no. 3, pp. 219–222, 1994. https://doi.org/10.1093/comjnl/37.3.219.

S. Kumaravel and R. Marimuthu, “VLSI implementation of high performance RSA algorithm using vedic mathematics,” Proceedings of the International Conference on Computational Intelligence and Multimedia Applications (ICCIMA 2007), Sivakasi, India, 2007, pp. 126-128. https://doi.org/10.1109/ICCIMA.2007.238.

Y. Bassil, A. Barbar, “Sequential and parallel algorithms for the addition of big-integer numbers,” International Journal of Computational Science, vol. 4, no. 1, pp. 52–69, 2010.

L. Dadda, “Multioperand parallel decimal adder: A mixed binary and BCD approach,” IEEE Transactions on Computers, vol. 56, no. 10, pp. 1320–1328, 2007. https://doi.org/10.1109/TC.2007.1067.

M. Véstias, N. Horácio, “Improving the area of fast parallel decimal multipliers,” Microprocessors and Microsystems, vol. 61, pp. 96–107, 2018. https://doi.org/10.1016/j.micpro.2018.05.015.

A. K. Cherri, “Optical carry-free addition and borrow-free subtraction based on redundant signed-digit numbers,” Proceedings of the IEEE 1993 National Aerospace and Electronics Conference-NAECON 1993, pp. 1094-1099 vol.2, 1993. https://doi.org/10.1109/NAECON.1993.290789.

M. S. Schmookler and A. Weinberger, “High speed decimal addition,” IEEE Transactions on Computers, vol. C-20, no. 8, pp. 862–866, 1971. https://doi.org/10.1109/T-C.1971.223362.

C. McGeoch, “Parallel addition,” The American Mathematical Monthly, vol. 100, issue 9, pp. 867–871, 1993. https://doi.org/10.2307/2324666.

R. Floyd, D. Knuth, “Addition machines,” SIAM Journal on Computing, vol. 19, issue 2, pp. 329–340, 1990. https://doi.org/10.1137/0219022.

A. V. Anisimov, “Carryless addition,” Cybernetics and Systems Analysis, vol. 32, pp. 153–163, 1996. https://doi.org/10.1007/BF02366527.

V. K. Zadiraka, A. M. Tereshchenko, “Calculating the sum of multidigit values in the parallel computational model,” Cybernetics and Systems Analysis, vol. 58, pp. 473–480, 2022. https://doi.org/10.1007/s10559-022-00478-7.

Downloads

Published

2023-03-29

How to Cite

Tereshchenko, A., & Zadiraka, V. (2023). Algorithm for Calculation the Carry and Borrow Signs in Multi-digit Operations in the Parallel Computational Model. International Journal of Computing, 22(1), 21-28. https://doi.org/10.47839/ijc.22.1.2875

Issue

Section

Articles