Abstract :
The execution times of several algorithms for computing the GCD of arbitrary precision integers are compared. These algorithms are the known ones (Euclidean, binary, plus-minus), and the improved variants of these for multidigit computation (Lehmer and similar), as well as new algorithms introduced by the author: an improved Lehmer algorithm using two digits in partial consequence computation, and a generation of the binary algorithm using a new concept of modular conjugates. The last two algorithms prove to be the fastest of all, giving a speedup of six to eight times over the classical Euclidean scheme, and two times over the best currently known algorithms. Also, the generalized binary algorithm is suitable for systolic parallelization in a least-significant digits first pipelined manner
Keywords :
digital arithmetic; pipeline arithmetic; systolic arrays; Euclidean; GCD algorithms; Lehmer; binary; improved Lehmer algorithm; least-significant digits first; modular conjugates; multidigit computation; partial consequence computation; plus-minus; precision integers; systolic parallelization; Algebra; Algorithm design and analysis; Arithmetic; Artificial intelligence; Computational Intelligence Society; Concurrent computing;
