fact2 is O(log n) while fact is O(n).<br><br>fact2 is partitioning the problem.<br><br><div class="gmail_quote">On Wed, Dec 30, 2009 at 08:57, Artyom Kazak <span dir="ltr">&lt;<a href="mailto:artyom.kazak@gmail.com">artyom.kazak@gmail.com</a>&gt;</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;"><br>Why fact2 is quicker than fact?!<br><br>fact2 :: Integer -&gt; Integer<br>fact2 x = f x y<br>
where<br>f n e | n &lt; 2 = 1<br>      | e == 0 = n * (n - 1)<br>      | e &gt; 0 = (f n (e `div` 2)) * (f (n - (e * 2)) (e `div` 2))<br>
y = 2 ^ (truncate (log (fromInteger x) / log 2))<br><br>fact :: Integer -&gt; Integer<br>fact 1 = 1<br>fact n = n * fact (n - 1)<br><br>I tried to write tail-recursive fact, fact as &quot;product [1..n]&quot; - fact2 is 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></blockquote></div><br><br clear="all"><br>-- <br>Rafael Gustavo da Cunha Pereira Pinto<br><br>