Title :
A systolic algorithm for integer GCD computation
Author :
Brent, R.P. ; Rung, H.T.
Author_Institution :
Centre for Mathematical Analysis Australian National University Canberra, A.C.T. 2601 Australia
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.
Keywords :
Arrays; Convergence; Hardware; Parallel algorithms; Pipelines; Polynomials; Very large scale integration;
Conference_Titel :
Computer Arithmetic (ARITH), 1985 IEEE 7th Symposium on
Conference_Location :
Urbana, IL,
DOI :
10.1109/ARITH.1985.6158931
