# Mysterious factorial Classic List Threaded 11 messages Open this post in threaded view
|

## Mysterious factorial

 Why fact2 is quicker than fact?!fact2 :: Integer -> Integerfact2 x = f x ywheref 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 -> Integerfact 1 = 1fact 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 [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Mysterious factorial

 fact2 is O(log n) while fact is O(n).fact2 is partitioning the problem.On Wed, Dec 30, 2009 at 08:57, Artyom Kazak wrote: Why fact2 is quicker than fact?!fact2 :: Integer -> Integerfact2 x = f x y wheref 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 -> Integerfact 1 = 1fact 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 [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe -- Rafael Gustavo da Cunha Pereira Pinto _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Mysterious factorial

 > 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 <[hidden email]> 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 > > [hidden email] > > http://www.haskell.org/mailman/listinfo/haskell-cafe> _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Mysterious factorial

 fact2 sparks 2*n multiplications for every (n^2) factorsfact sparks n multiplications for every n factorsOn Wed, Dec 30, 2009 at 10:13, Ralf Hinze 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 <[hidden email]> 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 > > [hidden email] > > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Rafael Gustavo da Cunha Pereira Pinto _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Mysterious factorial

 > fact2 sparks 2*n multiplications for every (n^2) factors > > fact sparks n multiplications for every n factors Okay, let's count: > data Tree a = Leaf a | Fork (Tree a) (Tree a) >   deriving (Show) > fact 1 = Leaf 1 > fact n = Leaf n `Fork` fact (n - 1) > fact2 x = f x y >   where >   f n e | n < 2  = Leaf 1 >         | e == 0 = Leaf n `Fork` Leaf (n - 1) >         | e > 0  = (f n (e `div` 2)) `Fork` (f (n - (e * 2)) (e `div` 2)) >   y = 2 ^ (truncate (log (fromInteger x) / log 2)) > size (Leaf a) = 0 > size (Fork l r) = 1 + size l + size r The code now creates a binary tree (instead of performing a multiplication). Main> size (fact 1000000) 999999 Main> size (fact2 1000000) 1000008 Convinced? Cheers, Ralf _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Mysterious factorial

 I can't offer much insight but could the answer lie in the Integer type? I suspect that with a sufficiently large fixed Int type (2^14 bits?) the performance of the two functions would be almost equal. Could it be that the second function delays the multiplication of large numbers as long as possible? The divide-and-conquer approach? _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Mysterious factorial

 In reply to this post by Artyom Kazak Am Mittwoch 30 Dezember 2009 11:57:28 schrieb Artyom Kazak: > 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. If you follow the evaluation of fact2, it is basically the same as fact3 n = binaryMult [1 .. n] where binaryMult [p] = p binaryMult xs = binaryMult (pairMult xs) pairMult (x:y:zs) = x*y : pairMult zs pairMult xs = xs , just without the list construction, but with a few more ones [aside: You should subtract one from the exponent of y. As it is, in the first call to f, the second factor is always 1 because x < 2*y. Doesn't make much of a difference regarding performance, but it seems cleaner.]. Perhaps fact3 is a little easier to follow. Looking at fact3 (2^k), we see that in the first iteration of binaryMult, 2^(k-1) products of small integers (<= k+1 bits) are carried out. These multiplications are fast. In the second iteration, we have 2^(k-2) products of still small integers (<= 2*k bits). These multiplications are a tad slower, but still fast. In the third iteration, we have 2^(k-3) products of integers of (<= k*2^2 bits) and so on. We see that the overwhelming majority of the 2^k-1 multiplications carried out don't involve huge numbers and thus are relatively fast (for k = 32, no multiplication in the first five iterations involves a number with more than 1000 bits, so no more than 3% of the multiplications involve large numbers; for k = 20, the first product with more than 100 bits is produced in the sixth iteration, so less than 20000 multiplications involve a number with more than 1000 bits, less than 1000 multiplications have a factor with more than 10000 bits, less than 128 have a factor with more than 100000 bits). If the factorial is computed sequentially, like fact0 n = foldl' (*) 1 [2 .. n] -- or product [2 .. n], just don't build huge thunks like in fact above , you have many multiplications involving one huge number (and one small), since fact k has of the order of k*log k bits. 1000! has about 8500 bits, 10000! has about 120000 bits and 100000! has about 1.5 million bits. So that way, computing the factorial of 2^20 needs more than 990000 multiplications where one factor has more than 100000 bits and over 900000 multiplications where one factor has more than one million bits. Since multiplications where one factor is huge take long, even if the other factor is small, we see why a sequential computation of a factorial is so much slower than a tree-like computation._______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Mysterious factorial

 In reply to this post by Roel van Dijk-3 Am Mittwoch 30 Dezember 2009 17:28:37 schrieb Roel van Dijk: > I can't offer much insight but could the answer lie in the Integer > type? I suspect that with a sufficiently large fixed Int type (2^14 > bits?) the performance of the two functions would be almost equal. For fact (10^6), we'd need rather 2^24 bits for the performance to be comparable. Imagine such an ALU :D > > Could it be that the second function delays the multiplication of > large numbers as long as possible? The divide-and-conquer approach? Exactly. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Mysterious factorial

 As an aside, in one of my libraries I have a combinator for folding a list in a binary-subdivision scheme. > foldm                         :: (a -> a -> a) -> a -> [a] -> a > foldm (*) e x >   | null x                    =  e >   | otherwise                 =  fst (rec (length x) x) >   where rec 1 (a : as)        =  (a, as) >         rec n as              =  (a1 * a2, as2) >           where m             =  n `div` 2 >                 (a1, as1)     =  rec (n - m) as >                 (a2, as2)     =  rec m       as1 Then factorial can be defined more succinctly > factorial n = foldm (*) 1 [1 .. n] Cheers, Ralf _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe