One approach which should help with efficiency would be to find bounding numerators (min and max) for each denominator, and then generate the numerators between the bounds and eliminate duplicate fractions.
And, if that was too slow, I might be tempted to delve into factoring my denominators (for example, when n and 2n are both denominators my above approach would be doing duplicate work). But this gets into a lot of complexity (and we also have a bound which is arbitrary which must be handled here), and complexity has its own computational costs. -- Raul On Mon, Oct 10, 2011 at 8:59 AM, Nick Simicich <simic...@gmail.com> wrote: > I looked u faery cycles when I first cracked the forum, then tried coding > an algorithm. I coded a verb and by the time I got to my fourth or fifth > recursin it had slowed. By 10-12 it was painful and I still had a long way > to go to 12000. > > In termsof how, the code I posted made rationals of all possible numerators > and denominators, and counted those that were not reduced when examined. I > was wondering if it was possible to code that both tacitly and efficiently > for order 12000 > > > On Mon, Oct 10, 2011 at 5:04 AM, Mike Day <mike_liz....@tiscali.co.uk>wrote: > >> I thought I'd check back and see how I solved this: but there's no >> trace in my >> saved APL or J files, so I suppose I must have done a brute-force >> one-liner on >> the original, smaller problem. >> >> So I've just had another look, and today's pretty naive solution works >> in about >> 2 seconds and about 200 kB on my 2GB laptop; it's order O(n^2), so doesn't >> scale well, but is fine for the size of problem given. >> >> (I still think Problem 289, "Eulerian Cycles", is the hardest of the lot! >> see http://projecteuler.net/problem=289 >> I haven't yet solved it but I'm _not_ looking for spoilers. Perhaps it >> needs what >> Crossword Solvers call the PDM, the "Penny Drop Moment." Anyway, that's >> another topic.) >> >> Mike >> >> On 10/10/2011 12:56 AM, Nick Simicich wrote: >> > They increased the program space in Euler 73 to up to 12000 fractions. >> > Euler 73 requires that you determine how many exclusive numerators and >> > denominators there are between 1r3 and 1r2 given that the numerators and >> > denominators can be up to 12000. >> > >> > I'm trying to do this in limited space on a 32 bit netbook with not too >> much >> > extra memory, 2 gig total. >> > >> > Read about it here. http://projecteuler.net/problem=73 >> > >> > The sample space they give is up to 8. This makes it clear that I can't >> > just say ~. (>:1.8)%8, it has to be more like >> > >> > #~.(#~ (>&1r3 *.<&1r2)),%/~>:i.8 >> > >> > That works perfectly for 8 and 12, and when you try it with 10000 it runs >> > out of memory. With 12000 it gives a "limit error". I tried breaking the >> > problem into smaller tables, and it fails, out of memory when I try to >> > combine tables and nub them. >> > >> > I finally decided I could not keep separate tables, and looked at a 16 by >> 16 >> > table to get ideas. When I looked at (* (<&1r2 *.>&1r3))%/~>:i.16x I >> > didn't see anything, but when I looked at |:(* (<&1r2 *.>&1r3))%/~>:i.16x >> I >> > finally realized that any fraction that was reduced would come up >> somewhere >> > else. >> > >> > That led to this program: >> > >> > e73a =: verb define >> > count =. 0 >> > for_i.>:i. x: y do. >> > j=.<.i%3x >> > count =. count + +/i = {:"_1 ]2 x: (#~ (>&1r3 *.<&1r2)) >> > i%~j+>:i.((<.i%2x)-j) >> > end. >> > ) >> > >> > Essentially, I loop over 1<: i<: y where y is 8 or 16 for testing, and >> > 12000 for the "final answer" >> > >> > It builds a vector where the numbers in the vector are all extended >> > fractions, and the numerator is between about a third and a half of the >> > denominator. Then it trims that vector so that the survivors are >> greater >> > than 1/3 and less than 1/2. >> > >> > Finally, it looks at the denominators and counts all of the fractions >> that >> > were not reduced. >> > >> > I took a couple of half hearted attempts at making it into a one >> liner,and I >> > could not figure out how to. >> > >> > What stops me is that, well, I would have to assign the number to a >> variable >> > before using it in the expression. I could unfactor j and so forth, but, >> > well, if someone could point me to an online example, or explain, I'd >> > appreciate it. >> > >> > I've seen the item in the forum that applies the method I thought about >> > using, but they fit it into 32 bits: >> > >> > $~.;(<@#~>&(%3) *.<&0.5)@:%"0 1/~>:@i.10000 >> > >> > Now >> > >> > $~.;(<@#~>&(%3) *.<&0.5)@:%"0 1/~>:@i.12000 >> > >> > So far as I see it, well, I didn't understand how the "0 1 part worked, >> then >> > I tried this expression: >> > >> > ;"0 1/~>:@i.16 >> > >> > So if I wanted to do a lot of unneeded arithmetic, I could rewrite my >> deal >> > to use this to generate the half of the stuff I didn't care about. But >> then >> > I'd have to somehow figure out how to put the original denominator into >> the >> > boxes at the head, say. Instead of everything by everything, you only get >> > n(m max) by 1..m. But it is not at all clear whether that would have >> worked >> > for me, as I would have had to stash the original denominator or maybe >> use >> > the greatest denominator, if that worked. >> > >> > >> > - >> > Of course I can ride in the carpool lane, officer. Jesus is my constant >> > companion. >> > ---------------------------------------------------------------------- >> > For information about J forums see http://www.jsoftware.com/forums.htm >> > >> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> > > > > -- > Of course I can ride in the carpool lane, officer. Jesus is my constant > companion. > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
