Quantcast

ANN: combinatorics

classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

ANN: combinatorics

wren ng thornton
--------------------------------------------
-- combinatorics 0.1.0
--------------------------------------------

The combinatorics package offers efficient *exact* computation of common
combinatorial functions like the binomial coefficients and factorial.
(For fast *approximations*, see the math-functions package instead.)


--------------------------------------------
-- Long Description
--------------------------------------------

* Math.Combinatorics.Primes: provides the prime numbers via Runciman's
lazy wheel sieve algorithm. Provided here since efficient algorithms for
combinatorial functions often require prime numbers. The current version
memoizes the primes as an infinite list CAF, which could lead to memory
leaks in long-running programs with irregular access to large primes.
I'm looking into a GHC patch to allow resetting individual CAFs from
within compiled programs so that you can explicitly decide when to
un-memoize the primes. (In GHCi when you reload a module all the CAFs
are reset. However, there's no way to access this feature from within
compiled programs as yet.)

* Math.Combinatorics.Binomial: offers a fast computation of the binomial
coefficients based on the prime factorization of the result. As it turns
out, it's easier to compute the prime factorization of the answer than
it is to compute the answer directly! And you don't even need the
factorial function to do so. Albeit, with a fast factorial function, the
naive definition of binomial coefficients gives this algorithm a run for
its money.

* Math.Combinatorics.Factorial: offers a fast computation of factorial
numbers. As Peter Luschny comments[1], the factorial function is often
shown as a classic example of recursive functions, like addition of
Peano numbers, however that naive way of computing factorials is
extremely inefficient and does a disservice to those learning about
recursion. The current implementation uses the split-recursive algorithm
which is more than sufficient for casual use. I'm working on
implementing the parallel prime-swing algorithm, which should be a bit
faster still.


[1] http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

--------------------------------------------
-- Links
--------------------------------------------

Homepage:
     http://code.haskell.org/~wren/

Hackage:
     http://hackage.haskell.org/package/combinatorics

Darcs:
     http://community.haskell.org/~wren/combinatorics

Haddock (Darcs version):
 
http://community.haskell.org/~wren/combinatorics/dist/doc/html/combinatorics

--
Live well,
~wren

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

Re: ANN: combinatorics

Roman Cheplyaka-2
* wren ng thornton <[hidden email]> [2012-01-28 23:06:08-0500]

> * Math.Combinatorics.Primes: provides the prime numbers via
> Runciman's lazy wheel sieve algorithm. Provided here since efficient
> algorithms for combinatorial functions often require prime numbers.
> The current version memoizes the primes as an infinite list CAF,
> which could lead to memory leaks in long-running programs with
> irregular access to large primes. I'm looking into a GHC patch to
> allow resetting individual CAFs from within compiled programs so that
> you can explicitly decide when to un-memoize the primes. (In GHCi
> when you reload a module all the CAFs are reset. However, there's no
> way to access this feature from within compiled programs as yet.)

Why not to make it more pure? That is, return a lazy list of Ints (but
not a CAF), which user can throw away by the usual GC means?

The functions from the other modules that use primes would have to be
put in a Reader monad. That would make it a little bit more awkward to
use, but personally I'd prefer that over memory leaks.

--
Roman I. Cheplyaka :: http://ro-che.info/

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

Re: ANN: combinatorics

wren ng thornton
On 1/29/12 5:48 AM, Roman Cheplyaka wrote:

> * wren ng thornton<[hidden email]>  [2012-01-28 23:06:08-0500]
>> * Math.Combinatorics.Primes: provides the prime numbers via
>> Runciman's lazy wheel sieve algorithm. Provided here since efficient
>> algorithms for combinatorial functions often require prime numbers.
>> The current version memoizes the primes as an infinite list CAF,
>> which could lead to memory leaks in long-running programs with
>> irregular access to large primes. I'm looking into a GHC patch to
>> allow resetting individual CAFs from within compiled programs so that
>> you can explicitly decide when to un-memoize the primes. (In GHCi
>> when you reload a module all the CAFs are reset. However, there's no
>> way to access this feature from within compiled programs as yet.)
>
> Why not to make it more pure? That is, return a lazy list of Ints (but
> not a CAF), which user can throw away by the usual GC means?
>
> The functions from the other modules that use primes would have to be
> put in a Reader monad. That would make it a little bit more awkward to
> use, but personally I'd prefer that over memory leaks.

