scan=. ((~/)\.)(&.|.)
   -scan p:i.5
2 _1 _6 _13 _24
   -/\ p:i.5
2 _1 4 _3 8

-- 
Raul

On Tue, Jan 10, 2023 at 3:18 PM Jose Mario Quintana
<jose.mario.quint...@gmail.com> wrote:
>
> Indeed,
>
>    scan=. ((~/)\.)(&.|.)
>
>    %&:{./"_1 +/ .*  /\ (1 0,:~,&1)"0 ]10$1
> 1 2 1.5 1.66667 1.6 1.625 1.61538 1.61905 1.61765 1.61818
>    %&:{./"_1 +/ .*scan (1 0,:~,&1)"0 ]10$1
> 1 2 1.5 1.66667 1.6 1.625 1.61538 1.61905 1.61765 1.61818
>
>    stp=. ] (([ ((<;._1 '|Sentence|Space|Time|Space * Time') , (, */&.:>@:(1
> 2&{))@:(] ; 7!:2@:] ; 6!:2)&>) (10{a.) -.&a:@:(<;._2@,~) ]) [ (0 0 $
> 13!:8^:((0 e. ])`(12"_)))@:(2 -:/\ ])@:(".&.>)@:((10{a.) -.&a:@:(<;._2@,~)
> ]) ::(0 0&$@(1!:2&2)@:('Mismatch!'"_))) ".@:('0( : 0)'"_)
>
>    stp 11
>     %&:{./"_1 +/ .*/\   (1 0,:~,&1)"0 ]1000$1
>     %&:{./"_1 +/ .*scan (1 0,:~,&1)"0 ]1000$1
> )
> ┌─────────────────────────────────────────────┬──────┬───────────┬────────────┐
> │Sentence                                     │Space │Time       │Space *
> Time│
> ├─────────────────────────────────────────────┼──────┼───────────┼────────────┤
> │    %&:{./"_1 +/ .*/\   (1 0,:~,&1)"0 ]1000$1│79552 │0.059218   │4710.91
>   │
> ├─────────────────────────────────────────────┼──────┼───────────┼────────────┤
> │    %&:{./"_1 +/ .*scan (1 0,:~,&1)"0 ]1000$1│206656│0.000644564│133.203
>   │
> └─────────────────────────────────────────────┴──────┴───────────┴────────────┘
>
>    2,1}.,1 1&,"0]2*1+i.3
> 2 1 2 1 1 4 1 1 6
>
>    %&:{./"_1 +/ .*/\   (1 0,:~,&1)"0 ]2,1}.,1 1&,"0]2*1+i.3
> 2 3 2.66667 2.75 2.71429 2.71875 2.71795 2.71831 2.71828
>    %&:{./"_1 +/ .*scan (1 0,:~,&1)"0 ]2,1}.,1 1&,"0]2*1+i.3
> 2 3 2.66667 2.75 2.71429 2.71875 2.71795 2.71831 2.71828
>
>
>    stp 11
>    %&:{./"_1 +/ .*/\   (1 0,:~,&1)"0 ]2,1}.,1 1&,"0]2*1+i.30
>    %&:{./"_1 +/ .*scan (1 0,:~,&1)"0 ]2,1}.,1 1&,"0]2*1+i.30
> )
> ┌────────────────────────────────────────────────────────────┬─────┬───────────┬────────────┐
> │Sentence                                                    │Space│Time
>     │Space * Time│
> ├────────────────────────────────────────────────────────────┼─────┼───────────┼────────────┤
> │   %&:{./"_1 +/ .*/\   (1 0,:~,&1)"0 ]2,1}.,1
> 1&,"0]2*1+i.30│19840│0.00190225 │37.7407     │
> ├────────────────────────────────────────────────────────────┼─────┼───────────┼────────────┤
> │   %&:{./"_1 +/ .*scan (1 0,:~,&1)"0 ]2,1}.,1
> 1&,"0]2*1+i.30│30336│0.000149318│4.52972     │
> └────────────────────────────────────────────────────────────┴─────┴───────────┴────────────┘
>
> NB. 300 instead of 30 is too many...
>
> On Mon, Jan 9, 2023 at 11:21 AM Henry Rich <henryhr...@gmail.com> wrote:
>
> > f/\ is quadratic but f/\. shouldn't be.
> >
> > Henry Rich
> >
> > On 1/9/2023 11:20 AM, Marshall Lochbaum wrote:
> > > It's not just Fibonacci numbers. This is equivalent to a general method
> > > for computing continued fractions convergents in linear time, using
> > > matrix multiplication. There's a nice explanation of why it works in
> > > here:
> > >
> > > https://perl.plover.com/classes/cftalk/INFO/gosper.txt
> > >
> > > And a J version, with phi's continued fraction 1 1 1... :
> > >
> > >     %&:{./"_1 +/ .*/\ (1 0,:~,&1)"0 ]10$1
> > > 1 2 1.5 1.66667 1.6 1.625 1.61538 1.61905 1.61765 1.61818
> > >
> > > Here's the continued fraction sequence for e:
> > >
> > >     2,1}.,1 1&,"0]2*1+i.3
> > > 2 1 2 1 1 4 1 1 6
> > >
> > >     %&:{./"_1 +/ .*/\ (1 0,:~,&1)"0 ]2,1}.,1 1&,"0]2*1+i.3
> > > 2 3 2.66667 2.75 2.71429 2.71875 2.71795 2.71831 2.71828
> > >
> > > My timings show J taking quadratic time for the scan, so this
> > > formulation is pretty slow but shows the principle.
> > >
> > > Marshall
> > >
> > > On Sun, Jan 08, 2023 at 07:05:46PM -0800, Elijah Stone wrote:
> > >> Can we generate phi, the golden ratio, in parallel?
> > >>
> > >> Of course we can!  Follows is an exposition of a classic method for
> > doing
> > >> it, which may be of interest; I have not seen it satisfactorily
> > described
> > >> elsewhere.
> > >>
> > >> The classic method for generating phi in j uses a continued fraction:
> > >>
> > >>     (+%)/10#1
> > >> 1.61818
> > >>
> > >> (It can be equivalently spelt (1+%)^:n]1.)
> > >>
> > >> Using rational numbers clarifies slightly:
> > >>
> > >>     (+%)/10#1x
> > >> 89r55
> > >>
> > >> Unsurprisingly, it's generating ratios of successive fibonacci
> > numbers.  Can
> > >> it be parallelised?  The operation used for reduction is not
> > associative:
> > >>
> > >>     ((1 +% 1) +% 1) -: (1 +% (1 +% 1))
> > >> 0
> > >>
> > >> So it's not obvious how we would parallelise it.  Taking a step back, it
> > >> performs repeated division, where we don't know the divisor a priori,
> > >> instead generating it recursively, so attacking it thus seems hopeless.
> > >>
> > >> Here's another method, based more directly on fibonacci numbers, which
> > is
> > >> more promising:
> > >>
> > >>     (u=. {:,+/)^:9]1 1
> > >> 55 89
> > >>
> > >> Here we generate fibonacci numbers via a recurrence relation, using two
> > >> successive terms to generate the next.
> > >>
> > >> At first glance, this seems just as hopelessly sequential as the first
> > >> solution, but the use of ^: is a tell.  u^:n is the same as u@:u@:u@:
> > ... n
> > >> times.  And _@:_ is associative!  So if we can somehow express the
> > operation
> > >> of u as 'data', and ditto the composition of any number of us, then we
> > can
> > >> create a big array of n copies of u, and then reduce @: over it (in
> > >> parallel), and finally apply the reduced u^:n to our y.
> > >>
> > >> Of course, this all depends on finding an efficient way of representing
> > >> compositions of u.  If we can't do that, then we'll waste a bunch of
> > >> parallel work constructing compositions, only to _still_ need linear
> > >> sequential work at the end, once we apply our composed u.
> > >>
> > >> Let's look at the operation of u _symbolically_:
> > >>
> > >> u a,b is b,a+b
> > >> u u a,b is (a+b),(a+2*b)
> > >> u u u a,b is (a+2*b),((2*a)+(3*b))
> > >>
> > >> In other words, u gives two results, each of which is a linear
> > combination
> > >> of its two inputs.  And we have a convenient way of representing such
> > >> functions: matrices!  Hence obtains an alternate implementation of u,
> > as a
> > >> matrix product:
> > >>
> > >>     u2=. (0 1,:1 1)&(+/ . *)
> > >>     u2^:9]1 1 NB.same result as u
> > >> 55 89
> > >>
> > >> Hence, we can generate an efficient representation for u^:n in parallel,
> > >> with only logarithmic span, for matrix multiplication is isomorphic to
> > >> composition (and it is associative).  The resultant function always
> > takes
> > >> the form of a 2x2 matrix, so we have only a constant amount of
> > additional
> > >> work to do at the end.
> > >>
> > >>     (+/ .*/9#,:0 1,:1 1) +/ .* 1 1
> > >> 55 89
> > >>
> > >> The astute may notice that this is wasted parallelism.  We use a
> > parallel
> > >> reduction to find +/ .*/n#,:0 1,:1 1 in logarithmic time, but this is in
> > >> fact just the nth power of matrix 0 1,:1 1, which can be calculated
> > >> _sequentially_ in logarithmic time, by repeated squaring.  But this
> > method
> > >> has a key advantage over that: if we want the entire fibonacci
> > sequence, we
> > >> can generate it, still with logarithmic span and linear work, by simply
> > >> replacing our reduction with a scan:
> > >>
> > >>     (+/ .*/\9#,:0 1,:1 1) +/ .* 1 1
> > >>   1  2
> > >>   2  3
> > >>   3  5
> > >>   5  8
> > >>   8 13
> > >> 13 21
> > >> 21 34
> > >> 34 55
> > >> ----------------------------------------------------------------------
> > >> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

Reply via email to