[Haskell-cafe] Mysterious factorial

[Rafael Gustavo da Cunha Pereira Pinto]

fact2 is O(log n) while fact is O(n).

fact2 is partitioning the problem.

On Wed, Dec 30, 2009 at 08:57, Artyom Kazak <artyom.kazak at gmail.com> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>


-- 
Rafael Gustavo da Cunha Pereira Pinto
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091230/d189f09b/attachment.html