Let explain why I want a "perfect power" routine. The AKS primality test use it as the first step in determing if a number is prime or not.
If the AKS primality test finds in this first step that the value passed in is a "perfect power" it bails because the number can not be a prime. If the cost of doing the "perfect power" test is reasonably the same as doing # q: then the first step of finding "perfect power" of the input variable too slow. Supposedly the "perfect power" test can be done in linear time. See http://cr.yp.to/papers/powers-ams.pdf I guess linear time means the same thing as (log2 n) exp( O(square-root(log log n log log logn)) for n > 16 as it says in the above .pdf file. ----- Original Message Follows ----- From: Joey K Tuttle <[email protected]> To: Programming forum <[email protected]> Subject: Re: [Jprogramming] perfect power??? Date: Mon, 8 Jun 2009 10:56:04 -0700 >Only a silly 1% longer - 99% of the time is taken by q: >determining that <:2x^607 is a prime... (I'm impressed >that it does :) > >And only one segmentation fault in poking at it... :( > > >At 09:38 -0800 2009/06/08, [email protected] >>wrote: Thanks for the help. >> >>I haven't really timed it, but it seems that doing: >> >># q: <: 2x ^ 607 >> >>is just about as fast as doing >> >>pp0 <: 2x ^ 607 >> >> >>----- Original Message Follows ----- >>From: Raul Miller <[email protected]> >>To: Programming forum <[email protected]> >>Subject: Re: [Jprogramming] perfect power??? >>Date: Mon, 8 Jun 2009 12:09:15 -0400 >> >>>On Mon, Jun 8, 2009 at 10:39 AM, >>>> <[email protected]> wrote: I would not >>>>think it was simpler, but if the verb returned: >>>> 1 - "IS" perfect power >>>> 0 - "IS NOT" perfect power >>>> >>>> that would be fine. >>> >>>Both Mike Day's and my own solutions work this way: >>> >> > pp0=: *./@(0&<@#, 2&<:, 1 < +./)@(#/....@q: ::0:"0) >>> >>> pp0 4 >>>1 >>> pp0 5 >>>0 >>> >>>FYI, >>> >>>-- >>>Raul >>>--------------------------------------------------------- >>>-- ----------- 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
