#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 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).
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.
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.)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4612#comment:6>
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
-~----------~----~----~----~------~----~------~--~---
