An algorithm for exact division

From MaRDI portal





Division of long integers is a frequently performed task in computer algebra. The common algorithms used for that purpose rely on computing quotient and remainder (IQR), even when it is known in advance that the latter one is zero. The author proposes to exploit the fact that the division is exact and gives a time-saving algorithm (EDIV) starting from the least significant digits of the operands, which is particulary efficient when the radix is a prime number or a power of 2. The speed-up may be quite significant, when the length of the result is much smaller than the lengths of the operands. Moreover the proposed algorithm is specially suited for systolic parallelization in pipelining least- significant-digits-first. The algorithm can be applied to integer GCD computation and to division modulo a power of 2. Benchmarks show that the ratio of CPU-times between EDIV and IQR is between 70\% and 30\% depending on the relation of the lengths of the operands. In computing the modular inverse the savings may even be better giving speed-ups between 23 and 28 depending on the input length.











This page was built for publication: An algorithm for exact division

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1260759)