#4612: [with patch, needs work] is_perfect_power for rationals
------------------------------+---------------------------------------------
Reporter: robertwb | Owner: somebody
Type: defect | Status: new
Priority: major | Milestone: sage-3.4
Component: basic arithmetic | Resolution:
Keywords: |
------------------------------+---------------------------------------------
Comment (by cremona):
Replying to [comment:6 robertwb]:
> I just looked at the gmp source, it does trial division for all three-
digit primes, aborting if it finds any inconsistency. If small factors
were found, it can bound the nth roots it needs to test on the remainder
(if any), otherwise it tries taking nth roots for primes up to lg(2).
ok -- I had not thought of checking the p-valuation for small primes but
that's a good idea. Otherwise it's the textbook method, which would not
be hard to adapt to provide the exponent.
>
> It does not compute the largest exponent for which it is an nth root,
only a divisor of it. I wonder if MPIR will would be willing to provide
such a function.
That would be good. All we have to do is ask!
>
> However, I believe there is an easier solution. Noting that the
numerator and denominator are relatively prime, one only needs to check if
the product is a perfect power, and if it is their ratio will be as well.
(It is unclear however whether or not it would be a time savings to do the
(cheaper) test on the smallest of the numerator/denominator first.)
Certainly it's clear that you can replace n/d by n*d, but we already know
what to do if know the numerator is an e'th power and the denom is an f'th
power (answer = gcd(e,f), or the odd part of that if the number was
negative), which would be more efficient. So as long as we can solve the
problem (with the exponent) for integers then it will be easy to do it for
rationals.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4612#comment:7>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
