Oops, sorry for the premature post. ---
Thanks for the prod Greg, I understand *`* now, at least somewhat :-) I think I would prefer the below which avoids factoring the multiplication as (x+1)+(2*x), although that's a pretty cute trick. *1+3*]* has the advantage of having only two operations (one +, one *) instead of three (two +, one *). *cgv=: 13 : '(2|y)} (<.-:)`(1+3*])`:0 y'* Roger's version wins by a long shot (2.2 vs 2.1 vs 1.7). It invokes fewer verbs. The interesting thing is that it's collatzv that runs faster not the code that follows - meaning that the interpreter is smart enough to use integer arithmetic before we even get to *<.* ?!? Cheers, Mike On Tue, Aug 5, 2014 at 5:25 PM, greg heil <[email protected]> wrote: > >An interesting alternative to the verbs Roger expressed on page > http://jsoftware.com/jwiki/Essays/Collatz%20Conjecture) > > collatz=: -:`(>:@(3&*))`1: @. (1&= + 2&|) > collatzv=: 3 : '<. (2|y)} 0 1 + 0.5 3 */y' > > are > > cg=:-:`(>:++:)`1:@.(1&=+2&|) > cgv=: 13 : '(2|y)} (<.-:)`(>:++:)`:0 y' > > >They are only slightly faster (0%? maybe Dan can do the same analysis he > did earlier:) but maybe clearer as to the algorithm of Collatz' conjecture, > ie > -:`(>:++:) NB. even`odd > > >If one wants to accomodate a 1 argument one can extend cgv like so: > cgvp=: 13 : '((1&= + 2&|)y)} (<.-:)`(>:++:)`1:`:0 y' > > greg > ~krsnadas.org > > -- > > from: Michal D. <[email protected]> > to: [email protected] > date: 4 August 2014 16:08 > subject: Re: [Jprogramming] Memoizing (Project Euler problem 14) > > >Good point, it's probably there solely for the type cast, allowing later > operations to work on integers. On my machine it's ~10% faster: > > ? collatzv=: 3 : '(2|y)} 0 1 + 0.5 3 */y' > ts 'cnv 1e6' > 2.03499 5.97765e7 > ts 'cnv 1e6' > 2.04466 5.97765e7 > ts 'cnv 1e6' > 2.08829 5.97765e7 > > ? collatzv=: 3 : '<. (2|y)} 0 1 + 0.5 3 */y' > ts 'cnv 1e6' > 1.81025 6.03008e7 > ts 'cnv 1e6' > 1.83654 6.03008e7 > ts 'cnv 1e6' > 1.87314 6.03008e7? > > -- > > from: Raul Miller <[email protected]> > to: Programming forum <[email protected]> > date: 4 August 2014 15:45 > subject: Re: [Jprogramming] Memoizing (Project Euler problem 14) > > That's an interesting thought. > > >As near as I can tell, the only thing it does is convert the result from > floating point representation to integer representation. > > >Whether that's good, bad, relevant or irrelevant is ... not something I > know how to decide for the general case. > > Thanks, > Raul > > -- > > from: Michal D. <[email protected]> > to: [email protected] > date: 4 August 2014 14:13 > subject: Re: [Jprogramming] Memoizing (Project Euler problem 14) > > Is it just me or is the <. in collatzv unnecessary? > > (I'm referring to http://jsoftware.com/jwiki/Essays/Collatz%20Conjecture) > > Cheers, > > Mike > > -- > > from: Dan Bron <[email protected]> > to: [email protected] > date: 4 August 2014 05:12 > subject: Re: [Jprogramming] Memoizing (Project Euler problem 14) > > >If you're OK with spoilers, have you seen Roger's Collatz Conjecture > essay on the Wiki? > > http://jsoftware.com/jwiki/Essays/Collatz%20Conjecture > > >In particular, he develops a vector approach to the problem which greatly > outperforms the scalar solution (a common pattern in J programs). > > >On my laptop, cnv is the clear winner; here is a comparison of Roger's cn > (scalar solution) to cnv (vector solution), both verbatim and against an > argument of 1e6: > > Algo Time Space > cn 10.85 1.00 > cnv 1.00 3.58 > > >The vector approach is an order of magnitude faster (but the scalar > solution is somewhat leaner). > > >I even tried "improving" the scalar solution by memoizing it, but somehow > that hurt performance. Here, cn and cnv are as above, and cnM is cn with M. > applied to the "collatz" subfunction, all against a much smaller argument, > 1e3 (you'll see why in a moment): > > Algo Time Space > cn 5.17 1.00 > cnM 127.88 12.44 > cnv 1.00 1.26 > > >Here, the memoized version is two orders of magnitude slower than the > vector solution, and also (somehow) an order of magnitude slower than its > unmemoized counterpart. > > >Takeaway: work simultaneously on as much data as you can (or, as Hnery > would put it "Let J's primitives see as much data as possible"). > > -Dan > > -- > > Subject: [Jprogramming] Memoizing (Project Euler problem 14) > From: mvillarino <[email protected]> > Date: Mon, 4 Aug 2014 13:18:03 +0200 > To: [email protected] > > Good day: > > >I've been struggling a couple weeks long to solve Project Euler problem > 14 in a reasonable time, but the best I can get takes much much longer in > my machine. Several hours. > > Well, my current solution is this: > > > collatz =. verb define > if. 1= y do. y return. end. > if. 0= 2|y do. y=. -:y else. y=.>:3*y end. > ) > > reduceTable=. verb define > NB. y is expected to be a 2-row table > NB. with starting numbers on first row > NB. and a number in the collatz sequence on the 2nd. > if. 1= $1{y do. y return. end. > NB. nmemonics / definicions > range =. 0{y > seq =. 1{y > NB. operations > NB. compute the following number in the collatz sequence for each of > NB. the candidates. Take off the table a candidate if it appears in > the > NB. sequence of any other candidate (as they are for sure not the > NB. ones with the longest sequence). > seq =. (aux=: -.(range e. aux)+.(aux e. 1 2 4))# aux=: collatz"0 seq > range=. aux#range > NB. reconstruction > range ,: seq > ) > > reduceTable^:_ ,:~ >:i.1e6 > > NB. another attempt > > reducirLista =. verb define > memo =. 1 1 > list =. }. list=.>:i.y > while. 1<#list do. > NB. compute the collatz sequence for the next number > c =. collatz^:(<_) {. list > NB. take out of the list of candidates ... (vid supra). > list =. (list -.@:e. c)#list > NB. remember the canditate and it's collatz sequence lenght. > memo =. memo, ,: ({.,#)c > end. > ) > > > >By reading spoilers, it seems the way to go is through memoization. > Despite my attempts with M. here and there, I have found no satisfying > solution (satisfying = fast). Can someone point me to a different approach > and to a memoization with J tutorial? > > Regards, > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
