[Jprogramming] arithmetic sequence

Thu Dec 20 18:01:01 UTC 2012

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 <bojacoby at 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.canada at gmail.com>
> >Til: Programming forum <programming at 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 <code95 at 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