((0 3+*&5)^:30)1 0x NB. brute force solution 931322574615478515625 698491930961608886718 (,.3*4%~1-~])5^30x NB. closed form solution 931322574615478515625 698491930961608886718
Is Skip Cave saying that the closed form solution is inferior? - Bo >________________________________ > Fra: Roger Hui <rogerhui.can...@gmail.com> >Til: Programming forum <programm...@jsoftware.com> >Sendt: 19:15 lørdag den 22. december 2012 >Emne: Re: [Jprogramming] arithmetic sequence > >I answered Alessandro's question. You can verify my reasoning by using >6!:2 or 7!:2. > >I believe Alessandro may have been confused by the related Fibonacci's >sequence, where a straightforward (double) recursion *would* cause S(0) and >others to be evaluated multiple times in the evaluation of S(n). But even >for that sequence there are numerous more efficient alternatives. See >http://www.jsoftware.com/jwiki/Essays/Fibonacci%20Sequence . > > >On Sat, Dec 22, 2012 at 9:23 AM, Skip Cave <s...@caveconsulting.com> wrote: > >> So, what is the answer to Alessandro's question, namely, whether any of the >> array-based solutions avoid redundant computations? We know the looping >> approach avoids redundancy, but what about the others? >> >> I'm not enough of a J expert to answer that question, as it requires a more >> intimate >> knowledge of the internals and optimizations of the J primitives than I >> have. >> One of the interesting effects of array languages is that the interpreter >> can detect >> and optimize array operations "under the covers", without the programmer >> having >> to worry about those optimizations. The J sort operator /: is a good >> example of this >> type of phenomena. >> >> Skip >> >> On Sat, Dec 22, 2012 at 9:52 AM, Boyko Bantchev <boyk...@gmail.com> wrote: >> >> > On 21 December 2012 01:02, Skip Cave <s...@caveconsulting.com> wrote: >> > > 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. >> > >> > Comparing solutions with respect to, say, speed, may only tell us >> > which one to use (once we have them all!) if we want that speed. >> > But such a comparison does not answer Alessandro's question, namely, >> > whether array-based solutions, or a particular one of them, avoid >> > the redundant computations that he wrote of. >> > >> > Furthermore, comparing solutions with explicit loops to solutions >> > without them always tends to be unfair to the former. Huge differences >> > in speed do arise not only because J performs excelently on whole- >> > array operations, but also because it is very slow when it has to >> > execute code repeatedly. In this it is much, much slower than most >> > other languages. >> > >> > This is easily demonstrated by writing in another language a program >> > similar to the above discussed acx, such as the following program in >> > Ruby: >> > >> > n = 5000 >> > a,b = 1,0 >> > r = [[a,b]] >> > (n-1).times do >> > a,b = 5*a,5*b+3 >> > r << [a,b] >> > end >> > >> > Regarding performance, Ruby is well known for the lack of it. Still, >> > this program is faster by orders of magnitude than acx. It is also >> > faster than hr1 and hr2, although not much faster – only about twice >> > on my computer for n=5000. (The speed ratio increases with the growth >> > of n.) >> > >> > One more observation. How can one *predict* that the closed-formula >> > based solution of Bo and Linda will lose so dramatically to Henry's >> > solutions? >> > ---------------------------------------------------------------------- >> > For information about J forums see http://www.jsoftware.com/forums.htm >> > >> >> -- >> Skip Cave >> Cave Consulting LLC >> ---------------------------------------------------------------------- >> 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
