-1

is_perfect is a method to check whether a number has a perfect nth root.
For example:
- is_perfect(125,3) should return True as 5^3 is 125 an integer
- is_perfect(126,3) should return False as there is no integer M for which M^3 is an integer

def is_perfect(num,power):
    root = 0.00
    p = 0.00
    float(p)
    p = 1.0/power
    root = num**(p)
    print ("root",root,sep = ' ')
    print ("root**power",root**power,sep = ' ')
    check = num -(root**power)
    print (check)
    if check < 1e-14:
        root = math.ceil(root)
    if (root-int(root)) ==0:
        print(num,root,int(root),p,sep = ' ')
        return True
    else:
        print(num,root,int(root),p,sep=' ')
        return False

In Python shell both give False when the result of 125 should be true.

>>> is_perfect(126,3)
root 5.0132979349645845
root**power 125.99999999999999
1.4210854715202004e-14
126 5.0132979349645845 5 0.3333333333333333
False
>>> is_perfect(125,3)
root 4.999999999999999
root**power 124.99999999999993
7.105427357601002e-14
125 4.999999999999999 4 0.3333333333333333
False
>>>

How can I modify my method to achieve the desired result.

akshaynagpal
  • 2,965
  • 30
  • 32

3 Answers3

3

As you see, the differences are slightly higher than the strict threshold you've set -- for example, 7.105427357601002e-14 vs your threshold of 1e-14.

Here's a different, simplistic approach, which uses integers as much as feasible, and works:

import math

def is_perfect(num, power):
    candidate = num ** (1/power)
    lo_candidate = int(math.floor(candidate))
    hi_candidate = int(math.ceil(candidate))
    return num == lo_candidate**power or num == hi_candidate**power

Added...: For extremely large floats, floor and ceil may be unable to return two adjacent ints, which might cause this simplistic approach to give a false negative. Here's a less simplistic approach that works, even for ginormous numbers, as long as int(math.floor(candidate)) <= candidate (and you have enough memory:-)...:

def is_perfect(num, power):
    float_candidate = num ** (1/power)
    int_candidate = int(math.floor(float_candidate))
    while True:
        powered = int_candidate ** power
        if powered == num: return True
        elif powered > num: return False
        int_candidate += 1

Added**2: and here's a version @Kevin considers more readable (matter of opinion:-)...:

import itertools

def is_perfect(num, power):
    float_candidate = num ** (1/power)
    for int_candidate in itertools.count(int(math.floor(float_candidate))):
        powered = int_candidate ** power
        if powered == num: return True
        elif powered > num: return False

Style apart there's still a problem with float_candidate = num ** (1/power) if num is an int too large to convert to a float (you get an OverflowError on that line). In real life I'd use gmpy.root from my good old gmpy package, but see also How to compute the nth root of a very big integer for alternatives.

However, a "dirty trick" worth knowing is to replace the first statement with:

    float_candidate = math.exp(math.log(num)/power)

because, peculiarly!, math.log(num) can be computed even for very large values of num which would cause an OverflowError in num ** (1/power)... (!)

Community
  • 1
  • 1
Alex Martelli
  • 854,459
  • 170
  • 1,222
  • 1,395
  • 1
    This will probably stop working once `candidate == candidate+1` starts being true (around `candidate = 9007199254740992.0` or so). – Kevin Dec 22 '14 at 17:53
  • @Kevin yes, if `floor` and `ceil` of extremely large floats are not some `x` and `x+1`. This can be fixed as long as `floor` is guaranteed to be `<= candidate` -- let me edit to show how. – Alex Martelli Dec 22 '14 at 17:56
  • You can use logarithms to reduce the magnitude of the values. If `y` is the `n`th root of `x`, then `log(y) == log(x)/n`. – chepner Dec 22 '14 at 18:03
  • I think you want to increment `power` in that last line, not `powered`. Otherwise, you could end up with an infinite loop. To make it easier to read, I'd prefer to use `itertools.count()` here. – Kevin Dec 22 '14 at 18:06
  • @chepner yes, but with logarithms you're inevitably dealing with `float`s, so `==` is just an approximation (which may not hold even when "mathematical equality" would). The key idea in my answer is to work with `int`s as much as possible. – Alex Martelli Dec 22 '14 at 18:06
  • @chepner I think your comment may answer the problem. Can you give some example of the log technique you used. – akshaynagpal Dec 22 '14 at 18:10
  • @Kevin, I actually meant to increment `int_candidate` in the last line -- neither `powered`, which immediately gets recomputed, nor `power`, the exponent. Thanks for noticing the thinko (which I've now edited away) even though your comment proposed the wrong fix:-). `itertools.count` is an interesting alternative to the simple `+= 1`, it's debatable whether it's more readable, but anyway the key issue is to increment the **right** variable, not **how** precisely to increment it. – Alex Martelli Dec 22 '14 at 18:11
  • I recommended `itertools.count()` in particular because you can transform the `while` into a `for`, which IMHO is nicer. – Kevin Dec 22 '14 at 18:14
  • @Kevin, OK, added the version you consider nicer -- it's OK. BTW, in real life I'd use `gmpy.root` (I'm not `gmpy`'s current maintainer any more, but I was its original author:-); otherwise one might get `OverflowError: int too large to convert to float` (with truly ginormous numbers). – Alex Martelli Dec 22 '14 at 18:33
  • To accommodate Python 2.x you should explicitly ensure that `1/power` is performed in floating-point arithmetic in the first line: either say `1/float(power)` or just `1.0 / power`. – jez Dec 22 '14 at 18:42
  • @jez, the OP's code had several examples of `print`-as-a-function, hence likely Python 3. Anyway, to work in e.g 2.7 it's best to start the module with `from __future__ import division, print_function` rather than uglifying the code:-). – Alex Martelli Dec 22 '14 at 19:01
  • 1
    Logarithms would quickly give you a floating point value to give you integer candidates. Suppose you want to know if 344 has an integer 8th power. A little algebra will show that the `y = exp(log(344)/8)` evaluates to 2.0752.... You can verify that `2**8 < 344` and `3**8 > 344`, indicating that there is no integer 8th root of 344. Similarly, the cube root of 125 is near `exp(log(344)/3 = 5.000000000001`, and you can quickly see that `5**3 == 125`. – chepner Dec 22 '14 at 19:13
  • @chepner, it's peculiar but true that `math.log(huge_int)` can indeed be computed even when `float(huge_int)` or `huge_int ** (1/N)` give an `OverflowError`. So you can indeed exploit this peculiarity to get the `int_candidate` (lower bound for a root) though then you do need to follow the rest of my solution (e.g, say `huge_int=9007199254740992**33`; now `int(math.floor(math.exp(math.log(huge_int)/33)))` is `9007199254740986` so you'll need to try several candidates up from that. Still a dirty trick worth knowing so I'm editing the answer, and, +1!-) – Alex Martelli Dec 22 '14 at 19:25
  • Hi @AlexMartelli! I've added an answer showing the use of `gmpy2`. Like you mentioned earlier, `gmpy` / `gmpy2` can handles large numbers quickly and without erros due to limited precision. – casevh Dec 24 '14 at 17:37
  • Hi @casevh, long time no see! Congratulations for your great ongoing work on `gmpy`! – Alex Martelli Dec 24 '14 at 17:47
