timjb · November 1, 2011 22:49
diff --git a/Euclid.hs b/Euclid.hs
 -- Extended Euclidean algorithm
 -- Preconditions: gcd(a, b) = 1, a > b
 -- Postcondition: (fst result) * a + (snd result) * b = 1

 euc :: (Integral a) => a -> a -> (a, a)
 euc a b = case b of
            1 -> (0, 1)
            _ -> let (e, f) = euc b d
                 in (f, e - c*f)
  where c = a `div` b
        d = a `mod` b
	-- Extended Euclidean algorithm
	-- Preconditions: gcd(a, b) = 1, a > b
	-- Postcondition: (fst result) * a + (snd result) * b = 1

	euc :: (Integral a) => a -> a -> (a, a)
	euc a b = case b of
	1 -> (0, 1)
	_ -> let (e, f) = euc b d
	in (f, e - c*f)
	where c = a `div` b
	d = a `mod` b
No results found