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