
30 Dec
2009
30 Dec
'09
2:37 p.m.
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