I'd also prefer a more pure solution, but I don't think that the Reader
monad is the right tool here. I played around with that approach, but it
requires extremely invasive changes to client code, obfuscating what
should be simple mathematical formulae. And, it's too fragile, exposing
the implementation in a way that breaks client code should I change a
non-prime-using algorithm to a prime-using one, or vice versa. The
fragility could be partially avoided by providing both prime-using and
non-prime-using algorithms, but then that forces users to decide which
one they want--- and if their only concern is performance, then they'd
have to go through the code-breaking refactoring anyways, just to
determine which is faster for their application.

One alternative I'm exploring is, rather than (only) making the primes
not a CAF, instead make the prime-using functions non-CAFs as well. That
is, provide a makePrimeUsingFunctions function which returns a
record/tuple of all the functions, sharing a stream of primes. This way,
after allocating the functions, they can be used purely just as in the
current model; and when the client wants the primes to be GCed, they can
drop their references to the allocated functions which use those primes
(allocating new functions later, if necessary).

I've used that pattern before for similar resource issues, and it worked
nicely. But how well it works depends a lot on the structure of the
program needing those resources. In particular it can lead to needing to
use the Reader monad (or similar) in order to pass around the functions,
even though the functions themselves can be used purely. Unfortunately I
don't have any large combinatorial programs on hand to assess whether
this would be problematic in practice or not.

--
Live well,
~wren

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

Re: ANN: combinatorics

Balazs Komuves
In reply to this post by wren ng thornton

--------------------------------------------
-- combinatorics 0.1.0
--------------------------------------------

The combinatorics package offers efficient *exact* computation of common
combinatorial functions like the binomial coefficients and factorial.
(For fast *approximations*, see the math-functions package instead.)


Shameless self-promotion: The combinat package (which deliberately
does not try to own the valuable namespace Math.Combinatorics) is
a more extensive combinatorics library:

http://hackage.haskell.org/package/combinat

While the main focus is the generation of combinatorial objects themselves,
counting functions and common number sequences like the above are
also offered.

Even though the binomial and factorial definition in this package are the
naive ones, a quick experiment imply that the differences start show
themselves around 100,000 factorial, or choosing 50,000 elements out
of 100,000, which is probably a rather specialized use case.

The primes function in the combinat package is based on an old Cafe
thread, and actually seems to be faster than the one in the combinatorics
package.

In any case, I may switch to the faster algorithms in the future :)

Balazs


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

Re: ANN: combinatorics

Roman Cheplyaka-2
In reply to this post by wren ng thornton
* wren ng thornton <[hidden email]> [2012-01-29 17:30:34-0500]

> On 1/29/12 5:48 AM, Roman Cheplyaka wrote:
> >* wren ng thornton<[hidden email]>  [2012-01-28 23:06:08-0500]
> >>* Math.Combinatorics.Primes: provides the prime numbers via
> >>Runciman's lazy wheel sieve algorithm. Provided here since efficient
> >>algorithms for combinatorial functions often require prime numbers.
> >>The current version memoizes the primes as an infinite list CAF,
> >>which could lead to memory leaks in long-running programs with
> >>irregular access to large primes. I'm looking into a GHC patch to
> >>allow resetting individual CAFs from within compiled programs so that
> >>you can explicitly decide when to un-memoize the primes. (In GHCi
> >>when you reload a module all the CAFs are reset. However, there's no
> >>way to access this feature from within compiled programs as yet.)
> >
> >Why not to make it more pure? That is, return a lazy list of Ints (but
> >not a CAF), which user can throw away by the usual GC means?
> >
> >The functions from the other modules that use primes would have to be
> >put in a Reader monad. That would make it a little bit more awkward to
> >use, but personally I'd prefer that over memory leaks.
>
> I'd also prefer a more pure solution, but I don't think that the
> Reader monad is the right tool here. I played around with that
> approach, but it requires extremely invasive changes to client code,
> obfuscating what should be simple mathematical formulae. And, it's
> too fragile, exposing the implementation in a way that breaks client
> code should I change a non-prime-using algorithm to a prime-using
> one, or vice versa. The fragility could be partially avoided by
> providing both prime-using and non-prime-using algorithms, but then
> that forces users to decide which one they want--- and if their only
> concern is performance, then they'd have to go through the
> code-breaking refactoring anyways, just to determine which is faster
> for their application.

