Change 0 3+*&5 to 0 3+5*] for some improvement: ts'(,.3*4%~1-~])5^(i.5000x)' 13.0767 4.99247e7 ts '((0 3+*&5)^:(i.5000))1 0x' 0.126067 2.59842e7 ts '((0 3+5*])^:(i.5000))1 0x' 0.113761 2.59759e7
Linda -----Original Message----- From: programming-boun...@forums.jsoftware.com [mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Don Guinn Sent: Saturday, December 22, 2012 10:34 PM To: programm...@jsoftware.com Subject: Re: [Jprogramming] arithmetic sequence If the only concern is the efficiency of a program meaning speed and minimizing redundant executed instructions, then obviously the best programming language is assembler, which is really machine language with assist. But efficiency is not nearly that simple. Development time, portability, understandability and many other considerations make up what we like to argue on what makes up an efficient program. Well, maybe not portability. But given proper choice of the things that make up efficiency it is not difficult to "prove" any language the most efficient. It really depends on what the needs are to determine efficiency. If a program is used millions of times and it is necessary to get the answer quickly, then efficiency is obviously speed. But if it is exploration of a problem then understandability and ease of trying things is most important. I think that is where J really stands out. I can try all sorts of things with J without having to write extensive programs with lots of loops as I would have to do in most other programming languages. And with a fair understanding of the tools available in J, not restricting myself to the way things are done in other languages, I can keep the finished product pretty efficient. On Sat, Dec 22, 2012 at 6:24 PM, Linda Alvord <lindaalv...@verizon.net>wrote: > 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 > > 1415962252209634578477123031738811510589509702067886271745966044709273 > 451837 > > 9577047138732343564188389817579469051279306783676415479760629182252191 > 671480 > > 4954482928019439147946719498651658518782306700947825912453640814308711 > 524391 > 4308334045872358803907166054... > _1{hr2x nn > > 1415962252209634578477123031738811510589509702067886271745966044709273 > 451837 > > 9577047138732343564188389817579469051279306783676415479760629182252191 > 671480 > > 4954482928019439147946719498651658518782306700947825912453640814308711 > 524391 > 4308334045872358803907166054... > _1{la1 5^i.nn > > 1415962252209634578477123031738811510589509702067886271745966044709273 > 451837 > > 9577047138732343564188389817579469051279306783676415479760629182252191 > 671480 > > 4954482928019439147946719498651658518782306700947825912453640814308711 > 524391 > 4308334045872358803907166054... > _1{acx nn > > 1415962252209634578477123031738811510589509702067886271745966044709273 > 451837 > > 9577047138732343564188389817579469051279306783676415479760629182252191 > 671480 > > 4954482928019439147946719498651658518782306700947825912453640814308711 > 524391 > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
