A ultra fast Euclidean division algorithm for prime memory systems
Benoît Dupont de Dinechin · 1991
In this paper, we describe a general method which is suitable for ejjicient hardware implementation of euclidean division by numbers of the form 2n & 1.This method relies on the properties of two's complement binay arithmetic to perform simultaneous computations of the quotient and the remainder of a q-bit number in Pogz([q + n~)l i-1 addition steps.Because it is restn"cted to 2 + 1 numbers, on which it operates one order of magnitude faster than the previously known constant division algorithms, our method appears to be better suited for implementation in super-computer and image processing memory systems.Specifically, it oflers a viable alternative to the simple low-order interleaving in multi-bank memory de-Sagn,as several non-linear skewing schemes no longer involve the speed nor the costs penalties that used to be associated with them.Moreover, since numbers of the form 2n&l include 3,5,7,17,31, 127,257.. .which are ail primes, implementations of the related pn'me memory systems turn out to be affordable as well.