Tutorials‎ > ‎

### Week 5: Arnold's Cat Map

You may have heard of Schrödinger's cat ... but have you met Arnold's cat?

Arnold's cat map is named after the mathematician Vladimir Arnold, who demonstrated the effect of repeatedly applying a linear transformation to an image of a cat like this one:

Click on the image above to see an animation of the Cat Map. Watch as the cat is "scrambled", and then, magically, reappears! Just like the Cheshire cat from Alice in Wonderland.

## Introduction

Last week we saw how to display images using the `pygame` package. We learnt how to manipulate the pixels ("picture elements") that make up the image. This week, we will put our knowledge to use, to make an animation of Arnold's cat map. Along the way we will learn a little about modular arithmetic and the Pisano periods of the Fibonacci sequence.

We will be using a slight modification of Arnold's original algorithm, that uses the Fibonacci sequence, which we learnt about in Week 1.  For this reason, I'm going to call it the Fibonacci Feline map.

## The Fibonacci Feline

Before we can start writing a code, we need to understand a little more about how Arnold's cat map actually works. In essence, Arnold's map is a rule for moving pixels around in a square, in such a way that we don't lose information. Let's consider a square of side length N, where the position of each pixel is given by an x coordinate and a y coordinate. The x and y coordinates are integers in the range 0, 1, ..., N-1. The map is simply a rule to tell us how to change the coordinates of each point, at each step. We can use any map that it is reversible (i.e. does not attempt to map two pixels to the same position) and periodic. We will use a map based on the Fibonacci sequence.

### Fibonacci Sequence

Remember the Fibonacci sequence, 0, 1, 1, 2, 3, 5, 8, 13, 21, etc? It was generated with a simple recurrence relation, Y(n+1) = Y(n) + Y(n-1), starting from two seed values, Y(0) = 0, Y(1) = 1.

To get the next Fibonacci number, we add together the previous two. So to take a step forward, we need to know (at least) the two previous numbers. Let's define a new variable, X(n+1) = Y(n). Then the recurrence relation can be rewritten like this:

• X(n+1) =             Y(n)
• Y(n+1) = X(n) + Y(n)
What's the point of writing the recurrence relation in this way? Well, now we have two numbers, X and Y, which in a moment we will think of as the x and y coordinates of a pixel. And we have a rule for iterating (i.e. moving them around). But first, we need to talk about:

### Modular Arithmetic

Each Fibonacci number is bigger than the last. The numbers in the sequence just keep on increasing, and there's no upper limit. To use the numbers in the Fibonacci sequence as coordinates for pixels in an image, we need to find a way to restrict them to a fixed range.

We have already met such a way: we may take a remainder. In Python, the remainder of k when divided by N is found with `k % N`.  This gives us a number in the range 0 to N - 1

In maths, "taking the remainder" is the key operation in modular arithmetic (also called clock arithmetic), which is a system of arithmetic for integers, in which numbers "wrap around" upon reaching a certain value N. Here N is called the modulus, and the remainder of k when divided by N is called "k modulo N" and is written as k (mod N). A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. On a 12-hour clock, 1pm on Tuesday appears exactly the same as 1am on a Friday. Time "wraps around" on the clock, and the hour of day is always in the range 1 to 12. ### Pisano Periods

Let's think about the Fibonacci numbers modulo N (in other words, the remainders of the Fibonacci numbers when divided by N). Here is some Python code for generating a sequence modulo N=8:

`nmax = 36`
`Fib = [0,1]`
`for k in range(2, nmax):    `
`    Fib.append(Fib[-1] + Fib[-2])`
`N = 8`
`FibmodN = [F % N for F in Fib]`
`print FibmodN`

This code should generate a sequence like this:

0,1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,3,5,0,5,5,2,7,1, ...

Look carefully at the sequence. Do you see the pattern?

The sequence repeats itself - did you spot this? The sequence above is generated from a repeated block of length 12, i.e.

0,1,1,2,3,5,0,5,5,2,7,1,      0,1,1,2,3,5,0,5,5,2,7,1,      0,1,1,2,3,5,0,5,5,2,7,1,     etc.

Now try changing N to another number (e.g. N=7).  Can you find the new repeating pattern? How long is it?

Repeating patterns in the Fibonacci sequence modulo N were first spotted by Lagrange in 1774. The Nth Pisano period, written π(N), is the period with which the sequence of Fibonacci numbers, modulo N repeats. So the 8th Pisano period is 12. Pisano periods of other N are given in this long list.

### The Map

The Fibonacci sequence modulo N gives us a rule for moving the (x,y) coordinates of single pixel. For example, modulo N=8, the pairs of (x,y) values in the Fibonacci sequence are

(0,1) -> (1,1) -> (1,2) -> (2,3) -> (3,5) -> (5,0) -> (0,5) -> (5,5) -> (5,2) -> (2,7) -> (7,1) -> (1,0) -> (0,1)

In fact, we can start with any two seed values (X0, Y0) and we will get a sequence whose length is the Pisano period. For example, try changing the initial values using `Fib = [6,7]` in the code above, to generate

(6,7) -> (7,5) -> (5,4) -> (4,1) -> (1,5) -> (5,6) -> (6,3) -> (3,1) -> (1,4) -> (4,5) -> (5,1) -> (1,6) -> (6,7)

There are 5 such sequences for N=8, each of length 12, so this gives us a rule for moving all 64 pixels in the 8 x 8 square.

## The Program

### The Algorithm

We want to write a program which does the following:
1. Load a square image, of side length N.
2. Display the image.
3. Move the pixels using the rule below
4. Display the scrambled image
5. Repeat from step 3.

Here is the rule:

xk+1 = yk % N

yk+1 = (xk + yk) % N

where % indicates the "remainder" operation. Here (xk, yk) are the coordinates of a pixel at the kth step, and (xk+1, yk+1) are the new coordinates.

If you are feeling confident, you may now want to write a Python program yourself, to implement the Fibonacci Feline map. Or you may wish to look at:

### Example Code

Attached below is a Python program, `catmap.py`, which implements the Fibonacci Feline map. Download it and give it a go! You should save `cat.jpg` image in the same directory as `catmap.py`.

Much of the code is similar to last week's code for the animated sieve. For example, we load an image, retrieve a (`numpy`) array of pixels, manipulate the pixels, and display on screen. However, there are some new ideas. I needed to copy an array, so that I could move the pixels around without overwriting them. To do this I used the copy package, with code like this:

`import copynew_array = copy.copy(old_array) `

I also rescaled the displayed image to be twice as big as the original image, using:

`pygame.transform.scale2x(mysurf, screen)`

### Exercises

1. Use the alternative image of the Raspberry Pi logo, attached below.  It's a different size. How does this affect the time it takes for the original image to reappear?
2. Try using an image of your own (first you should make sure it is a square).
3. Write a Python code to compute the Pisano periods for N up to 2013. Check your results against this list.
4. Can you come up with a new rule for moving the pixels around? Does the image still reappear eventually? Or is it lost forever?
5. Advanced: Save each frame of the Fibonacci Feline animation as an image, and then combine the images into an animated gif.
ą
cat.jpg
(5k)
Sam Dolan,
28 Apr 2013, 23:40
ċ
Sam Dolan,
28 Apr 2013, 23:47
ą
Sam Dolan,
28 Apr 2013, 23:42