#10170: Speed up the computation of Bell numbers
----------------------------------------------------+-----------------------
Reporter: gerbicz | Owner:
sage-combinat
Type: enhancement | Status:
positive_review
Priority: major | Milestone: sage-5.10
Component: combinatorics | Resolution:
Keywords: bell number | Work issues:
Report Upstream: N/A | Reviewers: Ben
Salisbury
Authors: Robert Gerbicz, Travis Scrimshaw | Merged in:
Dependencies: | Stopgaps:
----------------------------------------------------+-----------------------
Description changed by jdemeyer:
Old description:
> For large n values use the formula: `bell(n) = exp(-1)*sum(k=0, infinity,
> k**n/k!)`
>
> Currently my code beats all known implementations, also sage's code which
> wraps GAP's Bell is slow and using lots of memory, and unable to compute
> bell_number(n) if n is large.
>
> Some timings on Amd 2.1 GHz:
>
> n time (Wall time)
>
> 300 0.01 sec.
>
> 1000 0.03 sec.
>
> 3000 0.18 sec.
>
> 10000 2.88 sec.
>
> 30000 46.79 sec.
>
> 100000 819.37 sec.
>
> Compare these with another programs:
> http://fredrik-j.blogspot.com/2009/03/computing-generalized-bell-
> numbers.html
>
> Also exposes mpmath's `bell()` as an alternative algorithm.
>
> -----
>
> Apply: [attachment: trac_10170-bell_number_improvements-ts.patch]
New description:
For large n values use the formula: `bell(n) = exp(-1)*sum(k=0, infinity,
k**n/k!)`
Currently my code beats all known implementations, also sage's code which
wraps GAP's Bell is slow and using lots of memory, and unable to compute
bell_number(n) if n is large.
Some timings on Amd 2.1 GHz:
n time (Wall time)
300 0.01 sec.
1000 0.03 sec.
3000 0.18 sec.
10000 2.88 sec.
30000 46.79 sec.
100000 819.37 sec.
Compare these with another programs:
http://fredrik-j.blogspot.com/2009/03/computing-generalized-bell-
numbers.html
Also exposes mpmath's `bell()` as an alternative algorithm.
-----
Apply: [attachment:trac_10170-bell_number_improvements-ts.patch]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10170#comment:15>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
