Name:
Anonymous
2009-04-21 8:46
ITT: Your favourite implementation of fact.
Mine would be:
fact x = foldr (*) 1 $ takeWhile (/= 1) [x,x-1..]
I wrote it today :3
Name:
Anonymous
2009-04-21 13:17
>>1,3
slow factorials are slow.
primes = 2 : 3 : 5 : 7 : [k + r | k <- [0, 30..], r <- [11, 13, 17, 19, 23, 29, 31, 37], primeTest (k + r)]
where primeTest n = all ((0 /=) . mod n) . takeWhile ((n >=) . join (*)) $ drop 3 primes
bitCount 0 = 0
bitCount n = uncurry (+) . (first bitCount) $ divMod n 2
swing n | n < 33 = genericIndex smallOddSwing n
| True = product pList
where smallOddSwing = [1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179, 2028117, 676039, 16900975, 1300075, 35102025, 5014575, 145422675, 9694845, 300540195, 300540195]
pListA q p prime = let x = div q prime in case x of
0 -> case p of
1 -> []
_ -> [p]
_ -> pListA x (p * prime ^ (mod x 2)) prime
pListB = (filter ((1==) . flip mod 2 . div n) . takeWhile (<= div n 3) $ dropWhile ((<= n) . (^2)) primes)
pListC = takeWhile (<= n) $ dropWhile (<= div n 2) primes
pList = (concatMap (pListA n 1) . takeWhile ((n >=) . (^2)) $ tail primes) ++ pListB ++ pListC
recFactorial n | n < 2 = 1
| True = (recFactorial $ div n 2) ^ 2 * swing n
factorial n | n < 20 = product [2..n]
| True = recFactorial n * 2 ^ (n - bitCount n)