## 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