1

Based on this answer, I'm implementing a simple algorithm in Python 3.x to determine whether or not a integer n is a power of another integer base. However, the algorithm doesn't return the correct result. The code in the linked answer is:

while (n % 3 == 0) {
    n /= 3;
}
return n == 1;

(A comment indicates that checking n == 0 is also necessary, logically). This is my code:

def is_power(n: int, base: int) -> bool:
    if n == 0:
        return false
    while (n % base == 0):
        n /= base
    return n == 1

I wrote simple testing code that tests a certain range of bases and exponents, but the results it returns are incorrect. Testing code:

for base in range(3, 10):
    print("Base: {0}".format(base))
    for exp in range(30, 40):
        b = is_power(pow(base, exp), base)
        if not(b):
            print("{: <3}: {: <5}".format(exp, str(b)))

I tested this with a much larger range, but for the sake of output, I limited it in this example. This outputs:

Base: 3
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 4
Base: 5
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 6
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 7
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 8
Base: 9
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False

which is clearly incorrect. I've tried debugging a small example, where n = pow(3, 35) and base = 3 yields these values of n in the loop:

50031545098999707
1.6677181699666568e+16

and the loop ends, because 50031545098999707 / 3 == 1.667718169966656 9 e+16 (note that the last digit is different). Is this the problem? Are Python's calculations failing? If not, what is the problem with this algorithm?

The algorithm also fails even more if I use math.pow instead, but I'm not necessarily surprised by that, since checking one example demonstrates that pow and math.pow don't always return the same value. 

import math
pow(3, 35) == math.pow(3, 35) # 50031545098999707 != 5.0031545098999704e+16
Community
  • 1
  • 1
Ricardo Altamirano
  • 14,650
  • 21
  • 72
  • 105
  • Why the function annotations? –  Jul 21 '12 at 23:09
  • @delnan By now, force of habit. I'm not sure how I got into the habit in the first place, though. – Ricardo Altamirano Jul 21 '12 at 23:47
  • I'm curious to know why this question would be considered too localised; although in hindsight, it's a tad foolish of a question, I think the [accepted answer](http://stackoverflow.com/a/11595679/869912) makes a lot of important points, and real division vs. integer division isn't exactly a narrow issue. – Ricardo Altamirano Jul 22 '12 at 00:10

2 Answers2

7

Since you are using Python 3, you should use

def is_power(n: int, base: int) -> bool:
    if n == 0:
        return false
    while (n % base == 0):
        n //= base
    #     ^^ note two slashes
    return n == 1

In Python 3.x, the / operation always perform "real division" and return a floating point number, but in the algorithm you've linked to, it expects the / to do integer division, which is done with the // ("floor division") operator instead.

And the test fails really because of the lack of precision in floating-point arithmetic, as you have expected. The algorithm is still correct when / returns an infinite-precision real number. Take 3.034 as an example,

3.0 ** 34 == 16677181699666569
          == 0b111011001111111100111011110011000100000011001010001001

The default floating-point format only supports 53 bits of precision, but the above number requires 54 bits to represent, so we have to round off the last bit (the 1), resulting in 

             0b111011001111111100111011110011000100000011001010001000
                                                                    ^
          == 16677181699666568

which the modulus to 3 will return 2, which will break the loop and return false.

(I haven't checked why it rounds down instead of up, but even if it rounds up the modulus is still not zero, so it will still return false.)

kennytm
  • 510,854
  • 105
  • 1,084
  • 1,005
  • This is correct. `11/2 = 5` in python2 but is '5.5' in python3 (or in python2 with `from __future__ import division`). – ninjagecko Jul 21 '12 at 20:43
  • And... I'm a fool. Thanks for pointing out the error. I can't believe that slipped my mind... – Ricardo Altamirano Jul 21 '12 at 20:44
  • `def is_power(n: int, base: int) -> bool` I am not familiar with this notation "->bool" .. is this some sort of indication of what this function is going to return? I just looked through "What's new in v3" and if it's there, I must have missed it. – Levon Jul 21 '12 at 22:44
  • @Levon The [what's new](http://docs.python.org/release/3.0.1/whatsnew/3.0.html) section links to [PEP 3107](http://www.python.org/dev/peps/pep-3107/#syntax) on function annotations. The annotations don't restrict anything about the function; they just provide a standardised way of annotating its parameters and return values. (See the PEP for a better explanation than I can give) – Ricardo Altamirano Jul 22 '12 at 02:17
  • @KennyTM - I just saw your edit to the question, and that's a *great* example. Thank you for the additional information! – Ricardo Altamirano Jul 22 '12 at 02:19
  • @RicardoAltamirano Thank you very much for the information and links, I did think it was some sort of documentation aid, it'll be interesting to find out more. – Levon Jul 22 '12 at 02:23
2

Think about your algorithm: what do you want /= to do?

Floating point division? Or integer division? Your question clearly uses the former, but try it by hand and see if it will work--you will keep dividing by base and getting non-integers.

In python 3, integer division is //.

Andrew Jaffe
  • 26,554
  • 4
  • 50
  • 59