id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
9663 Fast computation of Stirling numbers of 2nd kind fredrik.johansson sage-combinat "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}
}}}" enhancement closed major sage-4.6.1 combinatorics fixed was sage-4.6.1.alpha0 Fredrik Johansson, Nathann Cohen Nathann Cohen, Nicolas Borie, Jeroen Demeyer N/A