gcd ( x y -- a d )
Factor handbook » The language » Numbers » Mathematical functions » Integer functions

Prev:	align ( m w -- n )
Next:	log2 ( x -- n )

Vocabulary
math

Inputs

x	an integer
y	an integer

Outputs

a	an integer
d	an integer

Word description
Computes the positive greatest common divisor d of x and y, and another value a satisfying:

(a*x - d) mod y == 0

Notes
If d is 1, then a is the inverse of x modulo y.

Examples

USING: kernel math prettyprint ; 54 26 gcd [ . ] bi@
1 2

USING: math prettyprint ; 54 1 * 2 - 26 mod .
0

Definition

USING: kernel math.private ;

IN: math

: gcd ( x y -- a d ) [ 0 1 ] 2dip (gcd) dup 0 < [ neg ] when
    ; inline