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.hi...@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.ka...@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@haskell.org > > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > -- Rafael Gustavo da Cunha Pereira Pinto
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe