A systolic algorithm for extended GCD computation (Q1110555)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A systolic algorithm for extended GCD computation |
scientific article |
Statements
A systolic algorithm for extended GCD computation (English)
0 references
1987
0 references
The systolic algorithm of R. P. Brent and H. T. Kung is extended to find - for positive integers a,b - integers u,v,g such that \(ua+vb=g\), where g is gcd(a,b). It is claimed that this algorithm - which is O(n) when performed on systolic cells - is superior to Purdy's one; also its use in reducing rational numbers to standard form is presented.
0 references
computational number theory
0 references
greatest common divisor
0 references
systolic algorithm
0 references
