1votos

Factorizar el factorial en Haskell

por josejuan hace 5 años

Ésta no es la solución más eficiente, pero es bastante rápida y creo que elegante. Además, si asumimos que el grupo de las factorizaciones está implementado (parece razonable), es inmediato.

Obtener la descomposición en factores primos (con sus exponentes, claro) del factorial de un número natural dado.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
-- Si representamos la factorización de un número como 
-- 
--          [p1^k1, p2^k2, p3^k3, ...] 
-- 
-- en Haskell, aunque no es una forma más óptima, podemos 
-- representarlo como 
 
data Factorization a = Factors [(a, a)] deriving Show 
 
-- el conjunto de factorizaciones forman un grupo abeliano (como la suma), 
-- en el que el elemento neutro (el 0 en la suma) es la factorización 1^k 
-- (única, aunque con múltiples representaciones) y la composición (el operador 
-- suma) es el producto de las factorizaciones, por ejemplo 
-- 
--      [2^a 3^b] · [3^c 5^d] = [2^a 3^(b+c) 5^d] 
-- 
-- (que es como hacer A+B=C pero en éste grupo de factorizaciones) 
-- 
-- así, dada una lista de factorizaciones 
-- 
--      [f1, f2, f3, ...] 
-- 
-- podemos reducirlo a una única factorización aplicando la operación interna 
-- (que viene a ser como reducir una lista de números sumándolos todos). 
-- 
-- Esta operación puede realizarse en cualquier orden (pues es abeliano, como 
-- la suma) y en particular paralelizando el proceso (como la suma). 
-- 
-- Por otro lado, el factorial de `n` es el producto de los números 
-- 
--      1 · 2 · 3 ... (n-1) n 
-- 
-- que es una lista de factorizaciones como la anterior ([f1, f2, ...]), 
-- basta por tanto aplicar la reducción anterior para obtener la factorización 
-- del factorial. 
 
-- En Haskell, podemos representar el grupo abeliano como un monoide (en este 
-- caso conmutativo), sea éste monoide 
 
instance Integral a => Monoid (Factorization a) where 
 
-- Entonces, calcular la factorización del factorial, es recucir el monoide, 
-- que en Haskell es `mconcat` 
 
facfac = mconcat . map factorization . enumFromTo 2 
 
-- Y ya está (aunque como no he visto éste monoide implementado lo tenemos que 
-- hacer nosotros, claro, está abajo, pero es lo suficientemente general como 
-- para que sí estuviera en alguna librería). 
 
 
 
-- De éste modo, pueden calcularse las factorizaciones de factoriales bastante 
-- grandes, por ejemplo, en un hilo AMD Phenom(tm) II X6 a 2,7GHz le toma 1,24seg 
-- calcular la factorización del factorial 100000! (un número entorno 10e460000). 
 
-- El método, no obstante, admite múltiples optimizaciones adhoc (ej. la más 
-- agresiva sería dejar constantes en tamaño todos los arrays asociados a cada 
-- factorización, para combinar, sólo hay que sumar uno a uno los elementos del 
-- array, muy rápido usando SSE, OpenMP, etc...). 
 
-- En cualquier caso, existe una forma MUCHO más rápida... :D 
 
 
 
 
-------------------------------------------------------------------------- 
-- El código completo y algunas notas sobre el rendimiento 
 
import Data.List 
import Data.Monoid 
import Data.Numbers.Primes 
import Control.Parallel 
import System.Environment 
 
-- la mejor representación en este caso, sería un vector mutable (para acumular 
-- una factorización sobre otra preexistente) o como mínimo Map, para que el coste 
-- de actualización sea O(min(n,m)) y no como es ahora O(max(n,m)) 
data Factorization a = Factors [(a, a)] deriving Show 
 
factorization = Factors . map (\ps -> (head ps, length ps)) . group . primeFactors 
 
instance Integral a => Monoid (Factorization a) where 
  mempty = Factors [] 
  mappend (Factors []) fs = fs 
  mappend fs (Factors []) = fs 
  mappend xfs@(Factors (xf@(x, a):xs)) yfs@(Factors (yf@(y, b):ys)) = 
    case x `compare` y of 
      EQ -> Factors ((x, a + b):ms) 
      LT -> Factors (xf:ns) 
      GT -> Factors (yf:os) 
    where Factors ms = mappend (Factors xs) (Factors ys) 
          Factors ns = mappend (Factors xs) yfs 
          Factors os = mappend xfs (Factors ys) 
 
-- paralelización del plegamiento de la secuencia monoidal (no tunned!!) 
-- no obstante, el útil porque permite ir reduciendo con cadenas cortas 
-- es decir, va uniendo cadenas de longitud similar y no cadenas cortas 
-- con una cadena muy grande 
  mconcat [] = mempty 
  mconcat [x] = x 
  mconcat xs = (left' `par` right') `pseq` (left' `mappend` right') 
      where size = length xs 
            index = (size + size `mod` 2) `div` 2 
            (left, right) = splitAt index xs 
            left' =  mconcat left 
            right' = mconcat right 
 
facfac = mconcat . map factorization . enumFromTo 2 
 
main = getArgs >>= print . facfac . read . head 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.