I was leading up to the possibility of a closed-form solution but Bo got
there while I was still winding up.
Just to finish the "better question" idea, with timings, we take a look at
how performance stats scale with increasing arguments for the rational
number inputs:
ts &> '(i. nn) next 1 0x';'nn next@]^:(i.@[) 1 0x' [ nn=. 1e2
0.000214702 64768
0.000160513 90752
ts &> '(i. nn) next 1 0x';'nn next@]^:(i.@[) 1 0x' [ nn=. 1e3
0.00413188 2.5193e6
0.00356003 2.79206e6
ts &> '(i. nn) next 1 0x';'nn next@]^:(i.@[) 1 0x' [ nn=. 1e4
0.328623 2.03783e8
0.346591 2.06426e8
ts &> '(i. nn) next 1 0x';'nn next@]^:(i.@[) 1 0x' [ nn=. 2e4
2.26308 8.06897e8
2.32999 8.12181e8
NB. Seems to be O(n^2)
Comparing performance of generating the full set of results versus just the
last one,
ts &> '(i. nn) next 1 0x';'nn next@]^:(i.@[) 1 0x' [ nn=. 2e4
2.07533 8.06897e8
2.02436 8.12181e8
ts &> 'nn next 1 0x';'nn next@]^:( [) 1 0x' [ nn=. 2e4
0.845289 298752
0.753032 299392
This indicates that much of our (time) performance hit is probably coming
from the memory allocation itself, not the CPU load.
On Thu, Dec 20, 2012 at 11:16 AM, Bo Jacoby <bojac...@yahoo.dk> wrote:
>
>
> next=:0 3+*&5
> (next^:(i.9)) 1 0 NB. brute force solution
> 1 0
> 5 3
> 25 18
> 125 93
> 625 468
> 3125 2343
> 15625
> 11718
> 78125 58593
> 390625 292968
>
> (,.3*4%~1-~])5^i.9 NB. closed form solution
> 1 0
> 5 3
> 25 18
> 125 93
> 625 468
> 3125 2343
> 15625
> 11718
> 78125 58593
> 390625 292968
>
>
>
>
>
>
>
> >________________________________
> > Fra: Roger Hui <rogerhui.can...@gmail.com>
> >Til: Programming forum <programm...@jsoftware.com>
> >Sendt: 16:07 torsdag den 20. december 2012
> >Emne: Re: [Jprogramming] arithmetic sequence
> >
> >In both versions of the code, if you give a single "exponent" n, the code
> >would produce a single answer for S(n). Internally, it would keep a
> single
> >intermediate result. If what it's doing is what you suspect (accuse! :-)
> >it of doing, you can verify it by using space=:7!:2
> > space '10 next 1 0'
> > space '20 next 1 0'
> >and look at the grow of the space consumption.
> >
> >BTW, since the function is extremely fast growing,
> >
> > 5^.2^1023
> >440.582
> > 441 next 1 0
> >1.76105e308 1.32079e308
> > 442 next 1 0
> >_ _
> >
> >If you are not interested in rational numbers, the function has only a few
> >possible answers. If you are worried about time/space, one approach may
> be
> >to recompute a vector S of length 442 of all possible results, and then
> >define next=: {&S .
> >
> >
> >
> >On Thu, Dec 20, 2012 at 5:28 AM, alessandro codenotti <cod...@live.it
> >wrote:
> >
> >>
> >> I think I badly explained myself, or maybe i completely misunderstood
> the
> >> code:
> >>
> >> > next=.5&(0 3 + *)
> >>
> >> the verb next simply applies the "multiply by five and add 3" to is
> right
> >> argument a number of times given by is left argument, right?
> >>
> >> > (i. 20) next 1 0
> >>
> >> this instruction, first applies 0 times "next" to 1 0, then applies once
> >> "next" to 1 0, then applies twice "next" to 1 0, ... , then applies 20
> >> times "next" to 1 0, right?
> >>
> >> this mean that S(0) has been calculated 20 times, S(1) has been
> calculated
> >> 19 times, S(n) has been calculated 20-n times since every time the
> function
> >> next restarts from
> >> the first term (which is 1 0), right?
> >>
> >> What i mean is that with something like the following pseudo-code S(n)
> is
> >> calculated once avoiding a huge waste of time and memory:
> >>
> >> S(1)=1 0
> >> for i=2 to 20 do
> >> S(i)=.3+5*S(i-1)
> >> end
> >>
> >> My question then was if the code:
> >>
> >> > next=.0 3+*&5
> >> > 20 next@]^:(i.@[) 1 0
> >>
> >> has the same problem or not and, in case of a positive answer, how can i
> >> translate my pseudo-code in J avoiding an explicit loop.
> >>
> >> It may be that I completely misunderstood your code and the problem that
> >> is worring me doesn't exist at all but I'm really a beginner in J...
> >>
> >> Alessandro
> >>
> >>
> >>
> >>
> >>
> >> ----------------------------------------------------------------------
> >> 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
>
--
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
