GGT.hs

Dateiinhalt

{-
  Haskell Code zur Vorlesung "Logik und Diskrete Strukuren"
  am 18.05.2016, ausführbar mit GHCI, siehe www.haskell.org
  
  Lehrstuhl TCS, LMU München
  
  Verwendungsbeispiel:
  
    linux-machine:~/S16_LDS> ghci
    GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
    Prelude> :l GGT.hs 
    [1 of 1] Compiling GGT              ( GGT.hs, interpreted )
    Ok, modules loaded: GGT.
    *GGT> ggT(24,15)
    =ggT(24,15)
    =ggT(15,9)
    =ggT(9,6)
    =ggT(6,3)
    =ggT(3,0)
    3
    *GGT> eggT(24,15)
    3 = 0*6 + 1*3
    3 = 1*9 + -1*6
    3 = -1*15 + 2*9
    3 = 2*24 + -3*15
    (3,2,-3)
    *GGT>     
-}


module GGT where

import Debug.Trace -- damit man sieht, wie gerechnet wird


--ggT(a,b) = trace ("=ggT("++(show a)++","++(show b)++")") $ ggT'(a,b) -- Variante ohne Vertauschung
ggT(a,b) = trace ("=ggT("++(show a)++","++(show b)++")") $ ggTs(a,b)   -- Variante mit  Vertauschung

ggT'(a,b)
 | a == 0    = b
 | b == 0    = a
 | b >  a    = ggT(b,a)
 | otherwise = ggT(a `mod` b, b) 
-- "a `mod` b" ist ad-hoc Infix-Schreibweise für "mod a b"
 
-- Mit integrierter Vertauschung:
ggTs (a,b)
 | a == 0    = b
 | b == 0    = a
 | b >  a    = ggT(b,a)
 | otherwise = ggT(b,a `mod` b)

-- Erweiterter Euklidischer Algorithmus: 
-- ohne Ausdruck der Berechnung  
eggT' (a,b)
  | a == 0  = (b,0,1)
  | b == 0  = (a,1,0)
  | b > a   = (d,t,s) 
  where  (d,s,t) = eggT'(b,a)
eggT' (a,b) = (d,s,t-s*(a `div` b))  
  where  (d,t,s) = eggT'(b,a `mod` b)  

-- mit Ausdruck der Berechnung  
eggT (a,b)
  | a == 0    = (b,0,1)
  | b == 0    = (a,1,0)
  | b > a     = (d,t,s) 
  where (d,s,t) = eggT(b,a)
eggT (a,b) =          
    let r@(d',s',t') = (d,s,t-s*(a `div` b))
    in  trace ((show d') ++ " = " ++ (show s')++"*"++(show a)++" + "++(show t')++"*"++(show b)) $ r
  where (d,t,s) = eggT(b,a `mod` b)