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).


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.


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