El algoritmo binario del mcd

4 Comentarios

1. Haskell

   import Test.QuickCheck mcd :: Integer -> Integer -> Integer mcd a 0 = a mcd 0 b = b mcd a b | a == b = a | even a && even b = 2 * mcd (div a 2) (div b 2) | even a && odd b = mcd (div a 2) b | even b = mcd a (div b 2) | a > b = mcd (div (a-b) 2) b | otherwise = mcd a (div (b-a) 2) prop_mcd :: Integer -> Integer -> Property prop_mcd a b = a >= 0 && b >= 0 ==> mcd a b == gcd a b -- *Main> quickCheck prop_mcd -- +++ OK, passed 100 tests.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   import Test.QuickCheck   mcd :: Integer -> Integer -> Integer mcd a 0 = a mcd 0 b = b mcd a b |      a == b      = a         | even a && even b = 2 * mcd (div a 2) (div b 2)         | even a && odd  b =     mcd (div a 2)      b         |           even b =     mcd      a    (div b 2)         |      a >  b      =     mcd (div (a-b) 2)  b         | otherwise        =     mcd    a  (div (b-a) 2)   prop_mcd :: Integer -> Integer -> Property prop_mcd a b = a >= 0 && b >= 0 ==> mcd a b == gcd a b   -- *Main> quickCheck prop_mcd -- +++ OK, passed 100 tests.

   Responder

2. Haskell

   mcd :: Integer -> Integer -> Integer mcd a 0 = a mcd 0 b = b mcd a b | even a == True && even b == True = 2 * mcd (div a 2) (div b 2) | even a /= even b = mcd (div par 2) imp | odd a == True && odd b == True = mcd (div (m-m') 2) m' | a == b = a where par = head $ filter (even) [a,b] imp = head $ filter (odd) [a,b] m = max a b m' = min a b prop_equivalentes :: Integer -> Integer -> Property prop_equivalentes a b = min a b >= 0 ==> mcd a b == gcd a b -- *Main> quickCheck prop_equivalentes -- +++ OK, passed 100 tests.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   mcd :: Integer -> Integer -> Integer mcd a 0 = a mcd 0 b = b mcd a b | even a == True && even b == True  = 2 * mcd (div a 2) (div b 2)         | even a /= even b                  = mcd (div par 2) imp         | odd a == True && odd b == True    = mcd (div (m-m') 2) m'         | a == b                            = a      where par  = head $ filter (even) [a,b]            imp  = head $ filter (odd) [a,b]            m    = max a b            m'   = min a b   prop_equivalentes :: Integer -> Integer -> Property prop_equivalentes a b =      min a b >= 0 ==> mcd a b == gcd a b   -- *Main>  quickCheck prop_equivalentes -- +++ OK, passed 100 tests.

   Responder

   1. Haskell

      -- Definición simplificada mcd :: Integer -> Integer -> Integer mcd a 0 = a mcd 0 b = b mcd a b | even a && even b = 2 * mcd (div a 2) (div b 2) | even a /= even b = mcd (div par 2) imp | odd a && odd b = mcd (div (m-m') 2) m' | a == b = a where par = head $ filter even [a,b] imp = head $ filter odd [a,b] m = max a b m' = min a b

      1 2 3 4 5 6 7 8 9 10 11 12 13

      -- Definición simplificada   mcd :: Integer -> Integer -> Integer mcd a 0 = a mcd 0 b = b mcd a b | even a  && even b   = 2 * mcd (div a 2) (div b 2)         | even a /= even b    = mcd (div par 2) imp         | odd a  && odd b     = mcd (div (m-m') 2) m'         | a == b                            = a      where par  = head $ filter even [a,b]            imp  = head $ filter odd [a,b]            m    = max a b            m'   = min a b

      Responder

3. Haskell

   import Test.QuickCheck mcd :: Integer -> Integer -> Integer mcd 0 a = a mcd a b | b == 0 || b == a = a | even a && even b = 2 * mcd (div a 2) (div b 2) | odd a && odd b && a>b = mcd (div (a-b) 2) b | even a && odd b = mcd (div a 2) b | otherwise = mcd b a prop_mcd :: Integer -> Integer -> Property prop_mcd a b = a>=0 && b>=0 ==> mcd a b == gcd a b -- *Main> quickCheck prop_mcd -- +++ OK, passed 100 tests.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   import Test.QuickCheck   mcd :: Integer -> Integer -> Integer mcd 0 a = a mcd a b | b == 0 || b == a = a         | even a && even b = 2 * mcd (div a 2) (div b 2)         | odd a && odd b && a>b = mcd (div (a-b) 2) b         | even a && odd b = mcd (div a 2) b         | otherwise = mcd b a   prop_mcd :: Integer -> Integer -> Property prop_mcd a b = a>=0 && b>=0 ==> mcd a b == gcd a b   -- *Main> quickCheck prop_mcd -- +++ OK, passed 100 tests.

   Responder