Rounding a number up to the nearest multiple of a power of 2

Question

I'm doing some programming challenges over at CodeEval and came across a pretty straight forward simple one:

Given numbers x and n, where n is a power of 2, print out the smallest multiple of n which is greater than or equal to x. Do not use division or modulo operator.

So the input looks something like this: 13, 8 first number being x second number being n. My first instinct was to use a while loop and return the result of multiplying the number once the loop hits the correct result, so:

 8 * 0 = 0
 8 * 1 = 8
 8 * 2 = 16; break because it's greater then 13

My question is, is it considered bad form to use float("inf") instead of a set number to multiply up to?

import sys


def multiply(x, y):
    max_multiple_try = 0
    while max_multiple_try != float("inf"):
        res = x * max_multiple_try
        if res != x and res >= y:
            return res
        else:
            max_multiple_try += 1


if __name__ == '__main__':
    with open(sys.argv[1]) as data:
        for line in data.readlines():
            numbers = line.rstrip().split(",")
            print(multiply(int(numbers[1]), int(numbers[0])))

Answer 1

Function interface

First of all, it is good that you used a function to contain the code solving the problem!

However, there are some shortcomings:

• It is very confusing that the function parameter representing \$n\$ from the problem description is named x, and the one representing \$x\$ is named y.

• The function is badly named, as it doesn't multiply the two arguments. A better name would be smallest_multiple or similar.

• The function lacks a docstring which describes what it does. It is therefore hard to check if it is implemented correctly. The first sentence of the problem description would make a good docstring (replacing "print out" with "return").

Bug

The function returns the wrong result if both arguments are the same, for example:

>>> multiply(8, 8)
16

But the smallest multiple of 8 which is greater than or equal to 8 should be 8, not 16.

(Maybe you thought that 8 is not considered a multiple of 8?)

The bug is fixed by removing the res != x condition.

Loop exit condition

Let's ignore everything that doesn't affect the max_multiple_try variable:

max_multiple_try = 0
while max_multiple_try != float("inf"):
    …
    if …:
        …
    else:
        max_multiple_try += 1

We can see that it is always an integer (which has unlimited size in Python). Therefore it can never be equal to the special float('inf') value, and the loop could as well have been written using while True: ….

However, as max_multiple_try simply counts the loop iterations, this pattern would be better written as a for loop using itertools.count (and using a simpler and more descriptive name):

from itertools import count
…
for factor in count():  # factor = 0, 1, 2, …
    res = x * factor
    if res >= y:
        return res

Top-level code

Congratulations on using if __name__ == '__main__' and using with to open a file!

Here are some improvements:

• Iterate directly over data instead of using readlines.

• Use tuple assignment:

  x, n = line.rstrip().split(",")
  print(multiply(int(n), int(x)))
  

Alternative algorithm

The problem states that the value of \$n\$ is constrained to powers of two. While your solution actually solves the more general problem for any value of \$n\$, this description probably aims for a different algorithm which makes use of the constraint.

Hint: What does the binary representation of powers of two look like? How could you solve the problem if \$n\$ were constrained to powers of ten?

Answer 2

As someone hinted before, the 'n' is limited to powers of 2. I'm no python expert, but I assume python ints are 64 bit and that number will be big enough not to worry about overflow. And you certainly don't need floating point.

def findMultiple(maxx, powern):
    res = powern
    while res < maxx:
        res = res + powern;
    return res

Answer 3

If you want to avoid explicitly calling float('inf'), you can bypass it as follows:

def multiply(x, y):
    max_multiple_try = 0

    while True:       

        res = x * max_multiple_try

        if res != x and res >= y:
            return res
        else:
            max_multiple_try += 1

        if res+1 == res: ###implicit float('inf') check

            return 'not found'