# Paste: gcd

Author: kib2 factor Tue, 23 Dec 2008 17:21:00
Plain Text |
```! ==== testkib.factor ====
! Copyright Kibleur Christophe - 2008

IN: testkib

! prettyprint for using "."
USING: prettyprint io math kernel ;

: pgcd ( a b -- c )
2dup ! Stack is now : a b a b
/i dup ! Stack is now : a b a b remainder
! Returns b if remainder=0, else call pgcd on last two elements
0 = [ drop swap drop ] [ drop swap pgcd ] if . ;

10 4 pgcd ```

## Annotation: gcd

Author: kib2 factor Tue, 23 Dec 2008 22:56:42
Plain Text |
```! ==== testkib.factor ====
! Copyright Kibleur Christophe - 2008
! Computes the gcd of 2 integers

IN: testkib
! launch with ./factor testkib.factor

USING: prettyprint math math.order kernel ;

: pgcd ( a b -- c )
! We first need to swap a and b if a < b
2dup
< [ swap ] when

! Computation :
2dup ! Stack is now : a b a b
mod dup ! Stack is now : a b r r (where r is the remainder)
! If remainder is null, returns b
zero? [ drop min ] ! stack was sort of : a b r f/t so it becomes a b
! else call pgcd on b and remainder
[ min pgcd ] if ;

! this is also possible : 411 685 pgcd .
685 411 pgcd .  ```

## Annotation: cleaner?

Author: mrjbq7 factor Wed, 24 Dec 2008 00:14:05
Plain Text |
```: jgcd ( a b -- c )
dup zero?
[ drop ]
[ [ mod ] keep swap jgcd ]
if
;
```