Python vs Java performace: brute force equation solver

Question

I wrote a program in Python and in Java to search for the smallest integer solution of the equation:

$$a^5+b^5+c^5+d^5=e^5$$

(expected output is \$133^5 + 110^5 + 84^5 + 27^5 = 144^5\$)

Powers and roots are either computed directly ("direct calculation" method) or computed and stored in an array ("power lookup" method). Fifth powers are looked up like n5 = fifth_power[n]. Fifth power root is computed using a binary search in array 'fifth_power`.

I am running it on NetBeans if it matters. It takes:

• 30 s (Python, direct)
• 20 s (Python, lookup)
• 5.6 s (Java, direct)
• 0.8 s (Java, lookup)

Is there a way to boost Python performance? I am not looking for better math (sieving of some kind). I am looking for better implementation of "for each combination of a,b,c,d compute some of their powers, check if the sum is a perfect power. If it is - print the result".

Is it expected that Python runs some 20 times slower than Java?

Python 3.5

from array import *
import math
import time

#PYTHON, BRUTEFORCE : ~30 s
millis1 = int(round(time.time() * 1000))
keep_searching = True
a=1
result=""
while(keep_searching):
    a+=1
    for b in range(1,a+1):
        for c in range(1,b+1):
            for d in range(1,c+1):
                sum=math.pow(a,5)+math.pow(b,5)+math.pow(c,5)+math.pow(d,5)
                root = math.pow(sum,0.2)
                e = round(root)


                e5 = math.pow(e,5)               

                if(e5==sum):
                    result="{}^5 + {}^5 + {}^5 + {}^5 = {}^5".format(int(a),int(b), int(c),int(d), int(e))
                    keep_searching = False
                    millis2 = int(round(time.time() * 1000))

print(result)
print("Found solution in {} ms".format(millis2-millis1))

#PYTHON, PRECOMPUTE POWERS: ~20 s
millis3 = int(round(time.time() * 1000))  
#fifth_power #175 is enough
size=176
fifth_power = [None] * size
for i in range(size):
    fifth_power[i]=long(math.pow(i,5))

millis4 = int(round(time.time() * 1000))   

#returns  value if it is a perfect power (32 returns 2)  
#returns -1 if between perfect powers, -2 if greater than max value in array, -3 if smaller than min value in array

def check_perfect_power(number, min, max, fifth_power):


    current=int((min+max)/2)
    while(max>=min):
        if(number==fifth_power[current]):
            return current
        elif(number>fifth_power[current]):
            min=current+1
            current=int((max+min)/2)
        else:
            max=current-1
            current=int((max+min)/2)

    if(min>=len(fifth_power)):        
        return -2
    if(max<0):
        return -3

    return -1   

keep_searching = True
a=0
result=""
while(keep_searching):
    a+=1
    for b in range(1,a+1):
        for c in range(1,b+1):
            for d in range(1,c+1):
                mymax=min(int(a*1.32)+1, size-1)
                e=check_perfect_power(fifth_power[a]+fifth_power[b]+fifth_power[c]+fifth_power[d], a, mymax, fifth_power)
                if(e>0):
                    result="{}^5 + {}^5 + {}^5 + {}^5 = {}^5".format(int(a),int(b), int(c),int(d), int(e))
                    keep_searching = False
                    millis5 = int(round(time.time() * 1000))

print(result)
print("Populated in {} ms, find solution in {} ms".format(millis4-millis3,millis5-millis4))

Answer 1

An obvious possible improvement for both languages is storing the values to the fifth power (But I'm going to focus on python here).

In python, while is a keyword and does not need parenthesis. Also, global lookup of methods is slower than local lookup, so I would define pow = math.pow

pow = math.pow
while keep_searching:
    a += 1
    a5 = pow(a, 5)
    for b in range(1, a+1):
        b5 = pow(b, 5)
        for c in range(1, b+1):
            sum_begin = a5 + b5 + pow(c, 5)
            for d in range(1, c+1):
                sum = sum_begin + pow(d, 5)
                ...

Also note that python has an official style-guide, PEP8, which recommends putting spaces around operators and after commas in argument lists (I applied those rules in the code above).

Note that str.format does not care what it's parameters are. It will just call str on them and use that. So no need to call int on your parameters (they are already ints anyway).

Answer 2

C++ bruteforce ~3 s, C++ reference lookup - 0.25 s.

This code has several problems:
(1) math.pow(a,5) is way slower than a**5

(2) It calculates a^5 each time d changes. Rather it should be

for c in range(1,b+1):
    a5b5c5=a5b5+c**5 #c^5 is incremented and a partial sum a^5+b^5+c^5 is calculated

(3) Lists and lookup work blazing fast in C++ (due to the way pointers work), but not in Python. Use set instead.

Adding fifth powers to a set and checking if a^5+b^5+c^5+d^5 is a number in the set is the way to go in Python. With these tweaks code executes in 2 seconds and is faster than the original implementation in C++.