How to parallelize this algorithm?

Question

triples = []
for a_side in range(1, 21):
    for b_side in range(a_side, 21):
        for c_side in range(1, min(a_side + b_side, 21)):
            if a_side*a_side + b_side*b_side == c_side*c_side:
                triples.append((a_side, b_side, c_side))
 
print(triples)

There is an algorithm for finding the Pythagorean Triplets. How to parallelize this algorithm?

https://stackoverflow.com/questions/9786102/how-do-i-parallelize-a-simple-python-loop — JJ., Dec 27 '21 at 11:17

Alain T. · Answer 1 · 2021-12-29T05:56:42.297

Parallellizing isn't going to improve performance as much as a better algorithm. By building a dictionary of squares that you intersect with itself, you could get the triplets with only one level of loop nesting.

You can even do it in a list comprehension:

s = {n*n:n for n in range(1,21)}  # squares dictionary: {n^2:n}

T = [ (s[a2],s[c2-a2],s[c2])                     # triples n^2 --> n
      for c2 in s                                # c^2
      for a2 in takewhile(lambda n2:n2<c2-n2,s)  # a^2 < b^2
      if c2-a2 in s ]                            # b^2 exists ?

print(T) # in ascending order of c^2
[(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17), (12, 16, 20)]

This can be converted to generators which will allow you to launch threads for interleaved values of c^2:

maxSide      = 20
processCount = 3

# preparation ...
squares      = {n*n:n for n in range(1,maxSide+1)}
result       = [[] for _ in range(processCount)] # per process results

# Launching parallel processing ...
from itertools import islice,takewhile
from threading import Thread
threads = []
for p in range(processCount):
    
    # launch Thread/Process for subset of c^2 values
    t = Thread(target= lambda:
               result[p].extend( (squares[a2],squares[c2-a2],squares[c2])
                      for c2 in islice(squares,p,maxSide,processCount)
                      for a2 in takewhile(lambda n2:n2<c2-n2,squares)
                      if c2-a2 in squares ) )
    t.start()
    threads.append(t)
        
# wait for threads/processes to finish ...
for t in threads:
    t.join()

output:

print(result)
[[(6, 8, 10), (5, 12, 13)], 
 [(3, 4, 5), (8, 15, 17), (12, 16, 20)], 
 [(9, 12, 15)]]

# assemble results (you could merge sublists to get c^2 order without sorting)
final = []
for r in result:final.extend(r)

print(sorted(final,key=lambda t:t[2]))
[(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17), (12, 16, 20)]

Note that this example uses the threading module for simplicity of demonstration. Python's Global Interpreter Lock will not allow these CPU-bound threads to actually run in parallel so there is no gain in execution time. To get actual parallel processing, you would have to use the multiprocessing module which will be considerably more involved from a resource sharing and result consolidation perspective

score 0 · Answer 2 · answered Dec 27 '21 at 11:22

you dont need to calculate c here just need to find the squareroot is int or not

so a little better version of your code

triples = []
store_square ={a_side:a_side**2 for i in range(1,22)}

for a_side in range(1, 21):
    val = store_square[a_side]
    for b_side in range(a_side+1, 21):
        val2 = store_square[b_side]
        sum_ = val+val2
        c_side = sum_**0.5
        if c_side%1==0:
               triples.append((a_side, b_side, int(c_side))
print(triples)

How to parallelize this algorithm?

2 Answers2