Implentation of Extended Euclidean Algorithm

.gitignore

dist
*.hi
*.o

Bezout.cabal

-- Initial Bezout.cabal generated by cabal init.  For further 
-- documentation, see http://haskell.org/cabal/users-guide/

name:                Bezout
version:             0.1.0.0
-- synopsis:            
-- description:         
license:             PublicDomain
license-file:        LICENSE
author:              Noah Luck Easterly
maintainer:          [email protected]
-- copyright:           
-- category:            
build-type:          Simple
-- extra-source-files:  
cabal-version:       >=1.10

library
  exposed-modules:     Bezout
  -- other-modules:       
  other-extensions:    BangPatterns
  build-depends:       base >=4.7 && <4.8
  -- hs-source-dirs:      
  default-language:    Haskell2010
  ghc-options:         -Wall

Test-Suite test-bezout
  type:                exitcode-stdio-1.0
  main-is:             Test.hs
  build-depends:       base >=4.7 && <4.8, QuickCheck >=2.7 && <2.8
  default-language:    Haskell2010
  ghc-options:         -Wall

Bezout.hs

{-# LANGUAGE BangPatterns #-}
module Bezout (bezout) where

-- http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Description
bezout :: Integer -> Integer -> (Integer, Integer)
bezout u v | au >= av  = go au su 0 av 0 sv
           | otherwise = go av 0 sv au su 0 where
  au = abs u
  av = abs v
  su = signum u
  sv = signum v
  go _ x y 0 _ _ = (x, y)
  go r0 s0 t0 r1 !s1 !t1 = 
    let (q,r2) = r0 `quotRem` r1 
    in go r1 s1 t1 r2 (s0 - q*s1) (t0 - q*t1)

LICENSE

Setup.hs

import Distribution.Simple
main = defaultMain

Test.hs

import Bezout (bezout)
import Test.QuickCheck (quickCheckResult)
import Test.QuickCheck.Test (isSuccess)
import System.Exit (exitFailure,exitSuccess)
main = do
  r <- quickCheckResult bezout_yields_gcd 
  if isSuccess r
    then exitSuccess
    else exitFailure

bezout_yields_gcd :: Integer -> Integer -> Bool
bezout_yields_gcd a b = let (x,y) = bezout a b in x*a + y*b == gcd a b