#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:
----------------------------------------------------+-----------------------
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
>
> -----
>
> 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]
--
Comment (by tscrim):
From my 10 minutes of googling, no, it should not be. The exponential
numbers seem to be a generalization of the Bell numbers and I don't know
that this implementation can be generalized to that (and hence go into
that module). My guess is that it's probably yes, but I'll leave that to
someone with more expertise to answer.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10170#comment:8>
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.
