[Haskell-cafe] Mysterious factorial
Ralf Hinze
ralf.hinze at comlab.ox.ac.uk
Wed Dec 30 09:37:08 EST 2009
> fact2 sparks 2*n multiplications for every (n^2) factors
>
> fact sparks n multiplications for every n factors
Okay, let's count:
> data Tree a = Leaf a | Fork (Tree a) (Tree a)
> deriving (Show)
> fact 1 = Leaf 1
> fact n = Leaf n `Fork` fact (n - 1)
> fact2 x = f x y
> where
> f n e | n < 2 = Leaf 1
> | e == 0 = Leaf n `Fork` Leaf (n - 1)
> | e > 0 = (f n (e `div` 2)) `Fork` (f (n - (e * 2)) (e `div` 2))
> y = 2 ^ (truncate (log (fromInteger x) / log 2))
> size (Leaf a) = 0
> size (Fork l r) = 1 + size l + size r
The code now creates a binary tree (instead of performing
a multiplication).
Main> size (fact 1000000)
999999
Main> size (fact2 1000000)
1000008
Convinced?
Cheers, Ralf
More information about the Haskell-Cafe
mailing list