Paste: gcd

! ==== 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

! ==== 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?

: jgcd ( a b -- c )
    dup zero? 
    [ drop ] 
    [ [ mod ] keep swap jgcd ]
    if
    ; 

New Annotation