A Systolic Algorithm for Integer GCD Computation. Revision
Richard P. Brent, H. T. Kung · Defense Technical Information Center (DTIC) · 1984
In this document the authors show 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 array of O(n) identical systolic cells, each of which is a finite-state machine with connections to its nearest neighbours. (Author)