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