Problem: A Pythagorean triplet is a set of three natural numbers, $a<b<c$ such that

\[a^2+b^2=c^2\]

For example, $3^2+4^2=9+16=25=5^2$. There exists exactly one Pythagorean triplet for which $a+b+c=1000$. Find the product $abc$.

Python Solution

import time
 
def prod_triplet_w_sum(n):
    for i in range(1,n,1):
        for j in range(1,n-i,1):
            k = n-i-j
            if i**2+j**2==k**2:
                return i*j*k
    return 0
 
start = time.time()
product = prod_triplet_w_sum(1000)
elapsed = (time.time() - start)
 
print "found %s in %s seconds" % (product,elapsed)

When executed, this code gives the following result.

found 31875000 in 0.101438999176 seconds

Cython Solution

We take the same approach in Cython, but remove the Python iterators in an attempt to improve performance.

%cython
 
import time
 
cdef prod_triplet_w_sum(unsigned int n):
    cdef unsigned int i,j,k
    i = 1
    while i < n:
        j = 1
        while j < n - i:
            k = n - i - j
            if i**2 + j**2 == k**2:
                return i*j*k
            j += 1
        i += 1
    return 0
 
start = time.time()
product = prod_triplet_w_sum(1000)
elapsed = (time.time() - start)
 
print "found %s in %s seconds" % (product,elapsed)

This gives us the following.

found 31875000 in 0.00186085700989 seconds

Thus, the Cython version is roughly 56 times faster than the Python code.


Comments are closed