Find the smallest regular number that is not less than N (Python)

This is from an answer to my own StackOverflow question on how to efficiently find a regular number that is greater than or equal to a given value.

I originally implemented this in C# but translated it to Python because I guessed (correctly) that it would be shorter and would eliminate a third-party library dependency.

I am a Python newbie though - This is the longest Python program I have ever written. So I would like to know:

• Is there a convention for indicating what version of the language you are targeting (like require  in perl?) This program only works in 2.6.

• Instead of the priority queue, is there a better way to generate the odd regular numbers? I know it is possible to implement lazy lists in Python but they are not in 2.6 are they?

• Any other idioms/naming conventions I am missing?

from itertools import ifilter, takewhile
from Queue import PriorityQueue

def nextPowerOf2(n):
    p = max(1, n)
    while p != (p & -p):
        p += p & -p
    return p

# Generate multiples of powers of 3, 5
def oddRegulars():
    q = PriorityQueue()
    q.put(1)
    prev = None
    while not q.empty():
        n = q.get()
        if n != prev:
            prev = n
            yield n
            if n % 3 == 0:
                q.put(n // 3 * 5)
            q.put(n * 3)

# Generate regular numbers with the same number of bits as n
def regularsCloseTo(n):
    p = nextPowerOf2(n)
    numBits = len(bin(n))
    for i in takewhile(lambda x: x = n, regularsCloseTo(n))
    return min(bigEnough)

from itertools import ifilter, takewhile
from Queue import PriorityQueue

def nextPowerOf2(n):

Python convention says that function should be named with_underscores

p = max(1, n)
    while p != (p & -p):

Parens not needed.

p += p & -p
    return p

I suspect that isn't the most efficient way to implement this function. See here for some profiling done on various implementations. http://www.willmcgugan.com/blog/tech/2007/7/1/profiling-bit-twiddling-in-python/

# Generate multiples of powers of 3, 5
def oddRegulars():
    q = PriorityQueue()

So this is a synchronized class, intended to be used for threading purposes. Since you aren't using it that way, you are paying for locking you aren't using.

q.put(1)
    prev = None
    while not q.empty():

Given that the queue will never be empty in this algorithm, why are you checking for it?

n = q.get()
        if n != prev:
            prev = n

The prev stuff bothers me. Its ugly code that seems to distract from your algorithm. It also means that you are generating duplicates of the same number. I.e. it would be better to avoid generating the duplicates at all.

yield n
            if n % 3 == 0:
                q.put(n // 3 * 5)
            q.put(n * 3)

So why don't you just push n 3 and n 5 onto your queue?

# Generate regular numbers with the same number of bits as n
def regularsCloseTo(n):
    p = nextPowerOf2(n)
    numBits = len(bin(n))

These two things are basically the same thing. p = 2**(numBits+1). You should be able to calculate one from the other rather then going through the work over again.

for i in takewhile(lambda x: x <= p, oddRegulars()):
        yield i << max(0, numBits - len(bin(i)))

I'd have a comment here because its tricky to figure out what you are doing.

def nextRegular(n):
    bigEnough = ifilter(lambda x: x >= n, regularsCloseTo(n))
    return min(bigEnough)

I'd combine those two lines.


Is there a convention for indicating what version of the language you are targeting (like > require in perl?) This program only works in 2.6.

Honestly, much programs just fail when trying to use something not supported in the current version of python.


I know it is possible to implement lazy lists in Python but they are not in 2.6 are they?

Lazy lists? You might be referring to generators. But they are supported in 2.6, and you used one in your code.

StackExchange Code Review Q#8928, answer score: 2