Exercises¶

Exercise 1: Cythonization¶

Study the provided fractal.py for computing the Newton fractal. Determine (by timing, profiling, or just guessing) which part is the bottleneck and decide which part is worthwhile to convert to Cython. Do the conversion and add necessary type declarations etc.

How large a speedup do you get?

Exercise 2: Wrapping C¶

Part 1

In directory wrapping is a simple C library computing the sin elementwise for a Numpy array. The header stuff.h defines a function with the signature:

void compute(int n, double *input, double *output)

which takes two C arrays of doubles containing n doubles.

Write a Cython wrapper:

def do_compute(input_array):
    ...
    return output_array

for this function.

You can address the double* data contained in a Numpy array via the .data attribute of the corresponding cdef-ed variable. (Remember to check .flags.c_contiguous!)

Part 2 (only do at the end if you have time)

In the directory wrapping2 is an old library written in C that generates anagrams from words. Write a Cython wrapper for it; this requires some string and resource handling.

The only thing you need to know about the C library is that its interface consists of two C functions:

char* simple_anagram(char *dictfile, char *word, int index)
void simple_anagram_free(char *data)

Usage is as follows:

1. Call simple_anagram with the name of a dictionary file, a word you want to generate anagrams for, and the number of the anagram you want to generate (starts with 0).
2. If there is an anagram corresponding to the number, it returns a C string containing the anagram. Otherwise, you get NULL.
3. You will need to free the returned C string by calling simple_anagram_free on it.

Exercise 3: Conway’s Game of Life¶

The Game of Life is a well-known cellular automaton, whose behavior is interesting in many ways. It is defined on a grid of cells, where each cell has 8 neighbors:

.........
.........
...ooo...
...oxo...
...ooo...
.........
.........

The update rule to get a new state from the old one is:

• Cells with with less than 2 or more than 3 live neighbors die.
• Cell with exactly 3 live neighbors becomes alive.

Write a Cython function life_update(old_state, new_state) that takes an N x N Numpy array old_state of type int8 containing the old state, and writes the new state to a similar array new_state. Just use four nested for-loops, but remember to add type declarations.

Some image file containing well-know interesting shapes are supplied (use matplotlib.pyplot.imread to read them into Numpy arrays). Assign them at the center of a big grid, and see what happens!

• glider.png: the glider
• glider_gun.png: the Gosper glider gun
• breeder.png: one sort of a breeder
• ... and others!

These examples come from the very interesting Game of Life simulator Golly.

import matplotlib.pyplot as plt
import time
from life import life_update # <-- comes from your Cython module

# put some starting image into state_1
state_1 = ...
state_2 = np.zeros_like(state_1)

# Prepare animation
pixel_size = 2

plt.ion()
fig = plt.figure(dpi=50, figsize=(pixel_size * state_1.shape[1]/50.,
                                  pixel_size * state_2.shape[0]/50.))
plt.axes([0, 0, 1, 1])
img = plt.imshow(state_1, interpolation='nearest')
plt.gray()

print "Press Ctrl-C in the terminal to exit..."

# Animate
try:
    while True:
        life_update(state_1, state_2)
        state_1, state_2 = state_2, state_1   # swap buffers
        img.set_data(state_1)
        plt.draw()
        time.sleep(0.01)
except KeyboardInterrupt:
    pass

Exercise 4: On better algorithms...¶

Sometimes, the right solution is to (also) use a better algorithm.

Take the gravity example, and in the time step function interchange the order of position and velocity updates. This transforms the algorithm (Euler method) to a more appropriate one (the symplectic Euler method). Check what happens to the “exploding orbits” problem when the number of time steps is decreased.