UserManual

arygcd

Compute gcd with rational, Gauss, Eisenstein integer.

Functions

binarygcd(a, b)

Return the greatest common divisor of two integers a and b by binary gcd algorithm.

>>> binarygcd(32, 48)
16

arygcd_i(a1, a2, b1, b2)

Return the greatest common divisor of two Gauss-integers a1+a2*i and b1+b2*i by (1+i)-ary gcd algorithm (similar to binary gcd algorithm).

>>> arygcd_i(1, 13, 13, 9)
(-3, 1)
It means gcd(1+13i, 13+9i) = -3+i.

arygcd_w(a1, a2, b1, b2)

Return the greatest common divisor of two Eisenstein-integers a1+a2*w and b1+b2*w by (1-w)-ary gcd algorithm (similar to binary gcd algorithm), where 'w' is the primitive cubic root of unity.

>>> arygcd_w(2, 13, 33, 15)
(4, 5)
It means gcd(2+13w, 33+15w) = 4+5w.

Last-modified: 2007-03-06 (Ва) 18:44:14