fact2 is O(log n) while fact is O(n). fact2 is partitioning the problem.

But fact2 sparks off two recursive calls. If we assume that multiplication is a constant-time operations, both algorithms have the same asymptotic running time (try a version that operates on Ints). For Integers, this assumption is, of course, false ... Cheers, Ralf

On Wed, Dec 30, 2009 at 08:57, Artyom Kazak wrote:

...

Why fact2 is quicker than fact?!

fact2 :: Integer -> Integer fact2 x = f x y where f n e | n < 2 = 1

| e == 0 = n * (n - 1) | e > 0 = (f n (e `div` 2)) * (f (n - (e * 2)) (e `div` 2))

y = 2 ^ (truncate (log (fromInteger x) / log 2))

fact :: Integer -> Integer fact 1 = 1 fact n = n * fact (n - 1)

I tried to write tail-recursive fact, fact as "product [1..n]" - fact2 is quicker!

fact2 1000000 == fact 1000000 - I tested.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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

Am Mittwoch 30 Dezember 2009 17:28:37 schrieb Roel van Dijk:

I can't offer much insight but could the answer lie in the Integer type? I suspect that with a sufficiently large fixed Int type (2^14 bits?) the performance of the two functions would be almost equal.

For fact (10^6), we'd need rather 2^24 bits for the performance to be comparable. Imagine such an ALU :D

Could it be that the second function delays the multiplication of large numbers as long as possible? The divide-and-conquer approach?

Exactly.

On Wed, Dec 30, 2009 at 10:35 AM, Ralf Hinze wrote:

As an aside, in one of my libraries I have a combinator for folding a list in a binary-subdivision scheme.

...

foldm                         :: (a -> a -> a) -> a -> [a] -> a

I would use: foldm :: Monoid m => [m] -> m Which is just a better implementation of mconcat / fold. The reason I prefer this interface is that foldm has a precondition in order to have a simple semantics: the operator you're giving it has to be associative. I like to use typeclasses to express laws. You don't need to prove anything to use a function, but you do often need to prove something to make an instance of a typeclass. Fortunately Monoid already has what we need.

...

foldm (*) e x   | null x                    =  e   | otherwise                 =  fst (rec (length x) x)   where rec 1 (a : as)        =  (a, as)         rec n as              =  (a1 * a2, as2)           where m             =  n `div` 2                 (a1, as1)     =  rec (n - m) as                 (a2, as2)     =  rec m       as1

Then factorial can be defined more succinctly

...

factorial n = foldm (*) 1 [1 .. n]

Cheers, Ralf _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe