Hi all,
At 15:58 13.01.99 +0100, I wrote:
>Numerical experiments seem to indicate that the asymptotic growth of
>computation times for Stirling numbers of the first kind is much better
>than that for Stirling numbers of the second kind, though the latter can be
>given explicitly by the simple formula
>
>STIRLING2(n, k) := 1/k! SUM(COMB(k, j_)(-1)^(k - j_)j_^n, j_, 1, k)
>
>This leads to the following interesting question: Is this inevitable or
>does there exist an implementation for Stirling numbers of the second kind
>as well that is asymtotically faster than the one above?
>
Yes, there is an implementation with a far better asymptotic behaviour and
as a matter of fact it is so simple that is almost embarrassing. (Why
couldn't this guy do his job properly from the very start?!)
STIRLING2(n, k) := (ITERATE([APPEND(v_, [0]) + INSERT_ELEMENT(0, v_), n_ +
1], [v_, n_], [[1], 0], k))SUB1 VECTOR((-1)^(k - j_) j_^n, j_, 0, k)/k!
For small n and k, you may gain some fractions of a second by using the old
implementation, but in my opinion it doesn't pay off to split the
computation depending on the size of the arguments.
When I compared the computation time for STIRLING2(1000,500) for
Mathematica 3.0 and Maple V, Rel.5, I found out that Maple was exactly 6
times faster than Mathematica (5.3s vs. 31.8s) on my Pentium 166 PC. This
is a little bit surprising, because as you may remember for
STIRLING1(1000,500) it was the other way round. There is only one thing you
may rely on: DERIVE is again #1 in terms of speed with 3.3s (vs. 103.3s
with old routine!) ... Le roi est mort, vive le roi!
Cheers, Johann
_______________________________________________________________________
Johann Wiesenbauer
Institut f. Algebra und Computermathematik
der Technischen Universitaet Wien
Wiedner Hauptstrasse 8-10,
A1040-Vienna, Austria
Tel.: +43 1 58801 11813
Fax: +43 1 58801 11899
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|