An algorithm for exact division (Q1260759)

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.