Re: [Haskell-cafe] Mysterious factorial

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