fact2 sparks 2*n multiplications for every (n^2) factors<br><br>fact sparks n multiplications for every n factors<br><br><br><div class="gmail_quote">On Wed, Dec 30, 2009 at 10:13, Ralf Hinze <span dir="ltr"><<a href="mailto:ralf.hinze@comlab.ox.ac.uk">ralf.hinze@comlab.ox.ac.uk</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im">> fact2 is O(log n) while fact is O(n).<br>
> fact2 is partitioning the problem.<br>
<br>
</div>But fact2 sparks off two recursive calls. If we assume that<br>
multiplication is a constant-time operations, both algorithms<br>
have the same asymptotic running time (try a version that<br>
operates on Ints). For Integers, this assumption is, of course,<br>
false ...<br>
<br>
Cheers, Ralf<br>
<div><div></div><div class="h5"><br>
> On Wed, Dec 30, 2009 at 08:57, Artyom Kazak <<a href="mailto:artyom.kazak@gmail.com">artyom.kazak@gmail.com</a>> wrote:<br>
> > Why fact2 is quicker than fact?!<br>
> ><br>
> > fact2 :: Integer -> Integer<br>
> > fact2 x = f x y<br>
> > where<br>
> > f n e | n < 2 = 1<br>
> ><br>
> > | e == 0 = n * (n - 1)<br>
> > | e > 0 = (f n (e `div` 2)) * (f (n - (e * 2)) (e `div` 2))<br>
> ><br>
> > y = 2 ^ (truncate (log (fromInteger x) / log 2))<br>
> ><br>
> > fact :: Integer -> Integer<br>
> > fact 1 = 1<br>
> > fact n = n * fact (n - 1)<br>
> ><br>
> > I tried to write tail-recursive fact, fact as "product [1..n]" - fact2 is<br>
> > quicker!<br>
> ><br>
> ><br>
> > fact2 1000000 == fact 1000000 - I tested.<br>
> ><br>
> > _______________________________________________<br>
> > Haskell-Cafe mailing list<br>
> > <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
> > <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Rafael Gustavo da Cunha Pereira Pinto<br><br>