IsPerfectPower

[James Wanless]

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:

int
mpz_perfect_power_p (mpz_srcptr u)
{
	// begin added JGW 2011-03-16
	mpz_srcptr temp1, temp2, temp3;

	mpz_powm(temp1, 2, u, u);
	
	mpz_sub(temp2, temp1, 2);

	mpz_gcd(temp3, u, temp2);
	
	if (mpz_cmp(temp3, 1) > 0)
		return temp3;
	// end added JGW 2011-03-16
	
   return mpn_perfect_power_p (PTR (u), SIZ (u));
}

On 16 Mar 2011, at 11:25, James Wanless wrote:

>>
>> Is this an algorithm for computing a^{1/b} which works just when a  
>> is an
>> integer (and b is an integer too)?
>>
>> We don't have, but that should be very simple to do using 2^t-adic
>> arithmetic and lifting (increasing t).  Is that what ACCANT does?
>
> I _think_ you're saying the same thing.
> Basically it relies on gcd of 2^a-2 and a (ie FlittleT) to find a^(1/ 
> b) [I think I've got that right]
>
>>
>> I guess a good implementation it would be less than a page of mpn  
>> code.
>
> If you're tentatively suggesting I write such - I'd be (sortof)  
> prepared to have a go, though a) I'd be a little nervous of messing  
> something up and b) you _might_ find by the time you've sorted me  
> out it would have been quicker to write it yourself (eg I've never  
> yet used 'patch', though maybe it's something I should learn! :) ).  
> Anyway (to answer your question) I (too) believe the algorithm is  
> very simple
>
>>
>> -- 
>> Torbjörn
>
> James
>
>
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss