Hacker News Reader

Comment by zxw | Hacker News Reader

Is there a reason this won't work? It's the most 'readable' way I could come up with.

    #(python code)
    def is_power_of_two(n):
        import math

        if n <= 0:
            return False

        power = round(math.log(n, 2))
        return 2 ** power == n

View on HN

This will probably give the wrong answer for some integer. I have tried something similar in Java. Since it was three years ago my memory is a little hazy. I was working on a parallelizing compiler written in Java (but not for Java) and I saw that the other programmers had used a method similar to yours, it used log anyway. I knew about #9 and #10 and worried that their method was potentially wrong (and also inefficient). To check if it was wrong I coded up something that compared the log-floating point method against #10 for all non-negative integers and the log-floating point method gave the wrong answer for one value (out of 2 billion).

That was Java and your example is in Python, there could be some difference. If you try and compare in Python, please tell us the result.

Here is the code from the first test.[0] It increments a variable and prints a message if their is an inconsistency. I left it running till it reached 1,351,773,471 and didn't come up with any inconsistencies.

I then modified the test[1] to look for inconsistencies where they were most likely to be found, ie ±1 of 2n. I reached n being 1024 before python complained about a 'Result too large'.

[0] http://paste.pound-python.org/show/10067/

[1] http://paste.pound-python.org/show/10068/

Edit: just reread about the 1 in 2 billion chance, I'll leave the first test running longer to make sure.

Nice to see some experimentation. :)

I tested all 2^31 non-negative integers, which is 2147483648 values. If I remember correctly, the value that was wrong was large, probably between 2^30 and 2^31. Java is pretty fast and I think this took tens of minutes. Python is about 20 times slower so it may take hours for you.

Yeh it's fairly slow going. I'm at 3,706,382,752 and am going to call it a day. Looks like the code works properly.

math.log uses floating point arithmetic. That will lead to trouble on large numbers. The article addresses the issue.

I'm not doing power == int(power) though which is what he warns against. I haven't done a lot of testing however as far I can tell it's working.

    >>> is_power_of_two(2 ** 31 - 1)
    False
    >>> is_power_of_two(2 ** 31)
    True
    >>> is_power_of_two(2 ** 31 + 1)
    False

    >>> is_power_of_two(2 ** 548 - 1)
    False
    >>> is_power_of_two(2 ** 548)
    True
    >>> is_power_of_two(2 ** 548 + 1)
    False

Yes. It seems to work for much larger numbers than this on my version of Python, but going via doubles leaves a bad taste.

Reply on news.ycombinator.com