2

To avoid rounding errors in floating-point comparisons, you'll have to do some rounding and perform a final confirmation using integers:

def is_perfect( value, exponent ):
    root = value ** ( 1.0 / exponent )
    root = long( round( root ) )
    return root ** exponent  == value

To test:

[ x for x in range( 1000 ) if is_perfect( x, 3 ) ]

Output:

[0, 1, 8, 27, 64, 125, 216, 343, 512, 729]

Let's write a diagnostic test to see how high it can go:

def test( root, exponent ):  # should print [False, True, False]
    print( [ is_perfect( root ** exponent  + i, exponent ) for i in ( -1, 0, +1 ) ] )

For me, with an exponent of 19, the test fails when the root reaches somewhere in the 14 digit range. At this point when value = root**exponent is computed, value is around 900 bits long.

test( 100000000000000, 19)  # prints [False, True, False]
test( 999999999999999, 19)  # prints [False, False, False]
jez
  • 14,867
  • 5
  • 37
  • 64
  • but rounding will bring value more closer to root which will result in output True even when it should be False! @jez – akshaynagpal Dec 22 '14 at 18:13
  • Can you demonstrate a case in which it fails? The key is the last line: it will not return `True` unless `root ** exponent` (both integers) equal the value you put in, which is by definition what you wanted. – jez Dec 22 '14 at 18:32
  • Note that, while I think I can guarantee no false positives, I make no claim that there are no false *negatives* when very large numbers are involved – jez Dec 22 '14 at 19:17
  • I have to calculate upto n=19. Which is giving me runtime error. Any solution? – akshaynagpal Dec 22 '14 at 19:18
  • @A_nagpal not unless you're much more specific with your questions. You haven't mentioned `n` before—is that the root, the exponent, or the value you get from combining them? The most challenging case is when it's the exponent, but in that case you can still get pretty darn high (see edited answer). I don't know where your runtime error would be coming from unless I see it—works for me on both 32-bit and 64-bit systems. – jez Dec 24 '14 at 02:45
  • n =19 means 19th root of a number .hence n is exponent. – akshaynagpal Dec 24 '14 at 09:16
2

Disclaimer: I'm the current maintainer of @Alex Martelli's gmpy module. The current version is called gmpy2 and is available at https://code.google.com/p/gmpy/

If you can use an external library, the gmpy2.is_power and gmpy2.iroot are your best options.

gmpy2.is_power(x) will return True if the number is an exact power. It won't tell you the exponent but it will quickly identify those numbers are exact powers. gmpy2.iroot(x, n) will return a tuple containing the integer n-th root and a boolean value that indicates if the root is exact or not.

>>> gmpy2.is_power(123456789123456789**19)
True
>>> gmpy2.is_power(123456789123456789**19+1)
False
>>> gmpy2.iroot(123456789123456789**19, 19)
(mpz(123456789123456789), True)
>>> gmpy2.iroot(123456789123456789**19+1, 19)
(mpz(123456789123456789), False)

gmpy2 has improved support for multiple-precision floating point numbers. This led to a naming conflict: Should sqrt, 'root, etc. return an integer (as in gmpy) or a floating-point value? I chose to add isqrt, iroot, etc. to return integer values and sqrt, root, etc. now return floating-point values. This follows the convention of the math module.

Alex Martelli
  • 854,459
  • 170
  • 1,222
  • 1,395
casevh
  • 11,093
  • 1
  • 24
  • 35