(*************************************************
 ** NumberTheory.sml
 ** sml
 **
 ** Aleksandar Nanevski
 **
 **
 ** For now only gcd, but other number theoretic
 ** algorithms (e.g. factoring) should be added 
 ** here.
 *************************************************)


structure NumberTheory :> 
    NUMBER_THEORY where type int = InfiniteInteger.int = 
struct
    open InfiniteInteger 
	
    fun gcd(x, y) = 
	let fun bin' k = 
	    let fun loop (x, y) =
		let val t = x - y 
		in
		    if t = zero then <<(x, Word.fromInt k)
		    else
			let val {odd=t',...} = toOddExp t
			in
			    if (Int.>(sign t', 0)) then loop (t', y)
			    else loop (x, ~ t')
			end
		end
	    in
		loop
	    end
	
	    (* assumes x > y *)
	    fun gcd'(x, y) = 
		if (y = zero) then x
		else
		    let val {odd=x', exp=k1} = toOddExp x
			val {odd=y', exp=k2} = toOddExp y
		    in
			bin' (Int.min(k1, k2)) (x', y')
		    end
	in
	    let val (x, y) = (abs x, abs y)
	    in
		if x < y then 
		    if x = zero then y else
			let val (_, r) = quotrem(y, x)
			in
			    gcd'(x, r)
			end
		else 
		    if y = zero then x else
			let val (_, r) = quotrem(x, y)
			in
			    gcd'(y, r)
			end
	    end
	end
end