Makes sense; but doesn't making the monad abstract and putting all
functions in the monad address the fragility issue?

--
Roman I. Cheplyaka :: http://ro-che.info/

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

Re: ANN: combinatorics

Jean-Marie Gaillourdet-3
In reply to this post by wren ng thornton
Hi,
On 29.01.2012, at 23:30, wren ng thornton wrote:

> On 1/29/12 5:48 AM, Roman Cheplyaka wrote:
>> * wren ng thornton<[hidden email]>  [2012-01-28 23:06:08-0500]
>>
>> Why not to make it more pure? That is, return a lazy list of Ints (but
>> not a CAF), which user can throw away by the usual GC means?
>>
>> The functions from the other modules that use primes would have to be
>> put in a Reader monad. That would make it a little bit more awkward to
>> use, but personally I'd prefer that over memory leaks.
>
> I'd also prefer a more pure solution, but I don't think that the Reader monad is the right tool here. I played around with that approach, but it requires extremely invasive changes to client code, obfuscating what should be simple mathematical formulae. And, it's too fragile, exposing the implementation in a way that breaks client code should I change a non-prime-using algorithm to a prime-using one, or vice versa. The fragility could be partially avoided by providing both prime-using and non-prime-using algorithms, but then that forces users to decide which one they want--- and if their only concern is performance, then they'd have to go through the code-breaking refactoring anyways, just to determine which is faster for their application.
>
> One alternative I'm exploring is, rather than (only) making the primes not a CAF, instead make the prime-using functions non-CAFs as well. That is, provide a makePrimeUsingFunctions function which returns a record/tuple of all the functions, sharing a stream of primes. This way, after allocating the functions, they can be used purely just as in the current model; and when the client wants the primes to be GCed, they can drop their references to the allocated functions which use those primes (allocating new functions later, if necessary).

A slight variation on that approach is to use implicit parameters to parameterize your functions by the primes. Something allong the following lines:

