Re: [Haskell-cafe] Mysterious factorial

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