datatype L:0 (g 5000x); h 5000 +--------+--------+ |floating|extended| +--------+--------+
R.E. Boss > -----Oorspronkelijk bericht----- > Van: programming-boun...@forums.jsoftware.com > [mailto:programming-boun...@forums.jsoftware.com] Namens Linda Alvord > Verzonden: zondag 23 december 2012 2:25 > Aan: programm...@jsoftware.com > Onderwerp: Re: [Jprogramming] arithmetic sequence > > I don't usually worry much about time and space but here is interesting > thing I found: > > ts=: 6!:2,7!:2 > ts'(,.3*4%~1-~])5^(i.5000x)' > 12.7805 4.99247e7 > ts '((0 3+*&5)^:(i.5000))1 0x' > 0.125234 2.59924e7 > f=: 13 :'(,.3*4%~1-~])5^i.y' > f > [: (,. (3 * 4 %~ 1 -~ ])) 5 ^ i. > ts 'f 5000x' > 12.8862 4.95213e7 > g=: 13 :'((0 3+*&5)^:(i.y))1 0' > g > 3 : '((0 3+*&5)^:(i.y))1 0' > ts 'g 5000x' > 0.0859978 1.48096e6 > h > 3 : '((0 3+*&5)^:(i.y))1 0x' > 3 : '((0 3+*&5)^:(i.y))1 0x' > 3 : '((0 3+*&5)^:(i.y))1 0x' > ts 'h 5000' > 0.193622 2.59932e7 > > I found why g was so fast. Look at the first few of the 5000 lines in A. > > > $":(,.3*4%~1-~])5^(i.5000x) > 5000 6991 > $":((0 3+*&5)^:(i.5000))1 0x > 5000 6991 > > $":f 5000x > 5000 6991 > $":g 5000x > 5000 23 > $":h 5000x > 5000 6991 > ]A=:g 5000x > ... > _ _ > _ _ > _ _ > _ _ > _ _ > _ _ > _ _ > _ _ > > Linda > > -----Original Message----- > From: programming-boun...@forums.jsoftware.com > [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Skip Cave > Sent: Thursday, December 20, 2012 6:03 PM > To: programm...@jsoftware.com > Subject: Re: [Jprogramming] arithmetic sequence > > Alessandro is concerned about the efficiency of the approaches that were > proposed to his problem. I make the assumption here that he wants the verb > to calculate all the values up to a specific integer in the formula. > > Alessandro is worried that the approaches that are proposed may recalculate > the values S(0), S(1), S(2), over and over again, wasting processing time. > This is a typical concern of someone coming from a scalar language > background, when first confronted with matrix and recursive operations in J. > Also he worries that that these proposals may take up a considerable amount > of space during execution. He is asking if any of the solutions that were > proposed to his problem avoid this replication of the calculations. > > The best way to answer his question is to program the problem using his > explicit looping approach, and compare that approach with the approaches > proposed by the various members of the forum. > > Let's develop an explicit looping approach to solve the problem. Here's > Alessandro's problem coded in a typical explicit scalar looping style: > > ac =: 3 : 0 > n =. y > a =. 1 0 > z =. a > next=.0 3+*&5 > while. n > 0 do. > a =. next a > z =. z,a > n =. n-1 > end. > (y, 2) $ z > ) > > Here are some of the other solutions proposed on the forum: > NB. Henry Rich's first proposal > next=:0 3+*&5 > hr1 =: 3 : 'y next@]^:(i.@[) 1 0' > > NB. Henry Rich's second proposal > next1=: 5&(0 3 + *) > hr2 =: 3 : '(i. y) next1 1 0' > > NB. Linda Alford's proposal > la1=: 13 :'y ,.(3*(y-1)%4)' > ans =. la1 5^i. nn > > NB. They all get the same answer > nn =. 20 > (hr1 nn) -: hr2 nn > 1 > (hr1 nn) -: la1 5^i. nn > 1 > (hr1 nn) -: ac nn > 1 > > NB. So lets see how much time and space they use > > nn =. 20 > ts&>'hr1 nn';'hr2 nn';'la1 5^i.nn';'ac nn' > 0.000143973 8128 > 5.27389e_5 7680 > 8.85397e_6 1984 > 0.000201332 3008 > > Alessandro's explicit loop approach uses about half the space of the worst > case, but takes about three times the processing time. However, Linda's > scheme is by far the best, as it uses less space and time than any other > approach. > > Let's make the problem bigger > > nn =. 400 > ts&>'hr1 nn';'hr2 nn';'la1 5^i.nn';'ac nn' > 0.00121992 67456 > 0.00101282 67008 > 6.58273e_5 19264 > 0.00347769 10688 > > Now the explicit looping uses about one-seventh the space as the worst case, > but still takes three times as long to execute. Linda's approach is still > much better. > > Let's go even bigger: > > nn =. 5000 > ts&>'hr1 nn';'hr2 nn';'la1 5^i.nn';'ac nn' > 0.0403787 938880 > 0.0389937 938432 > 0.00243484 295744 > 0.0200658 256384 > > Of course we know that, even though the calculations are being done, the > results are all the same after 442 iterations due to the 64-bit precision > limit. In any case, Linda's approach still wins in both categories > > It's easy to convert all the verbs into extended precision by simply putting > an 'x' after the initial values in each verb. So we can see what happens > when we calculate some REALLY big numbers. > > nn =. 5000x > (hr1x nn) -: hr2x nn > 1 > (hr1x nn) -: acx nn > 1 > (hr1x nn) -: la1 5^i.nn > 1 > > ts&>'hr1x nn';'hr2x nn';'la1 5^i.nn';'acx nn' > 0.0699063 2.64288e7 > 0.0628555 2.64615e7 > 7.75595 4.99236e7 > 2.60534 107328 > > To make sure: > _1{hr1x nn > 1415962252209634578477123031738811510589509702067886271745966044709273451837 > 9577047138732343564188389817579469051279306783676415479760629182252191671480 > 4954482928019439147946719498651658518782306700947825912453640814308711524391 > 4308334045872358803907166054... > _1{hr2x nn > 1415962252209634578477123031738811510589509702067886271745966044709273451837 > 9577047138732343564188389817579469051279306783676415479760629182252191671480 > 4954482928019439147946719498651658518782306700947825912453640814308711524391 > 4308334045872358803907166054... > _1{la1 5^i.nn > 1415962252209634578477123031738811510589509702067886271745966044709273451837 > 9577047138732343564188389817579469051279306783676415479760629182252191671480 > 4954482928019439147946719498651658518782306700947825912453640814308711524391 > 4308334045872358803907166054... > _1{acx nn > 1415962252209634578477123031738811510589509702067886271745966044709273451837 > 9577047138732343564188389817579469051279306783676415479760629182252191671480 > 4954482928019439147946719498651658518782306700947825912453640814308711524391 > 4308334045872358803907166054... > > Well, now the explicit iterative solution wins the space battle by far. > Linda's approach looses the time battle by several orders of magnitude, with > Allessandro's verb not too far behind. . Both Henry's verbs are the winners > in the time battle using extended precision. > > This shows why trying to optimize for time and space in a program can be > quite a challenge, and is often more trouble than it is worth. A > programmer's time is almost always much more valuable than a computer's time > or memory space, so getting quickly to the answer usually costs much less > than spending programming time to save computer processing time or memory. > -- > Skip Cave > ---------------------------------------------------------------------- > 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
