Faster Image Transforms With Cython

Python to Cython

This is the second post on how to accelerate Python with Cython. The previous post used Cython to declare static C data types in Python, to speed up the runtime of a prime number generator. In this post we shall be modifying a more complex program, one that performs an image transform on a map. This will allow me to demonstrate some more advanced Cython techniques, such as importing C functions from the C math library, using memory views of Numpy arrays and turning off the Python global interpreter lock (GIL).

As with the previous post, we shall be making a series of Cython modifications to Python code, noting the speed improvement with each step. As we go, we’ll be using the Cython compiler’s annotation feature to see which lines are converted into C at each stage, and which lines are still using Python objects and functions. And as we tune the code to run at increasingly higher speeds, we shall be profiling it to see what’s still holding us up, and where to refocus our attention.

Although I will be using Python 3 on a Mac, the instructions I give will mostly be platform agnostic:  I will assume you have installed Cython on your system (on Windows, Linux or OS/X) and have followed and understood the installation and testing steps in my previous post. This will be essential if you are to follow the steps I outline below. As stated in the previous post, Cython is not for Python beginners.

Continue reading “Faster Image Transforms With Cython”

From Python To Cython

This longer post will show you some of the coding skills you’ll need for turning your existing Python code into the Python-C hybrid we call Cython. In doing so, we’ll be digging into some C static data types, to see how much faster Python code will run, and restructuring some Python code along the way for maximum speed.

With Cython, all the benefits of Python are still yours – easily readable code, fast development cycles, powerful high level commands, maintainability, a suite of web development frameworks, a huge standard library for data science, machine learning, imaging, databases and security, plus easy manipulation of files, documents and strings. You should still use Python for all these things – these are what Python does best. But you should also consider combining them with Cython to speed up the computationally intensive Python functions that needs to be fast. Continue reading “From Python To Cython”

Transverse Mercator With Python

Mercator mapWith global warming melting the icecaps and opening up the poles for oil exploration and tourism, I think it’s time for a new standard wall map, one that shifts those distorted map regions away from major land masses, and places the polar regions where we can see them. That way, our cruise ship and oil tanker captains can navigate more easily through the clear, blue Arctic Ocean, unimpeded by any tiresome ice-pack.

I particularly love that oil companies want to use the new Arctic Ocean sea lanes to transport their oil to market faster. Is it irony, or some form of rare, extinction-level stupidity that only comes around one every few thousand years? Hard to tell. But I digress.

Continue reading “Transverse Mercator With Python”

Eratosthenes 2: Swifter, Further, Cooler

Human & alien hands

 

This post describes the process I used to design an algorithm that allows you to implement a modified Sieve of Eratosthenes to bypass the memory limitations of your computer and, in the process, to find big primes well beyond your 64-bit computer’s supposed numerical limit of 2.0e63 (9.223e18). Beyond that, with this algorithm, the only limitation is the speed of your CPU.

Continue reading “Eratosthenes 2: Swifter, Further, Cooler”

A Faster Sieve of Eratosthenes

SievePic

The Sieve of Eratosthenes is a beautifully elegant way of finding all the prime numbers up to any limit. The goal of this post is to implement the algorithm as efficiently as possible in standard Python 3.5, without resorting to importing any modules, or to running it on faster hardware.

Eratosthenes was a Greek scholar who lived in Alexandria (276BC to 194BC) in the so-called Hellenistic period. He was working about a century after Alexander, and about a century before the Romans arrived to impose their cultural desert and call it peace. And then do nothing with the body of knowledge they discovered. Literally. For over 1,600 years, if you count Constantinople. Not a damn thing.

So much for overly religious, centralised, bureaucratic superstates, obsessed with conquest. But I digress.

Continue reading “A Faster Sieve of Eratosthenes”

Finding Primes Using Complex Numbers

Pythagoras In LegoWith complex numbers, I always feel as if I’m getting a glimpse of something truly awesome that lies hidden within mathematics. The first time I understood how they worked, I thought it was some form of magic.

I get the same feeling with prime numbers. Like many, I’ve looked at them from all angles – prime gaps, large primes, prime densities, prime sieves – and they continue to fascinate. A few months ago I was thumbing through Henry Warren’s programmers cookbook Hacker’s Delight (A) and discovered a whole chapter on the various formulas for (some of) them. Mind-bending stuff.

Continue reading “Finding Primes Using Complex Numbers”