IsPerfectPower

[James Wanless]

On 16 Mar 2011, at 13:45, Torbjorn Granlund wrote:

> James Wanless <james at grok.ltd.uk> writes:
>
>  On 16 Mar 2011, at 12:17, Torbjorn Granlund wrote:
>
>> James Wanless <james at grok.ltd.uk> writes:
>>
>> Code should go _something_ like this (I don't pretend this is a
>> genuine patch)
>> File mpz/perfpow.c should replace its only function implementation,
>> mpz_perfect_power_p, thusly:
>>
>> I don't follow you at all.  We have quite good code for detection of
>> perfect powers already.
>
>  This returns the actual root?
>  [though, like I said, maybe your version is just as fast :)]
>
> We are not communicating very well, are we?  :-(

Yes, I was beginning to get to the same conclusion (I sometimes try to  
hurry my responses when it would be better to draw breath)...

>
> I thought the operation you asked for was computation of the nth  
> root of
> some (large) integer a given that it is known by the caller that the
> exact result will be an integer.
>
> Was this what you mean?

Yes, exactly, [thank you!!!] (this I _can_ say with confidence). But  
note that my method does not require to know or evaluate n in advance  
(I believe).

>
> Then you quote mpz_perfect_power_p which does not seem to have much to
> do with this.  We have great code for mpz_perfect_power_p (by means  
> of a
> quite new mpn_perfect_power_p).

Yes, you are absolutely right - I _don't_ want to deal with  
mpz_perfect_power_p [because this just returns a boolean]. In fact the  
whole title of this thread [as created by me :-( ] I realize now is a  
misnomer. I probably should have called it something like  
'PerfectRoot' instead.

>
> (It is quite possible that some code from mpn_perfect_power_p can be
> reused from this new function, but that's a different story.)

Well, hopefully I've been of _some_ use (!), but I think you'd better  
not ask me to try to contribute any more... [for one thing GMP already  
has so many lovely optimizations that it would take me a long time to  
get up to speed on them, if I really tried to get to grips with the  
internal workings - I'm just glad I can use it myself as a 'black box'  
of some power!]

>
> -- 
> Torbjörn

James