Mysterious factorial

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Mysterious factorial

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.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mysterious factorial

Rafael Gustavo da Cunha Pereira Pinto-2
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 <[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
Reply | Threaded
Open this post in threaded view
|

Re: Mysterious factorial

Ralf Hinze-2
> 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
Reply | Threaded
Open this post in threaded view
|

Re: Mysterious factorial

Rafael Gustavo da Cunha Pereira Pinto-2
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 <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Mysterious factorial

Ralf Hinze-2
> 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
Reply | Threaded
Open this post in threaded view
|

Re: Mysterious factorial

Roel van Dijk-3
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
Reply | Threaded
Open this post in threaded view
|

Re: Mysterious factorial

Daniel Fischer-4
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
Reply | Threaded
Open this post in threaded view
|

Re: Mysterious factorial

Daniel Fischer-4
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
Reply | Threaded
Open this post in threaded view
|

Re: Mysterious factorial

Ralf Hinze-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Mysterious factorial

Luke Palmer-2
On Wed, Dec 30, 2009 at 10:35 AM, Ralf Hinze <[hidden email]> wrote:
> 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

I would use:

foldm :: Monoid m => [m] -> m

Which is just a better implementation of mconcat / fold.  The reason I
prefer this interface is that foldm has a precondition in order to
have a simple semantics: the operator you're giving it has to be
associative.  I like to use typeclasses to express laws. You don't
need to prove anything to use a function, but you do often need to
prove something to make an instance of a typeclass.  Fortunately
Monoid already has what we need.


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

Re: Mysterious factorial

Ralf Hinze-2
> I would use:
>
> foldm :: Monoid m => [m] -> m
>
> Which is just a better implementation of mconcat / fold.  The reason I
> prefer this interface is that foldm has a precondition in order to
> have a simple semantics: the operator you're giving it has to be
> associative.  I like to use typeclasses to express laws.

That's a valid point. Unfortunately, Haskell is not Coq, so there
is no guarantee that the monoid laws are actually satisfied. And
using a type-class has the downside that you can have only one
instance per type. Maybe, you want to use both `foldm (+) 0' and
`foldm (*) 1'. So the bottom-line is that you should have both
versions.

Cheers, Ralf
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe