[email protected]
[Top] [All Lists]

[Haskell-cafe] Mysterious factorial

Subject: [Haskell-cafe] Mysterious factorial
From: Artyom Kazak
Date: Wed, 30 Dec 2009 13:57:28 +0300

Why fact2 is quicker than fact?!

fact2 :: Integer -> Integer
fact2 x = f x y
where
f n e | n < 2 = 1
| e == 0 = n * (n - 1)
| e > 0 = (f n (e `div` 2)) * (f (n - (e * 2)) (e `div` 2))
y = 2 ^ (truncate (log (fromInteger x) / log 2))

fact :: Integer -> Integer
fact 1 = 1
fact n = n * fact (n - 1)

I tried to write tail-recursive fact, fact as "product [1..n]" - fact2 is quicker!


fact2 1000000 == fact 1000000 - I tested.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
<Prev in Thread] Current Thread [Next in Thread>