A systolic algorithm for extended GCD computation (Q1110555)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A systolic algorithm for extended GCD computation |
scientific article; zbMATH DE number 4073059
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A systolic algorithm for extended GCD computation |
scientific article; zbMATH DE number 4073059 |
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
