>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
