How can I make this Project Euler solution execute in Python at the same speed as Java?

Question

Before anyone starts in, I know that talking about "speed" in a programming language isn't always the most... useful discussion. That said, speed is the issue here.

I tackled Project Euler problem 5 in both languages and, while my implementations in both languages look fairly similar to my eye, the runtime is vastly different. Java returns an answer in only a few seconds whereas Python can take up to a minute (on the same machine, of course). I'm quite certain this is less the fault of Python and more the fault of a programmer (me) who hasn't quite learned to think Pythonically.

Note that I am not asking you to rewrite my code. I'm simply looking for a few nudges in the right direction. (And yes, I've looked at some similar threads but most of those are over my head and aren't directly comparing the same algorithm in two languages. This thread is helpful, but again, doesn't directly compare Java and Python - and frankly the answers are a little hard to follow.)

Without further ado:

Java

public class Problem5 {

    public static void main(String[] args){
        boolean found = false;

        for (int i = 20; !found; i += 20){
            if (DivisThrough20(i)) {
                found = true;
                System.out.println(i);
            }
        }
    }

    private static boolean DivisThrough20(int number){
        boolean result = true;
        for (int i = 19; result && i > 1; i--){
            if (number % i != 0) result = false;
        }
        return result;
    }
}

Python

def DivisThroughTwenty(number):
    for x in range(20,1,-1):
        if number % x != 0:
            return False
    return True

# the number we're looking for can't be any lower than 20, so we'll
# start there as a small optimization
testNumber = 20

keepLooking = True

while keepLooking:
    if not DivisThroughTwenty(testNumber):
        testNumber += 20
    else:
        keepLooking = False

print testNumber

It's funny, reading these side by side I can already see that the Python version of this algorithm is slightly more optimized than the Java version, yet it's still much slower. I'm even more curious to find another way to approach the problem now.

Answer 1

Python is a dynamically typed language, while Java is a statically typed language. This means that Java has more readily available information at compile time about what types your variables are, in particular numbers. Java's designers spent quite a bit of effort defining the JVM in such a way that 32-bit (int) and 64-bit arithmetic (long) calculations can work in an efficient manner.

Python, on the other hand, does not have variable type declarations so the variables such as x can hold any object at all. In your case, it happens that they always hold numbers, but CPython's compiler doesn't go to the effort of verifying that. When Python executes your code, evaluating an expression such as number % x involves looking up the % operator for the object represented by number, calling the % operator, getting the type of x, making sure it is a compatible number type, etc. This all takes time, particularly when you're doing it zillions of times.

Alternate Python implementations such as PyPy go to great effort to try to nail down the types of your variables. In your case, it could determine that number and x always refer to integers, and generate appropriate low-level code that doesn't have to check types.

Finally, you might want to look up the Least common multiple for a faster way to solve this Project Euler problem, in any language. As is common with Project Euler problems, the fastest solution is found not by writing faster code, but by choosing an appropriate algorithm.

Answer 2

I'm not sure how much this might help, but your worker code can be rewritten in a much more pythonic way like so:

def divis_through_twenty(n):
  return any(n % x for x in xrange(20,1,-1))

x = 20
while divis_through_twenty(x):
  x += 20

print x

You can optimise it a bit more if you like (e.g., if you already tested a number was divisible by 20, you don't need to check if it's divisible by 10, 5, or 2).