number_of_partitions

[Andrew Mathas]

Among other things, the patch #13072 cleans up sage.combinat.partition. I would like some input as to should happen to the function number_of_partitions.

Arguably, if you want to compute the number of partitions of some integer in sage then you should use the Partitions class:

sage: Partitions(2000).cardinality()
4720819175619413888601432406799959512200344166

It has been suggested, however, that in some applications that the extra overhead required to create the Partitions class would be significant and, consequently, that it is better to keep a stand alone number_of_partitions function for *fast* computations of the partition function.

Currently, in the global namespace number_of_partitions points to

sage.combinat.partition.number_of_partitions

This function does some mild argument parsing, most of which is historical in that it allows you to choose between different algorithms -- which you almost certainly do not want to do because the non-default algorithms are (significantly) slower than the default algorithm. There is also an option to allow you to compute the number of k-tuples of partitions which sum to n, for which one can/should use PartitionTuples(n).cardinality() -- although, see #11476.

If there is a need to have a *fast* number_of_partitions implementation of the partition function then I think that we should deprecate all of the argument parsing and have the function in the global point directly to the default implementation, which is currently Bober's algorithm in sage.combinat.partitions.number_of_partitions. Currently, the function number_of_partitions is effectively a wrapper to this function with some extra argument parsing on top to slow it down.

Please let me know which of the following options you prefer:

