[email protected]
[Top] [All Lists]

Re: [Haskell-cafe] Mysterious factorial

Subject: Re: [Haskell-cafe] Mysterious factorial
From: Ralf Hinze
Date: Wed, 30 Dec 2009 13:13:26 +0100
> 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 <[email protected]> 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
> > [email protected]
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

<Prev in Thread] Current Thread [Next in Thread>