> {-# LANGUAGE ImplicitParams, Rank2Types #-}
>  
>  
> data PrimeTable                 -- abstract
>  
> withPrimes :: ((?primes :: PrimeTable) => a) -> a
> withPrimes e = e
>   where
>     ?primes = ...
>  
>  
> factorial :: (?primes :: PrimeTable) => Integer -> Integer
> factorial = ...
>  
> example = withPrimes $ ... factorial n ….

This has the advantage that the user doesn't have to bring all the elemnts of your tuple/record into scope.
And you can have two modules with an almost identical content, one uses the implicit primes argument and the other uses a global CAF for its primes. A user would only have to change his type signatures and strategically add/remove a call to withPrimes when switching.  

Cheers,
  Jean



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

Re: ANN: combinatorics

wren ng thornton
In reply to this post by Balazs Komuves
On 1/30/12 12:55 PM, Balazs Komuves wrote:

>> --------------------------------------------
>> -- combinatorics 0.1.0
>> --------------------------------------------
>>
>> The combinatorics package offers efficient *exact* computation of common
>> combinatorial functions like the binomial coefficients and factorial.
>> (For fast *approximations*, see the math-functions package instead.)
>
> Shameless self-promotion: The combinat package (which deliberately
> does not try to own the valuable namespace Math.Combinatorics) is
> a more extensive combinatorics library:
>
> http://hackage.haskell.org/package/combinat
>
> While the main focus is the generation of combinatorial objects themselves,
> counting functions and common number sequences like the above are
> also offered.

I came across that package when looking around, but I only noticed the
generation of combinatorial objects rather than the counting functions.

As for namespacing, I'd be happy to move things further down to
Math.Combinatorics.Exact (or similar)[1] it's just that
Math.Combinatorics.* seemed not to be used by the numerous packages
floating around this area with different purposes[2], and it seems the
natural place for this sort of work. I think it'd be nice to get a bit
more collaboration among folks doing this stuff so we can (a) clean up
the namespace for this topic, and (b) reduce the amount of duplicated
effort.


[1] I'll probably end up doing that anyways, if I follow through with
the proposed pure solution to the space-leak issue about storing the primes.

[2] HaskellForMaths, gamma, statistics, erf, math-functions, combinat,...


> Even though the binomial and factorial definition in this package are the
> naive ones, a quick experiment imply that the differences start show
> themselves around 100,000 factorial, or choosing 50,000 elements out
> of 100,000, which is probably a rather specialized use case.

In my experiments the threshold was a bit lower, but yes it's special
purpose for people who need exact answers for big problems.


> The primes function in the combinat package is based on an old Cafe
> thread, and actually seems to be faster than the one in the combinatorics
> package.

The primes generator was some old code I had laying around for one of
those online programming challenges; fast enough for the task. I'll
probably trade it in for your algorithm though. One of the things I'm
disappointed by about the current implementation is the memory overhead
for storing the primes. It'd be nice to use chunked arrays of unboxed
integers in order to remove all the pointers; but my attempt at doing so
had catastrophic performance...

--
Live well,
~wren

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

Re: ANN: combinatorics

wren ng thornton
In reply to this post by Roman Cheplyaka-2
On 1/30/12 3:54 PM, Roman Cheplyaka wrote:
> Makes sense; but doesn't making the monad abstract and putting all
> functions in the monad address the fragility issue?

The primary issue with monads is that the syntax is extremely cumbersome
for the expected use case. It'd be like paranoid C where, since order of
evaluation is unspecified, all subexpressions are floated out into
let-bindings. At that point (a) the verbosity is ugly, (b) the code is
much harder to follow, and (c) it's all too easy to introduce errors
where you use x instead of x' or the like.

The semantic model of monads just isn't a good fit for this domain.
There really aren't any side effects going on, there's no sequencing of
actions, there's no "little language" that's being implemented,... I
love me some monads and all, but they just don't fit here.

--
Live well,
~wren

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

Re: ANN: combinatorics

wren ng thornton
In reply to this post by Jean-Marie Gaillourdet-3
On 1/31/12 8:58 AM, Jean-Marie Gaillourdet wrote:
> A slight variation on that approach is to use implicit parameters to parameterize your functions by the primes. Something allong the following lines:

That is another option. However, implicit parameters are GHC-only and
seldom used even in GHC. The RTS-hacking I mentioned in the announcement
would also be GHC-only, which is part of the reason I'd prefer to find a
non-cumbersome way of dealing with the issue purely. As it stands the
library is Haskell98 (with some trivial CPP to make the Haddocks pretty)
and it'd be nice to stay that way.

--
Live well,
~wren

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

Re: ANN: combinatorics

Brent Yorgey-2
In reply to this post by wren ng thornton
On Wed, Feb 01, 2012 at 01:53:03AM -0500, wren ng thornton wrote:
>
> [2] HaskellForMaths, gamma, statistics, erf, math-functions,
> combinat,...

To this list I'd like to add 'species' and also the specialized
'multiset-comb' packages.  The former doesn't build under recent GHCs
but I plan to fix that (and continue extending the library) soon.

Would people be interested in creating a mailing list for those
interested in combinatorics+Haskell?

-Brent

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

Re: ANN: combinatorics

Ivan Lazar Miljenovic
On 3 February 2012 07:11, Brent Yorgey <[hidden email]> wrote:

> On Wed, Feb 01, 2012 at 01:53:03AM -0500, wren ng thornton wrote:
>>
>> [2] HaskellForMaths, gamma, statistics, erf, math-functions,
>> combinat,...
>
> To this list I'd like to add 'species' and also the specialized
> 'multiset-comb' packages.  The former doesn't build under recent GHCs
> but I plan to fix that (and continue extending the library) soon.
>
> Would people be interested in creating a mailing list for those
> interested in combinatorics+Haskell?

I would.

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



--
Ivan Lazar Miljenovic
[hidden email]
IvanMiljenovic.wordpress.com

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

Re: ANN: combinatorics

Carter Schonwald
ditto

On Thu, Feb 2, 2012 at 4:06 PM, Ivan Lazar Miljenovic <[hidden email]> wrote:
On 3 February 2012 07:11, Brent Yorgey <[hidden email]> wrote:
> On Wed, Feb 01, 2012 at 01:53:03AM -0500, wren ng thornton wrote:
>>
>> [2] HaskellForMaths, gamma, statistics, erf, math-functions,
>> combinat,...
>
> To this list I'd like to add 'species' and also the specialized
> 'multiset-comb' packages.  The former doesn't build under recent GHCs
> but I plan to fix that (and continue extending the library) soon.
>
> Would people be interested in creating a mailing list for those
> interested in combinatorics+Haskell?

I would.

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



--
Ivan Lazar Miljenovic
[hidden email]
IvanMiljenovic.wordpress.com

_______________________________________________
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
|  
Report Content as Inappropriate

ANN: exact-combinatorics (re-release of combinatorics)

wren ng thornton
In reply to this post by wren ng thornton
--------------------------------------------
-- exact-combinatorics 0.2.0
--------------------------------------------

I've chosen to rename the combinatorics package to exact-combinatorics
to make it clearer what the purpose of the package is. Anyone
repackaging things for individual distros should use the new package and
not bother with the old one. Sorry for the noise and confusion.

Along the way I've also moved the Math.Combinatorics.* modules to
Math.Combinatorics.Exact.* so as not to claim the whole
Math.Combinatorics namespace. The code is otherwise unchanged so far.
The original announcement is below.



On 1/28/12 11:06 PM, wren ng thornton wrote:

> --------------------------------------------
> -- combinatorics 0.1.0
> --------------------------------------------
>
> The combinatorics package offers efficient *exact* computation of common
> combinatorial functions like the binomial coefficients and factorial.
> (For fast *approximations*, see the math-functions package instead.)
>
>
> --------------------------------------------
> -- Long Description
> --------------------------------------------
>
> * Math.Combinatorics.Primes: provides the prime numbers via Runciman's
> lazy wheel sieve algorithm. Provided here since efficient algorithms for
> combinatorial functions often require prime numbers. The current version
> memoizes the primes as an infinite list CAF, which could lead to memory
> leaks in long-running programs with irregular access to large primes.
> I'm looking into a GHC patch to allow resetting individual CAFs from
> within compiled programs so that you can explicitly decide when to
> un-memoize the primes. (In GHCi when you reload a module all the CAFs
> are reset. However, there's no way to access this feature from within
> compiled programs as yet.)
>
> * Math.Combinatorics.Binomial: offers a fast computation of the binomial
> coefficients based on the prime factorization of the result. As it turns
> out, it's easier to compute the prime factorization of the answer than
> it is to compute the answer directly! And you don't even need the
> factorial function to do so. Albeit, with a fast factorial function, the
> naive definition of binomial coefficients gives this algorithm a run for
> its money.
>
> * Math.Combinatorics.Factorial: offers a fast computation of factorial
> numbers. As Peter Luschny comments[1], the factorial function is often
> shown as a classic example of recursive functions, like addition of
> Peano numbers, however that naive way of computing factorials is
> extremely inefficient and does a disservice to those learning about
> recursion. The current implementation uses the split-recursive algorithm
> which is more than sufficient for casual use. I'm working on
> implementing the parallel prime-swing algorithm, which should be a bit
> faster still.
>
>
> [1] http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
>
> --------------------------------------------
> -- Links
> --------------------------------------------
>
> Homepage:
> http://code.haskell.org/~wren/
>
> Hackage:
> http://hackage.haskell.org/package/combinatorics
>
> Darcs:
> http://community.haskell.org/~wren/combinatorics
>
> Haddock (Darcs version):
>
> http://community.haskell.org/~wren/combinatorics/dist/doc/html/combinatorics
>
>
> --
> Live well,
> ~wren
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe


--
Live well,
~wren

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

Re: ANN: combinatorics

wren ng thornton
In reply to this post by Carter Schonwald
On 2/2/12 6:46 PM, Carter Schonwald wrote:

> On Thu, Feb 2, 2012 at 4:06 PM, Ivan Lazar Miljenovic wrote:
>> On 3 February 2012 07:11, Brent Yorgey wrote:
>>> On Wed, Feb 01, 2012 at 01:53:03AM -0500, wren ng thornton wrote:
>>>>
>>>> [2] HaskellForMaths, gamma, statistics, erf, math-functions,
>>>> combinat,...
>>>
>>> To this list I'd like to add 'species' and also the specialized
>>> 'multiset-comb' packages.  The former doesn't build under recent GHCs
>>> but I plan to fix that (and continue extending the library) soon.
>>>
>>> Would people be interested in creating a mailing list for those
>>> interested in combinatorics+Haskell?
>>
>> I would.
>
> ditto

I don't know how involved I'd be, but I'd join. It's just a side
interest for me (more a curiosity than a hobby at this point), though I
would definitely like to see things better organized and integrated
since it seems like there are a bunch of folks with passing interest in
the area, and it's someplace that Haskell could really shine.

--
Live well,
~wren

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

Re: ANN: combinatorics

Brent Yorgey-2
On Fri, Feb 03, 2012 at 01:06:16AM -0500, wren ng thornton wrote:

> On 2/2/12 6:46 PM, Carter Schonwald wrote:
> >On Thu, Feb 2, 2012 at 4:06 PM, Ivan Lazar Miljenovic wrote:
> >>On 3 February 2012 07:11, Brent Yorgey wrote:
> >>>On Wed, Feb 01, 2012 at 01:53:03AM -0500, wren ng thornton wrote:
> >>>>
> >>>>[2] HaskellForMaths, gamma, statistics, erf, math-functions,
> >>>>combinat,...
> >>>
> >>>To this list I'd like to add 'species' and also the specialized
> >>>'multiset-comb' packages.  The former doesn't build under recent GHCs
> >>>but I plan to fix that (and continue extending the library) soon.
> >>>
> >>>Would people be interested in creating a mailing list for those
> >>>interested in combinatorics+Haskell?
> >>
> >>I would.
> >
> >ditto
>
> I don't know how involved I'd be, but I'd join. It's just a side
> interest for me (more a curiosity than a hobby at this point), though
> I would definitely like to see things better organized and integrated
> since it seems like there are a bunch of folks with passing interest
> in the area, and it's someplace that Haskell could really shine.

OK, I've emailed [hidden email] requesting the creation of a
[hidden email] mailing list (if anyone knows of a better
way to go about this let me know).

-Brent

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

Re: ANN: combinatorics

Daniel Fischer
In reply to this post by wren ng thornton
On Wednesday 01 February 2012, 07:53:03, wren ng thornton wrote:
> > The primes function in the combinat package is based on an old Cafe
> > thread, and actually seems to be faster than the one in the
> > combinatorics package.

Yes, but it has a memory leak. On my box at least, with ghc 6.12, 7.0 and
7.2.

>
> The primes generator was some old code I had laying around for one of
> those online programming challenges; fast enough for the task.
> I'll  probably trade it in for your algorithm though.

Why not use one of the packages on hackage which offer faster prime
generators?

I'm aware of the following usable packages:

- primes: decentish performance if you don't need to sieve high, but not
recommendable if you want to sieve above ~10^7, in my measurements about
the same performance as the algorithm used in combinat, but without memory
leak.

- NumberSieves: The O'Neill sieve, about twice as fast as the primes sieve,
uses less memory (and scales better if you want to sieve to higher limits).

- arithmoi: A segmented Eratosthenes sieve using mutable unboxed arrays.
Much faster than the above and uses less memory.
If you don't like arrays, it also has a priority queue sieve similar to the
O'Neill sieve, but with a more efficient PQ implementation.

> One of the things
> I'm disappointed by about the current implementation is the memory
> overhead for storing the primes. It'd be nice to use chunked arrays of
> unboxed integers in order to remove all the pointers; but my attempt at
> doing so  had catastrophic performance...

arithmoi's Eratosthenes sieve offers the option to get a list of sieve
chunks, basically UArray Int Bool, which gives far more compact storage
than a list of Integers (~33KB per million range, much more compact than an
unboxed array of primes for the reachable ranges) from which the list of
primes can rather efficiently obtained when needed. That may do what you
want well enough.

Cheers,
Daniel

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

Re: ANN: combinatorics

wren ng thornton
On 2/5/12 10:21 AM, Daniel Fischer wrote:
> Why not use one of the packages on hackage which offer faster prime
> generators?

Mostly because I hadn't looked, having had the code already laying
around. I'm not opposed to it, however another goal is to remain
portable to other compilers, which means being H98/H2010 compliant.
NumberSieves uses BangPatterns, but that would be easily remedied if the
author is willing; arithmoi looks quite nice, however it is GHC-only.

--
Live well,
~wren

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

Re: ANN: combinatorics

Daniel Fischer
On Sunday 05 February 2012, 23:14:35, wren ng thornton wrote:
> On 2/5/12 10:21 AM, Daniel Fischer wrote:
> > Why not use one of the packages on hackage which offer faster prime
> > generators?
>
> Mostly because I hadn't looked, having had the code already laying
> around.

Yeah, that's fine, it was just

> > I'll  probably trade it in for your algorithm though.

that made me wonder.

> I'm not opposed to it, however another goal is to remain
> portable to other compilers, which means being H98/H2010 compliant.

A noble goal.

> NumberSieves uses BangPatterns, but that would be easily remedied if the
> author is willing; arithmoi looks quite nice, however it is GHC-only.

The curse of striving for efficiency.
"Portability is on the to-do list (with low priority, however)."
It just climbed a place.

Cheers,
Daniel


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

Re: ANN: combinatorics

wren ng thornton
On 2/5/12 5:40 PM, Daniel Fischer wrote:

> On Sunday 05 February 2012, 23:14:35, wren ng thornton wrote:
>> On 2/5/12 10:21 AM, Daniel Fischer wrote:
>>> Why not use one of the packages on hackage which offer faster prime
>>> generators?
>>
>> Mostly because I hadn't looked, having had the code already laying
>> around.
>
> Yeah, that's fine, it was just
>
>>> I'll  probably trade it in for your algorithm though.
>
> that made me wonder.

Well, I would've looked around before making the change :)


>> I'm not opposed to it, however another goal is to remain
>> portable to other compilers, which means being H98/H2010 compliant.
>
> A noble goal.

By which I really mean H98/H2010 plus all the things that were already
'standard' in the days of GHC 6.6 and Hugs. MPTCs and some of the
related extensions for making type classes more flexible really need to
be added to the standard, despite the valid political reasons for
wanting to wait for the FD vs TF/AT issues to get resolved.


>> NumberSieves uses BangPatterns, but that would be easily remedied if the
>> author is willing; arithmoi looks quite nice, however it is GHC-only.
>
> The curse of striving for efficiency.
> "Portability is on the to-do list (with low priority, however)."
> It just climbed a place.

Unless I'm doing something that by its nature requires GHC extensions,
I've been doing my best to avoid them in published packages. Not that I
have anything against them, but rather that I'd like to support JHC,
UHC, and other alternatives (just as I used to support Hugs before it
died). I think there's great value in compiler competition, so I'd like
to foster it as much as I can. There're quite a number of efficiency
hacks you can do while remaining in standard Haskell (and you can always
hide the GHC-only parts with CPP).

--
Live well,
~wren

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