#9663: Fast computation of Stirling numbers of 2nd kind
---------------------------------+------------------------------------------
Reporter: fredrik.johansson | Owner: sage-combinat
Type: enhancement | Status: new
Priority: major | Milestone:
Component: combinatorics | Keywords:
Author: fredrik.johansson | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
---------------------------------+------------------------------------------
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}
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9663>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
