#10170: Speed up the computation of Bell numbers
----------------------------------------------------+-----------------------
Reporter: gerbicz | Owner:
sage-combinat
Type: enhancement | Status:
needs_review
Priority: major | Milestone: sage-5.9
Component: combinatorics | Resolution:
Keywords: bell number | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Robert Gerbicz, Travis Scrimshaw | Merged in:
Dependencies: | Stopgaps:
----------------------------------------------------+-----------------------
Changes (by {'newvalue': u'Robert Gerbicz, Travis Scrimshaw', 'oldvalue':
u'Robert Gerbicz'}):
* cc: sage-combinat (added)
* status: needs_work => needs_review
* milestone: => sage-5.9
* author: Robert Gerbicz => Robert Gerbicz, Travis Scrimshaw
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
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
-----
Apply: [attachment: trac_10170-bell_number_improvements-ts.patch]
--
Comment:
I've uploaded a new version of the patch which also adds mpmath (so #7812
can be closed as a duplicate after this patch is done). I've also come
across an error in calling with the `'mpmath'` agrument and started
#14247.
For patchbot:
Apply: trac_10170-bell_number_improvements-ts.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10170#comment:5>
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.
