> 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe