[Haskell-cafe] Mysterious factorial

[Ralf Hinze]

> 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