Title of article :
An Algorithm for Exact Division
Author/Authors :
Tudor Jebelean، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 1993
Pages :
12
From page :
169
To page :
180
Abstract :
Current computer algebra systems use the quotient-remainder algorithm for division of long integers even when it is known in advance that the remainder is zero. We propose an algorithm which computes the quotient of two long integers in this particular situation, starting from the least-significant digits of the operands. This algorithm is particularly efficient when the radix is a prime number or a power of 2. The computing time of this new algorithm is smaller than the computing time of the classical division algorithm. If the length of the result is much smaller than the lengths of the inputs, then the speed-up may be quite significant, as it is confirmed by practical experiments. Most importantly, however, the new algorithm is better suited for systolic parallelization in a "least-significant digit first" pipelined manner, and therefore it is suitable for aggregation with other systolic algorithms for the arithmetic of long integers and long rationals. We also present applications of this algorithm in integer GCD computation and in division modulo a power of 2.
Journal title :
Journal of Symbolic Computation
Serial Year :
1993
Journal title :
Journal of Symbolic Computation
Record number :
804931
Link To Document :
بازگشت