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
    0 references
    0 references

    Identifiers