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))

• Simon Forsberg: Obvious question: Did you implement it in the same way for both Java and Python?
• Stepan: I did. pastebin.com/G4V3fHnD So, is this performance difference expected?
• 301_Moved_Permanently: stackoverflow.com/questions/672857/is-python-slower-than-java-c & snaplogic.com/blog/…
• BitTickler: On my machine for bruteforce approach: Py: 58s Rust 1.7s C++: 1.3s F# 2.4s. My recommendation: if you do a lot of numerics, don't use python.
• BitTickler: ... And haskell: 1.7s

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).

• Stepan: Python Power lookup stores fifth powers in an array. It Computes n^5 by calling arr[n] and it computes n^(1/5) by a binary search within 'arr.
• Graipher: @Stepan Not sure I missed some code or your edit added it. The way it is now, yes your array approach is better. However, storing the intermediate results is also a valid (and easy) improvement on your other method.

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++.