Carryless addition (Q1364070)

Processing of long numbers is a topical problem of considerable interest. On the one hand, this is attributable to the wide range of traditional computational problems that require high numerical precision. On the other hand, studies in the arithmetic of large numbers are stimulated by the rapid development of information-protection methods based on RSA or exponential public-key systems. This line of research is related to a series of studies that examine divisionless implementation of arithmetical modular functions. Of particular interest is the paper by \textit{R. W. Floyd} and \textit{D. E. Knuth} [SIAM J. Comput. 19, No. 2, 329-340 (1990; Zbl 0697.68057)], who show that the addition machine may be viewed as a basic computational model for efficient implementation of the main functions of modular arithmetic. The length of large numbers is an obstacle even in the simple operations of addition and subtraction. This is due to the need to calculate the ones carried to higher-order bits in each addition, and in principle the carry may propagate to all the bits of the numerical representation. Traditional addition of two \(N\)-digit numbers in general may require carrying an order of \(N\) bits. Since arithmetic adders are the architectural building blocks for computing all other arithmetic operations, improving their speed may produce a significant acceleration effect for the entire computation process. In this paper we show that the computation in a series of \(k\) additions can be organized so that the carry ones are considered only once during the final addition. All other operations are performed synchronously on all bits, requiring \(O(k)\) vector operations. The executing time of a series of additions is thus virtually independent of the number of digits. Given the results of \textit{R. W. Floyd} and \textit{D. E. Knuth} (see above), this suggests that we can design an efficient hardware implementation of addition machines for manipulation of superlarge numbers.