Menu Close

Factorial módulo

Definir la función

   factorialMod :: Integer -> Integer -> Integer

tal que (factorialMod n x) es el factorial de x módulo n. Por ejemplo,

   factorialMod (7+10^9) 100       ==  437918130
   factorialMod (7+10^9) (5*10^6)  ==  974067448

Soluciones

import Data.List (foldl')
 
-- 1ª definición
-- =============
 
factorialMod :: Integer -> Integer -> Integer
factorialMod n x =
  factorial x `mod` n
 
-- (factorial x) es el factorial de x. Por ejemplo,
--    factorial 3  ==  6
factorial :: Integer -> Integer
factorial x = product [1..x]
 
-- 2ª definición
-- =============
 
factorialMod2 :: Integer -> Integer -> Integer
factorialMod2 n x =
  foldl' (prodMod n) 1 [1..x]
 
-- (prodMod n x y) es el producto de x e y módulo n. Por ejemplo,
--    prodMod 3 4 7  ==  1
--    prodMod 5 4 7  ==  -- 3
prodMod :: Integer -> Integer -> Integer -> Integer
prodMod n x y =
  ((x `mod` n) * (y `mod` n)) `mod` n
 
-- Comparación de eficiencia
-- =========================
 
--    λ> factorialMod (7+10^9) (5*10^4)
--    737935835
--    (2.62 secs, 2,601,358,640 bytes)
--    λ> factorialMod2 (7+10^9) (5*10^4)
--    737935835
--    (0.07 secs, 23,471,880 bytes)

3 soluciones de “Factorial módulo

  1. agumaragu1
    factorialMod :: Integer -> Integer -> Integer
    factorialMod n x = foldl aux 1 [1..x]
      where aux a b = mod (a*b) n
    • alerodrod5

      Se puede mejorar bastante si se utiliza la versión impaciente de foldl. Quedaría tal que así

      import Data.List
       
      factorialMod :: Integer -> Integer ->Integer
      factorialMod n x = foldl' aux 1 [1..x]
        where aux a b = mod (a*b) n
       
      factorialMod (7+10^9) (5*10^6)
      974067448
      (1.69 secs, 760,120,496 bytes)
      λ> factorialMod2 (7+10^9) (5*10^6)
      974067448
      (3.39 secs, 1,380,729,928 bytes)

      Donde factorialMod utiliza foldl’

      • angruicam1

        Todavía se me ocurre otra mejora quitando argumentos en la función auxiliar:

        import Data.List (foldl')
         
        factorialMod :: Integer -> Integer -> Integer
        factorialMod n x = foldl' (((`mod` n) .) . (*)) 1 [1..x]

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.