1. deprecate the options to number_of_partitions and have the function in the global namespace point directly to sage.combinat.partitions.number_of_partitions so as to create a genuinely fast function.
   (This is what is currently done in #13072)
2. deprecate the options from number_of_partitions but still have the number_of_partitions function in the global namespace point to sage.combinat.partition.number_of_partitions which then calls whatever the current fastest implementation is.
3. deprecate number_of_partitions from the global namespace and require users to use the partitions classes or to import the number_of_partitions function.
   
4. leave as it (i.e. don't deprecate the options to number_of_partitions and leave the global namespace pointer to sage.combinat.partition.number_of_partitions

My preference is option #1. Note that all of the current options to number_of_partitions are still available through Partitions(*).cardinality() so no functionality is being lost

One issue in favour of option #2 is that the fastest algorithm available changes frequently (hence the choice of algorithm in the number_of_partitions function). Currently it is Bober's algorithm but trac #13199 implements a significantly faster algorithm which lives natively in FLINT. This patch depends on #12173 which updates FLINT to version 2.3. There seem to be some issues with the upgrade to FLINT 2.3 but as soon as they are resolved it should be possible to merge #13199 quickly into sage (I'm happy to review it).

Cheers,
Andrew

[Dima Pasechnik]

On Friday, 21 September 2012 10:25:45 UTC+8, Andrew Mathas wrote:

Among other things, the patch #13072 cleans up sage.combinat.partition. I would like some input as to should happen to the function number_of_partitions.

Arguably, if you want to compute the number of partitions of some integer in sage then you should use the Partitions class:

sage: Partitions(2000).cardinality()
4720819175619413888601432406799959512200344166

It has been suggested, however, that in some applications that the extra overhead required to create the Partitions class would be significant and, consequently, that it is better to keep a stand alone number_of_partitions function for *fast* computations of the partition function.

Currently, in the global namespace number_of_partitions points to

sage.combinat.partition.number_of_partitions

This function does some mild argument parsing, most of which is historical in that it allows you to choose between different algorithms -- which you almost certainly do not want to do because the non-default algorithms are (significantly) slower than the default algorithm. There is also an option to allow you to compute the number of k-tuples of partitions which sum to n, for which one can/should use PartitionTuples(n).cardinality() -- although, see #11476.

If there is a need to have a *fast* number_of_partitions implementation of the partition function then I think that we should deprecate all of the argument parsing and have the function in the global point directly to the default implementation, which is currently Bober's algorithm in sage.combinat.partitions.number_of_partitions. Currently, the function number_of_partitions is effectively a wrapper to this function with some extra argument parsing on top to slow it down.

This decreases the pedagogical value of Sage code for no good reason.
I'd rather consider making these various implementations directly visible to the user. Then
doing, say, sage.combinat.partition.number_of_partitions_Bober will call Bober's algorithm, sage.combinat.partition.number_of_partitions_FLINT will
call the algorithm in FLINT (when it will be available), etc. The user who needs a speedup will

then do the choice, if necessary. Needless to say, the default implementation should better

point to a fast implementation.
So this looks like option 5. :–)

Dima

[Volker Braun]

If there is an implementation that is *always* faster than the alternatives then it makes no sense to keep others around. The pedagogical value of being able to pick a slow algorithm is really limited (especially if the only thing that changes is the time it takes to spit out the same number), and in no relation to the cost of having useless arguments around.

So I'm +1 for number_of_partitions(n,k=None) dispatching to Partitions / PartitionTuples or whatever the fastest implementation is. Preferably as LazyImport, since there should not be a need to compute partitions during startup.

Construction of the Partitions() class doesn't really affect runtime:

sage: %time _ = [ number_of_partitions(i) for i in range(10000) ]

CPU times: user 2.45 s, sys: 0.00 s, total: 2.45 s

Wall time: 2.46 s

sage: %time _ = [ Partitions(i).cardinality() for i in range(10000) ]

CPU times: user 2.57 s, sys: 0.00 s, total: 2.57 s

Wall time: 2.59 s

[Jeroen Demeyer]

On 2012-09-21 10:52, Volker Braun wrote:
> If there is an implementation that is *always* faster than the
> alternatives then it makes no sense to keep others around.

...unless you have a simple but slow algorithm which can be used to
check the result of the complicated fast algorithm.

[Nicolas M. Thiery]

On Thu, Sep 20, 2012 at 07:25:42PM -0700, Andrew Mathas wrote:
> Please let me know which of the following options you prefer:

> 1. deprecate the options to number_of_partitions and have the function in

> the global namespace point directly to
> sage.combinat.partitions.number_of_partitions so as to create a
> genuinely fast function.
> (This is what is currently done in #13072)

> 2. deprecate the options from number_of_partitions but still have the

> number_of_partitions function in the global namespace point to
> sage.combinat.partition.number_of_partitions which then calls whatever
> the current fastest implementation is.
>

> ...

>
> My preference is option #1. Note that all of the current options to
> number_of_partitions are still available through
> Partitions(*).cardinality() so no functionality is being lost
>
> One issue in favour of option #2 is that the fastest algorithm available
> changes frequently (hence the choice of algorithm in the
> number_of_partitions function). Currently it is Bober's algorithm but trac
> #13199 implements a significantly faster algorithm which lives natively in
> FLINT. This patch depends on #12173 which updates FLINT to version 2.3.
> There seem to be some issues with the upgrade to FLINT 2.3 but as soon as
> they are resolved it should be possible to merge #13199 quickly into sage
> (I'm happy to review it).

In the long run I definitely vote for option 1, with
sage.combinat.partitions.number_of_partitions pointing at any time to
whatever implementation is fastest. I am also all fine with option 1
in the short run if the user gets a useful error message when passing
extra options; something like:

sage: number_of_partitions(4, <some options>)
Error ... options ... not supported anymore ...
Please use Partitions(n, <options>)

Otherwise I vote for option 2 as a first round, and option 1 later.

But that's just my 2 cents!

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Andrew Mathas]

On Friday, 21 September 2012 14:09:19 UTC+10, Dima Pasechnik wrote:

This decreases the pedagogical value of Sage code for no good reason.

Hi Dima,

If you reread my post you will see that ALL of the current functionality of number_of_partitions is still supported by Partitions(*).cardinality(), including the choice of multiple algorithms, so I don't think there is any decrease in value, pedagogical or otherwise.

Andrew

[kcrisman]

Hmm, good point. 

[Travis Scrimshaw]

Hey

 

In the long run I definitely vote for option 1, with
sage.combinat.partitions.number_of_partitions pointing at any time to
whatever implementation is fastest. I am also all fine with option 1
in the short run if the user gets a useful error message when passing
extra options; something like:

        sage: number_of_partitions(4, <some options>)
        Error ... options ... not supported anymore ...
        Please use Partitions(n, <options>)

Otherwise I vote for option 2 as a first round, and option 1 later.

But that's just my 2 cents!

If almost everyone will call the fastest algorithm, it makes sense not to do any subsequent argument parsing to decide which algorithm. Also having one main entry point means it is easier to maintain the code should a faster algorithm become available. Therefore option 1 is my first, then follow as Nicolas suggested. I guess that now makes it 4 cents.

Best,

Travis

[Dima Pasechnik]

indeed. In particular if this fast algorithm is a 

C(++)/assembler implementation done by Ueberhackers in an upstream library... 

Further, an overhead of extra default arguments should be tolerated, IMHO.