Opened 8 years ago

Closed 7 years ago

Last modified 7 years ago

#13199 closed enhancement (fixed)

Use FLINT to compute the partition function

Reported by: fredrik.johansson Owned by: sage-combinat
Priority: major Milestone: sage-5.11
Component: combinatorics Keywords:
Cc: Merged in: sage-5.11.beta1
Authors: Fredrik Johansson Reviewers: Andrew Mathas, Frédéric Chapoton, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by tscrim)

Before:

sage: %timeit number_of_partitions(1)   
625 loops, best of 3: 2.09 µs per loop
sage: %timeit number_of_partitions(10^3)
625 loops, best of 3: 197 µs per loop
sage: %timeit number_of_partitions(10^6)
25 loops, best of 3: 32.8 ms per loop
sage: %time number_of_partitions(10^9); 
CPU times: user 37.92 s, sys: 0.00 s, total: 37.92 s
Wall time: 37.93 s

After:

sage: %timeit number_of_partitions(1)
625 loops, best of 3: 1.94 µs per loop
sage: %timeit number_of_partitions(10^3)
625 loops, best of 3: 51.4 µs per loop
sage: %timeit number_of_partitions(10^6)
125 loops, best of 3: 2.66 ms per loop
sage: %time number_of_partitions(10^9); 
CPU times: user 0.47 s, sys: 0.00 s, total: 0.47 s
Wall time: 0.48 s

TODO: should add a 64-bit only test to check that evaluation works with n >= 232.


Apply:

Attachments (3)

flint_partition_function.patch (3.5 KB) - added by fredrik.johansson 8 years ago.
trac_13199_flint_partition_function_v2.patch (5.9 KB) - added by chapoton 7 years ago.
trac_13199-flint_partition-review-ts.patch (7.0 KB) - added by tscrim 7 years ago.

Download all attachments as: .zip

Change History (23)

Changed 8 years ago by fredrik.johansson

comment:1 Changed 8 years ago by chapoton

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by andrew.mathas

  • Reviewers set to Andrew Mathas

I am happy to review this, although it is not clear to me what the status of #12173 is and until this patch is merged it seems rather cumbersome to load the current patch on top of #12173 in order play around with this patch and check to see that it actually works.

Assuming that it is OK, I would like to see some more explicit tests inside the new number_of_partitions to show that it is working. I'd suggest simply reusing the ones that are in sage.combinat.partition.number_of_partitions. That is, adding the following tests to the doc-string for your number_of_partitions:

        sage: from sage.combinat.partitions import number_of_partitions
        sage: number_of_partitions(3)
        3
        sage: number_of_partitions(10)
        42
        sage: number_of_partitions(40)
        37338
        sage: number_of_partitions(100)
        190569292
        sage: number_of_partitions(100000)
        27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519

    TESTS::

        sage: n = 500 + randint(0,500)
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
        True
        sage: n = 1500 + randint(0,1500)
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
        True
        sage: n = 1000000 + randint(0,1000000)
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
        True
        sage: n = 1000000 + randint(0,1000000)
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
        True
        sage: n = 1000000 + randint(0,1000000)
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
        True
        sage: n = 1000000 + randint(0,1000000)
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
        True
        sage: n = 1000000 + randint(0,1000000)
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
        True
        sage: n = 1000000 + randint(0,1000000)
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
        True
        sage: n = 100000000 + randint(0,100000000)
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0  # long time (4s on sage.math, 2011)
        True

comment:3 Changed 7 years ago by andrew.mathas

  • Status changed from needs_review to needs_work

comment:4 Changed 7 years ago by chapoton

  • Dependencies #12173 deleted

I removed the dependency to #12173, since this has been closed in 5.10.beta3, and since a dependency on spkg makes the bot unhappy.

for the bot:

apply flint_partition_function.patch

comment:5 Changed 7 years ago by chapoton

  • Work issues set to needs rebase

this needs to be rebased on 5.10beta4

Changed 7 years ago by chapoton

comment:6 Changed 7 years ago by chapoton

for the bot:

apply trac_13199_flint_partition_function_v2.patch

I have made a rebased patch, passing all tests.

comment:7 Changed 7 years ago by chapoton

  • Status changed from needs_work to needs_review

comment:8 Changed 7 years ago by andrew.mathas

Hi. As I said on the ticket above, can you please add some more tests to the new partition function.

Last edited 7 years ago by andrew.mathas (previous) (diff)

comment:9 Changed 7 years ago by chapoton

ok, I will add the tests. But there is an annoying doctest failure concerning cached functions, see bot report.

comment:10 Changed 7 years ago by tscrim

  • Description modified (diff)
  • Reviewers changed from Andrew Mathas to Andrew Mathas, Frederic Chapoton, Travis Scrimshaw

Here's a review patch which should fix the problem, which was the Bober's implementation was cached (since it was the default). I changed this to the FLINT.

sage -t ../misc/cachefunc.pyx
    [593 tests, 78.50 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 79.6 seconds
    cpu time: 8.1 seconds
    cumulative wall time: 78.5 seconds

I also added the additional tests Andrew wanted and fixed the docstrings.

For patchbot:

Apply: trac_13199_flint_partition_function_v2.patch, trac_13199-flint_partition-review-ts.patch

comment:11 Changed 7 years ago by chapoton

Looks good to me, but the bot complains about the new module. Is there a way to avoid that, or should we just forget this warning ?

comment:12 Changed 7 years ago by tscrim

The new module can't really be avoided, plus it doesn't (significantly) add to the startup time, so I ignore these.

comment:13 Changed 7 years ago by tscrim

  • Status changed from needs_review to positive_review

I'm going to set this to positive review now since I don't think either of you (Andrew, Frederic) have any other objections. Feel free to set this to needs work if I'm wrong.

comment:14 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.10 to sage-5.11
  • Work issues needs rebase deleted

Changed 7 years ago by tscrim

comment:15 Changed 7 years ago by tscrim

  • Status changed from positive_review to needs_work

I've uploaded a new version of my review patch which removes the unneeded include_dirs from module_list.py.

comment:16 Changed 7 years ago by tscrim

  • Status changed from needs_work to needs_review

Because of the type of change, this needs another (quick) review.

comment:17 follow-up: Changed 7 years ago by chapoton

  • Status changed from needs_review to positive_review

ok, looks good to me.

comment:18 in reply to: ↑ 17 Changed 7 years ago by andrew.mathas

Replying to chapoton:

ok, looks good to me.

Thanks Travis. I'm happy too.

comment:19 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.11.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:20 Changed 7 years ago by jdemeyer

  • Reviewers changed from Andrew Mathas, Frederic Chapoton, Travis Scrimshaw to Andrew Mathas, Frédéric Chapoton, Travis Scrimshaw
Note: See TracTickets for help on using tickets.