Python make math calculations faster-CodePudding

I have this code to find the Pythagorean triplets, which works fine. I just want to make it faster. On my Intel i5 1135G7, it takes about 0.1272754669189453 time. Maybe it could be done using the multiprocessing module, as my CPU is not 100% utilized.

import math
import time 


results = [] 

start_time = time.time()

def triplets4(n):
    for a in range(n):
        for b in range(a, n):
            c = math.sqrt(a * a   b * b) 
            if c.is_integer() and c<=n:
                results.append([a , b, int(c)])

triplets4(1000)

end_time = time.time()

for x in results:
    print(x)

print(end_time-start_time) #print time elapsed

CodePudding user response：

I'm not a python programmer but after observing a few opportunities, I thought I'd make a few modifications for performance optimisation. Python is not a great language to use for speed except when using optimised library functions. You need a script you can compile for performance. Multi-threading can make your program faster but often requires a major refactoring of code. I excluded a=0 from the outputs as I don't think they count as triples. Anywho, this is what I did which runs all of 20%(!) faster on my computer, even after removing a=0 from your script. While the performance gain isn't great, I think some lessons can be learnt from the changes I made.

import math
import time 


results = [] 

start_time = time.time()

def triplets4(n):
    n2 = n*n
    for a in range(1, n):
        a2 = a*a
        blim = 1 int(math.sqrt(n2 - a2))
        for b in range(a 1, blim):
            arg = a2   b * b
            c = math.sqrt(arg) 
            if c.is_integer():
                results.append([a , b, int(c)])

triplets4(1000)

end_time = time.time()

for x in results:
    print(x)

print(end_time-start_time) #print time elapsed

CodePudding user response：

Short Answer

One simple way is to add a check for (a * b) % 12 != 0 before running sqrt or is_integer.

According to the Wolfram page on Pythagorean Triplets, the product of the legs (a and b) of a Pythagorean triplet/triangle is always divisible by 12.

Long Answer

We should profile your code first. Just to keep things simple, I've removed the print statements and timers, so we're working with this version of your code:

import math

results = [] 

def triplets4(n):
    for a in range(n):
        for b in range(a, n):
            c = math.sqrt(a * a   b * b) 
            if c.is_integer() and c<=n:
                results.append([a , b, int(c)])

triplets4(1000)

Using cProfile:

python -m cProfile .\pythagorean.py      
         1002950 function calls in 0.270 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.270    0.270 {built-in method builtins.exec}
        1    0.000    0.000    0.270    0.270 pythagorean.py:1(<module>)
        1    0.175    0.175    0.269    0.269 pythagorean.py:5(triplets4)
   500500    0.051    0.000    0.051    0.000 {built-in method math.sqrt}
   500500    0.043    0.000    0.043    0.000 {method 'is_integer' of 'float' objects}
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:1167(_find_and_load)
     1881    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}

Most of the time is spent on math.sqrt and is_integer.

So, to speed up your code we should just make fewer calls to those functions.

The simplest way I can think of is a divisibility test.

import math

results = [] 

def triplets4(n):
    for a in range(n):
        for b in range(a, n):
            # product of legs must be divisible by 12
            if (a * b) % 12 != 0: continue
            c = math.sqrt(a * a   b * b) 
            if c.is_integer() and c<=n:
                results.append([a , b, int(c)])

triplets4(1000)

python -m cProfile .\pythagorean_v2.py
         280672 function calls in 0.174 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.174    0.174 {built-in method builtins.exec}
        1    0.000    0.000    0.174    0.174 pythagorean_v2.py:1(<module>)
        1    0.135    0.135    0.174    0.174 pythagorean_v2.py:5(triplets4)
   139361    0.021    0.000    0.021    0.000 {built-in method math.sqrt}
   139361    0.018    0.000    0.018    0.000 {method 'is_integer' of 'float' objects}
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:1167(_find_and_load)
     1881    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}

In both versions we're still appending the same amount of triplets (1881), so that's a good sign.