A systolic VLSI array for integer GCD computation
77. R. P. Brent and
H. T. Kung,
A systolic VLSI array for integer GCD computation,
in ARITH-7, Proceedings of the Seventh Symposium on
Computer Arithmetic (edited by K. Hwang), IEEE CS Press, 1985,
118-125.
Abstract:
dvi (3K),
pdf (82K),
ps (29K).
Paper:
pdf (1196K).
Abstract
It is shown that the greatest common divisor of two n-bit
integers (given in the usual binary representation) can be computed in
time O(n) on a linear systolic array of O(n) identical
cells.
Comments
It is not known if the integer GCD problem is in the complexity
class NC. This paper gives the fastest known parallel algorithm
using a number of processors linear in n.
For related work see
[79,
82].
The polynomial GCD problem is discussed in
[73,
79].
Go to next publication
Return to Richard Brent's index page