Factorial módulo

3 Comentarios

1. Haskell

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

   1 2 3

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

   Responder

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

      Haskell

      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)

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

      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’

      Responder

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

         Haskell

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

         1 2 3 4

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

         Responder