Algorithm for Calculation the Carry and Borrow Signs in Multi-digit Operations in the Parallel Computational Model
DOI:
https://doi.org/10.47839/ijc.22.1.2875Keywords:
multi-digit arithmetic, multi-digit addition, multi-digit subtraction, multi-digit comparison, carry sign, borrow sign, parallel computational modelAbstract
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
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
