Nice!
I did note that you didn't need to have the n_ since it is not used. So
it can be simplified a little to:
STIRLING2(n, k) := ITERATE(APPEND(v_, [0]) + INSERT_ELEMENT(0, v_),
v_, [1], k) VECTOR((-1)^(k - j_) j_^n, j_, 0, k)/k!
Ralph
> X-Sender: [log in to unmask]
> Date: Sun, 17 Jan 1999 21:02:41 +0100
> Mime-Version: 1.0
> Subject: The ultimate STIRLING2
> From: Johann Wiesenbauer <[log in to unmask]>
> To: "[log in to unmask]" <[log in to unmask]>
> X-List: [log in to unmask]
> X-Unsub: To leave, send text 'leave derive-news' to [log in to unmask]
> X-List-Unsubscribe: <mailto:[log in to unmask]>
>
> 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
>
>
>
>
>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|