[Haskell-cafe] Mysterious factorial

[Rafael Gustavo da Cunha Pereira Pinto]

fact2 sparks 2*n multiplications for every (n^2) factors

fact sparks n multiplications for every n factors


On Wed, Dec 30, 2009 at 10:13, Ralf Hinze <ralf.hinze at comlab.ox.ac.uk>wrote:

> > 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 <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/37fdcf92/attachment.html