execution time is reduced about 20% if you use m=. e <....@%: y if. isinteger ( e ^. m )
instead of m=. e <....@%: y if. y=m^x: e do. m,e no biggie, but I guess every little bit helps ----- Original Message Follows ----- From: Roger Hui <[email protected]> To: Programming forum <[email protected]> Subject: Re: [Jprogramming] question about Roger Hui - perfect power code Date: Tue, 09 Jun 2009 23:44:42 -0700 >> Is it cheaper time-wise to just do all the exponents from >> 2 to >. 2 ^. y or would it be faster to prune the for_e >> list so it only contains primes. > >If only prime powers are required you can use >i.&.(_1&p:) >.2^.y instead of 2+i.>.2^.y . >In that case you should probably rename the >function to ppp (perfect prime power). > > > >----- Original Message ----- >From: [email protected] >Date: Tuesday, June 9, 2009 16:40 >Subject: [Jprogramming] question about Roger Hui - perfect >power code To: Programming forum ><[email protected]> > >> In the following code: >> >> pp=: 3 : 0 >> for_e. 2+i.>.2^.y do. >> m=. e <....@%: y >> if. y=m^x: e do. m,e >> return. end. >> end. >> '' >> ) >> >> I understand that: >> >> if. y=m^x: e do. m,e return. end. >> >> will exit when the input y equals the m^x: and display m >> ,e >> 1. Where does the "x" come from. I do not supply it >> as a >> left-hand-side argument. >> 2. what is the significance of "x:" >> >> Thanks for the explanation. >> >> A comment: >> >> In reading about the "perfect power" there was a >> statement I found that (I think) ... >> said that the only exponents I should test were those >> that were prime. >> >> Is it cheaper time-wise to just do all the exponents from >> 2 to >. 2 ^. y or would >> it be faster to prune the for_e list so it only contains >> primes. >> >> ----- Original Message Follows ----- >> From: Roger Hui <[email protected]> >> To: Programming forum <[email protected]> >> Subject: Re: [Jprogramming] perfect power??? >> Date: Mon, 08 Jun 2009 16:11:41 -0700 >> >> >Somewhere in the bowels of q: it calls 1&p: >> >before launching into the much more expensive >> >factoring routine. >> > >> >It seems to me there should be a straightforward >> >determination of whether a number y is a perfect power: >> >just try all possible exponents from 2 to 2 >....@^. y . >> >For example, for 2^607x the exponents are from 2 to 607, >> >which is not many exponents to try. Thus: >> > >> >pp=: 3 : 0 >> > for_e. 2+i.>.2^.y do. >> > m=. e <....@%: y >> > if. y=m^x: e do. m,e return. end. >> > end. >> > '' >> >) >> > >> > pp 81 >> >9 2 >> > pp 128 >> >2 7 >> > pp 125 >> >5 3 >> > pp 2^100x >> >1125899906842624 2 >> > pp <:2^607x >> > >> > 6!:2 'pp <: 2^607x' >> >0.159832 >> > >> >pptest=: *...@#@pp >> > >> > >> > >> > >> >----- Original Message ----- >> >From: Raul Miller <[email protected]> >> >Date: Monday, June 8, 2009 15:32 >> >Subject: Re: [Jprogramming] perfect power??? >> >To: Programming forum <[email protected]> >> > >> >> On Mon, Jun 8, 2009 at 6:13 PM, >> >> <[email protected]> wrote: >> >> > From what I am read in this article, determing if a >> >> > number is a "Perfect Power" should be >> >> > a lot faster. Either that or I am totally >> mis-reading >> >> > the article. >> >> >> >> Determining if a number is a perfect power is >> >> certainly faster than some algorithm for determining >> >> if a number is prime. >> >> >> >> But do you have any reason to believe J uses that >> >> algorithm, in its implementation of q? >> >> >> >> That said, 1 p: will determine whether or not a number >> >> is prime, and might be faster than 1 = # q: in some >> >> cases. >----------------------------------------------------------- >----------- For information about J forums see >http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
