Among other things, the patch #13072<http://trac.sagemath.org/sage_trac/ticket/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. <http://trac.sagemath.org/sage_trac/ticket/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 insage.combinat.partition
s.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 <http://trac.sagemath.org/sage_trac/ticket/13199> implements a significantly faster algorithm which lives natively in FLINT. This patch depends on #12173 <http://trac.sagemath.org/sage_trac/ticket/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
On Friday, 21 September 2012 10:25:45 UTC+8, Andrew Mathas wrote:
> Among other things, the patch #13072<http://trac.sagemath.org/sage_trac/ticket/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. <http://trac.sagemath.org/sage_trac/ticket/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 insage.combinat.partition
> s.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. :–)
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
On Friday, September 21, 2012 5:09:19 AM UTC+1, Dima Pasechnik wrote:
> On Friday, 21 September 2012 10:25:45 UTC+8, Andrew Mathas wrote:
>> Among other things, the patch #13072<http://trac.sagemath.org/sage_trac/ticket/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.<http://trac.sagemath.org/sage_trac/ticket/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 insage.combinat.partition
>> s.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. :–)
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.
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.
On Friday, September 21, 2012 5:09:25 AM UTC-4, Jeroen Demeyer wrote:
> 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.
> 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.
On Friday, 21 September 2012 17:09:25 UTC+8, Jeroen Demeyer wrote:
> 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.
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.
