Fast computation of Stirling numbers of 2nd kind

[fredrik-johansson]

Currently, Stirling numbers are computed by calling GAP. The patch provides fast Cython code for Stirling numbers of the second kind, and allows using GAP or Maxima as an optional algorithm.

By having less overhead, the Cython code is about 10000 times faster than GAP or Maxima for tiny inputs, and it remains much faster than GAP for larger inputs as well. Apparently Maxima uses a fast algorithm unlike GAP, but my code is still about twice as fast as Maxima for huge n due to an algorithmic optimization.

sage: %timeit stirling_number2(10,5)
625 loops, best of 3: 2.33 µs per loop
sage: %timeit stirling_number2(10,5,algorithm='gap')
25 loops, best of 3: 20 ms per loop
sage: %timeit stirling_number2(10,5,algorithm='maxima')
5 loops, best of 3: 40 ms per loop

625 loops, best of 3: 16.2 µs per loop
sage: %timeit stirling_number2(100,50,algorithm='gap')
25 loops, best of 3: 20 ms per loop
sage: %timeit stirling_number2(100,50,algorithm='maxima')
5 loops, best of 3: 40 ms per loop

sage: %timeit stirling_number2(2000,1500)
25 loops, best of 3: 35.9 ms per loop
sage: %timeit stirling_number2(2000,1500,algorithm='gap')
5 loops, best of 3: 348 ms per loop
sage: %timeit stirling_number2(2000,1500,algorithm='maxima')
5 loops, best of 3: 210 ms per loop

sage: %timeit stirling_number2(4000,3000)
5 loops, best of 3: 249 ms per loop
sage: %timeit stirling_number2(4000,3000,algorithm='gap')
5 loops, best of 3: 2.96 s per loop
sage: %timeit stirling_number2(4000,3000,algorithm='maxima')
5 loops, best of 3: 948 ms per loop

sage: %time stirling_number2(20000,15000);
CPU times: user 20.30 s, sys: 0.23 s, total: 20.53 s
Wall time: 21.82 s
sage: %time stirling_number2(20000,15000,algorithm='maxima');
CPU times: user 0.00 s, sys: 0.01 s, total: 0.01 s
Wall time: 51.90 s

Mathematica seems to be about as slow as GAP (warning: timed on a different system):

In[1]:= Timing[StirlingS2[4000,3000];]
Out[1]= {27.1809, Null}

CC: @williamstein

Component: combinatorics

Author: Fredrik Johansson, Nathann Cohen

Reviewer: Nathann Cohen, Nicolas Borie, Jeroen Demeyer

Merged: sage-4.6.1.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/9663

[williamstein]

comment:2

Please explain the massive number of changes to module_list.py of the form:

153	 	                [[blank looking line]]
 	153	                [[another blank looking line]]

[fredrik-johansson]

comment:3

Oops, my editor was set to "strip trailing whitespace when saving files".

[fredrik-johansson]

fast implementation of stirling_number2 -- updated patch

[fredrik-johansson]

comment:4

Attachment: stirling2.patch.gz

Please see the new version of the patch.

[nathanncohen]

Changed author from fredrik.johansson to Fredrik Johansson

[nathanncohen]

Reviewer: Nathann Cohen

[nathanncohen]

comment:5

Nice one !!

I learned many things while reviewing this patch :-)

Would you mind adding this small doctest in the patch I attach ? If not, you can set this ticket to "positive_review" !

Thanksssssssssssss !!!

Nathann

[nathanncohen]

Attachment: trac_9663 - additional test.patch.gz

[nathanncohen]

comment:6

Are you around ? There's basically nothing to do on this patch :-)

Nathann

[sagetrac-nborie]

Changed reviewer from Nathann Cohen to Nathann Cohen, Nicolas Borie

[sagetrac-nborie]

comment:7

The two patch applied on 4.5.3 All tests pass, no warning in docbuild... Nice documentation, powerful implantation... Good job!

I give the two patch a positive review.

For the release manager, please apply :

• stirling2.patch
• trac_9663 - additional test.patch

[jdemeyer]

Changed author from Fredrik Johansson to Fredrik Johansson, Nathann Cohen

[jdemeyer]

comment:8

I think you should add a patch with a test for "unknown algorithm".

[jdemeyer]

comment:10

Also, please do not put spaces in patch filenames.

[nathanncohen]

comment:11

Replying to @jdemeyer:

I think you should add a patch with a test for "unknown algorithm".

What do you mean ?

Nathann

[jdemeyer]

comment:12

Replying to @nathanncohen:

Replying to @jdemeyer:

I think you should add a patch with a test for "unknown algorithm".

What do you mean ?

A test which does something like

sage: n = stirling_number2(20,11,algorithm='foobar')

to check the "unknown algorithm" code.

[nathanncohen]

comment:13

Here is a new version of my patch with the requested doctest.

Nathann

[jdemeyer]

comment:14

Replying to @nathanncohen:

Here is a new version of my patch with the requested doctest.

Nathann

On line 670, TESTS:: should be TESTS: (the :: should precede a block of code, which is not the case here).

[jdemeyer]

Changed reviewer from Nathann Cohen, Nicolas Borie to Nathann Cohen, Nicolas Borie, Jeroen Demeyer

[nathanncohen]

comment:15

Done.

Nathann

[nathanncohen]

Attachment: trac_9663-additional_tests.patch.gz

[jdemeyer]

Merged: sage-4.6.1.alpha0