Better performance gives the recursive formula from http://en.wikipedia.org/wiki/Bell_number
Bn=: (, [:+/ (i.! <:)@# *])^:(]`(x:@1:)) 5 ts 'bellN0X i.120' 0.47826126 3212288 5 ts'Bn<: 120' 0.30759069 140800 ([EMAIL PROTECTED] -:Bn@<:) 120 1 R.E. Boss > -----Oorspronkelijk bericht----- > Van: [EMAIL PROTECTED] [mailto:programming- > [EMAIL PROTECTED] Namens R.E. Boss > Verzonden: maandag 17 december 2007 20:03 > Aan: 'Programming forum' > Onderwerp: RE: [Jprogramming] Bell numbers > > OK, I made a mistake by assuming that extended input would force extended > output. > > What is the performance of the Haskell approach? > > Since J is on arrays, performance should be on arrays .... > > et=: 6!:2 NB. execution time > > 5 et 'bellN1"0 i.120' > 3.156903 > > 5 et 'bellN0X i.120' > 0.40741206 > > (bellN0X-:bellN1"0) i.120 > 1 > > > R.E. Boss > > > > -----Oorspronkelijk bericht----- > > Van: [EMAIL PROTECTED] [mailto:programming- > > [EMAIL PROTECTED] Namens Arie Groeneveld > > Verzonden: maandag 17 december 2007 12:09 > > Aan: Programming forum > > Onderwerp: Re: [Jprogramming] Bell numbers > > > > > > It has of course no effect on a (first) call: > > it's an iteration, not a recursion. :-\ > > For successive calls with the same argument > > I presume the result is still in memory? > > > > -------....----------------- > > In trying to understand what's going on: > > > > bellN0 120 > > 5.1263e145 > > bellN0 120x > > 5.1263e145 > > > > ??? > > > > bellN17=: [:{.([:+/\{:,])^:(]`1:) > > timer 'bellN17 120' > > 0.000223 > > timer 'bellN0 120' > > 0.000244 > > > > > > bellN0X=:[:{."1 (([:+/\{:,])^:(]`(x:@1:))) > > timer 'bellN0X 120' > > 0.582729 > > > > That's why bellN0 has a major speed advantage?? > > So I think the imperative bellN1 is still the winner > > for big values (ext. prec.). > > > > timer 'bellN1 120' > > 0.126827 > > > > > > Hints: > > - think arraywise > > - avoid loops > > - avoid low ranks > > > > But, here's what I still have to work on :-( > > > > > > Thanks > > > > FWIW: > > I was inspired by an amazing approach in Haskell > > > > nextRow :: [Integer] -> [Integer] > > nextRow r = next > > where next = last r : zipWith (+) r next > > > > ...and I've not enough experience to emulate > > (translate) that in J. > > > > > > > > > > > > R.E. Boss schreef: > > > Notice the difference between bellN and (the improved version) bellN0: > > > > > > bellN=: [:{.([:+/\{:,x:&])^:(]`1:) M. > > > bellN0=:[:{."1 (([:+/\{:,])^:(]`1:)) > > > > > > (bellN0 -: bellN"0)i.120x > > > 1 > > > > > > 5 ts'bellN"0 i.120x' > > > 0.23613405 22528 > > > > > > 5 ts'bellN0 i.120x' > > > 0.00025226441 244864 > > > > > > which is 86 times as efficient. > > > > > > > > > BTW, what does M. do? > > > > > > > > > R.E. Boss > > > > > > > > > > > >> -----Oorspronkelijk bericht----- > > >> Van: [EMAIL PROTECTED] [mailto:programming- > > >> [EMAIL PROTECTED] Namens Arie Groeneveld > > >> Verzonden: zaterdag 15 december 2007 17:01 > > >> Aan: Programming forum > > >> Onderwerp: [Jprogramming] Bell numbers > > >> > > >> J4F > > >> > > >> Generating Bell numbers based on using > > >> the pierce Triangle. > > >> > > >> bell numbers: 1,1,2,5,15,52,203,877,4140,21147,115975 > > >> > > >> I can come up with these two verbs > > >> > > >> NB. for n>21 I need to add ext. precision -- x:&] > > >> bellN=: [:{.([:+/\{:,x:&])^:(]`1:) M. > > >> > > >> NB. next pierce triangle row > > >> vp3hr=: 3 : 0 > > >> v=.{:y > > >> for_i. i.#y do. > > >> v=. v,(i{v)+i{y > > >> end. > > >> ) > > >> > > >> bellN1=: [:{.vp3hr^:(]`(x:@1:)) > > >> > > >> > > >> bellN"0 i.10 > > >> 1 1 2 5 15 52 203 877 4140 21147 > > >> > > >> bellN1"0 i.10 > > >> 1 1 2 5 15 52 203 877 4140 21147 > > >> > > >> (bellN -: bellN1) 100 > > >> 1 > > >> > > >> timer 'bellN1 100' > > >> 0.086825 > > >> > > >> timer 'bellN 100' NB. first call > > >> 0.305226 > > >> > > >> > > >> > > >> Other possibilities? > > >> > > >> > > >> Regards > > >> > > >> =@@i > > >> > > >> > > >> > > >> --------------------------------------------------------------------- > - > > >> For information about J forums see > http://www.jsoftware.com/forums.htm > > >> > > > > > > ---------------------------------------------------------------------- > > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > > > > > > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
