post

Reproduce or die

It was about 1975 when I first heard of John Conway’s Game of life, a cellular automaton that is able to mimic aspects of living organisms, such as moving, reproducing and dying. Some school friends who had joined the computer club awoke my curiosity and even though I didn’t know the exact rules at the time, I made up my own version and called it: Reproduce or die 2/4. Let me explain.

John Conway’s version takes place in an infinite 2D checkerboard universe where time goes by in discrete steps. Each square or ‘cell’ in his universe has two possible states, either alive or dead. An initial configuration of living cells is created and the state of any cell at the next time step depends on how many living neighbouring cells it has at the current moment. Conway included all eight neighbouring cells surrounding the one being considered (see the green cell in the figure below), called the Moore neighbourhood. There are four cells touching its sides (labelled s in the figure): north, south, east and west and four neighbouring cells touching corners (labelled c) with the cell in question: NE, NW, SE and SW. If a cell has just two living neighbours, it will stay alive or stay dead. If it has three living neighbours, it will stay alive or come alive. Any other total and it will die or stay dead. For more about Conway’s version, check out this link.

Neighbouring cells.

In my checkerboard 2D universe, I only consider the 4 side cells that surround a living cell, i.e. the ones north, south, east and west (the cells marked ‘s’ above), known as the Von Neumann neighbourhood. I ignore the corner cells (marked ‘c’). The rules are simple:

  • If a living cell has exactly two living side neighbours in the present time step (or generation as I call it), then two new daughter cells are born into the two empty side cells (i.e. they come alive) and the parent stays alive in the next generation.
  • Every other cell dies or stays dead in the next generation.

As the only cells that survive are ones that have two out of four possible living neighbours and they also reproduce (all others dying), I call my version Reproduce or Die 2/4. At first I worked out the new generations by hand on graph paper, but when home computers became a reality in the early 1980’s, I wrote my own programs.

Applying the rules

Consider three living cells in a row (below left, shown in green) in the first generation. The end ones have only one neighbour each so they will die. The middle cell has two neighbours so will live and at the same time will produce two offspring, one in each of the empty neighbours cells (marked ‘0’), one above and one below (see middle figure below). A new shape is created, which is also a line of three living cells but this time vertical. In the next generation, only the middle cell will survive and will create two daughter cells, one to the left and one to the right. The ‘organism’ returns to its original shape (below right) and then repeats the cycle continuously. It is an oscillator of period 2. I call it the rod.

The evolution of the ‘rod’, from left to right.

Consider now a set of three living cells that make a small corner (below left). The end cells each have only one neighbour (the corner cell itself) so will die, but the middle cell that makes the corner has two neighbours so will live and give birth to two daughter cells, one in each of the two unoccupied side cells. The new shape is still a corner, but pointing the other way. In the next generation, the end cells will die and the middle cell will reproduce offspring into the two empty side cells and voila, we get the same starting shape again. This too is an oscillator of period two. I call this shape the corner. Every birth that is possible in this universe is built up of just these two: the rod and the corner.

The evolution of the ‘corner’, from left to right.

For simplicity, the chosen universe for the remainder of this article has a finite size (20×20 cells) but has periodic boundary conditions, like some video games. This means that the top of the spreadsheet is connected to the bottom and the right side is connected to the left side, so the universe is like the surface of a torus. Let us now see what kind of creatures can inhabit this cosmic doughnut when we start combining more than three living cells next to each other.

Shakers and movers

Five oscillators of period two. Clockwise from top: corner, rod, H, and the small and large butterflies. The grid on the right shows the second generation of each oscillator.

The Reproduce or die 2/4 universe cannot be static, due to the chosen rules and in its simplest state it has to at least oscillate, so let us have a look at a few of the ‘shakers’ that live here. Five oscillators are shown above.

The ‘corner’ and ‘rod’ have already been introduced. Each has a period of two and both are among the most common shapes to turn up in random initial conditions i.e. those where the initial state of each cell is chosen at random. The H also has a period of two. The ‘large and small butterflies’ shown above also have periods of two and seem quite rare, but have appeared as end products of a symmetric explosion (see later).

A good game of life would be boring if it didn’t have any mobile creatures, so fortunately this universe has a fair share of travelling folk. Four examples are shown below. In this case all move north:

Gliders that move north. Four time-steps are shown, going clockwise from top left. The gliders are called (clockwise from bottom left in the first time-step) the small C, the hat, the short leg, and the leg1.2.3.2.

The first glider (bottom left) I call the small C. It evolves over three generations before returning to its original shape, but it has moved one cell north during this period. It thus has a speed 1/3 that of light and a period of 3. (Note: speed of light is the name given to the maximum possible speed, which in this universe is one cell per time interval). The small C is very different to all the other gliders so far discovered, as will become clear. The next glider (above the C), I call the hat. It keeps the same shape every generation (so has a period of one) and moves at the speed of light: one cell per time step. It is the most common glider in this version of the Game of Life. The top right shape in, I call the short leg, which is like the hat but with one short limb. It has a period of two and moves at the speed of light. The final example (bottom right shape) is the leg1.2.3.2. This one has a period of 4 before it returns to its initial shape and like almost every glider it moves at the speed of light.

As with John Conway’s Game of Life, this version also has shapes that create strings of gliders (guns as they are called), plus there are many interesting collisions involving moving shapes, but time and space are limited so let us move onto one of the more spectacular performances in the presentation.

The big bang

There is a category of simple regular shapes that grow like an explosion and maintain their symmetry through each ensuing generation. I call the simplest one, starting with a 2×2 array of living cells, the ‘big bang’. A selection of stages of this explosion is shown below. Each generation might make a unique repeating floor tile, or possibly, one of the most challenging crosswords layouts ever!

The big bang on the 1st, 11th, 21st, 41st, 81st and 136th generation.

In an infinite universe, all such shapes would grow indefinitely, but as it is finite here, the advancing ‘shock waves’ of the exploding shapes meet each other at the edges and then interfere. The big bang eventually settles down to a simple oscillating pattern of 12 corners on the 136th generation, much like the formation of the galaxies (or stars) in our own universe. All other symmetrical patterns settle down, but some with a long dance, needing up to seven generations in the end repeating cycle.

A random field

A random initial field.

A random field is one where the initial state of the cells, alive or dead is decided by a probability rating $p$, e.g. $p = 0.5$ would mean the chance of a cell starting alive would be 50%, hence about 50% of the cells would be alive using a random number function at the start. Most random, asymmetric shapes produce what seem to be permanent disorder that expands and fills the space and looks like it never wants to settle down. As this particular universe is finite in size, then there are a finite number of possible states, so in fact all configurations will repeat, even if they take a long time. To the right is a typical example of such a random population many generations after its creation. In this example one can see, top right, an oscillating corner, while near the centre is a hat glider, moving downwards. Neither shape will survive more than a generation or two, but this is how precarious life is in this universe.

Conclusion

The Reproduce or die 2/4 variation does have its moments of oscillators, gliders, guns, collisions and explosions, with some amazing kaleidoscopic patterns to delight the eyes. The downside is that there are far too many uncontrolled population growths that swamp and destroy the more interesting order. Life in such volatile fields is short-lived and fleeting, much like the real universe. Perhaps that is what makes this kind of life so precious.

Whatever next?!

In Reproduce or die 2/4, there are a few questions I would like to ask:

  • How would changing the finite size of the universe change the outcomes? I used a 20×20 universe, but I’d expect it to be different for, say a 30×30. Readers will have a chance to try this out!
  • In a random field, is there a pattern to the population density?
  • What is the frequency of appearance of stable shapes, like the hat, corner and rod?
  • What would happen if the Reproduce or die 2/4 rules were modified slightly? For example when two cells are trying to be born into the same square, what if they cancelled out and it remained empty? That might dampen down those unwanted exponential explosions.

I asked one of my physics students, Dmitry Mikhailov, to create the Reproduce or Die world so readers could play with it themselves. He kindly took up the challenge and has made an interactive version here. All images in this article are also thanks to his program and Dmitry’s contribution is much appreciated.

Please share your discoveries of any interesting news shapes. Remember, stable shapes are hard to find as most situations end in disarray, so don’t be put off (unless you like entropy!). Finally, why not consider trying to create your own set of rules and you can then be the god (or goddess) of your own universe!

post

How do calculators do trigonometry?

How your calculator DOESN’T do it

The easiest and least accurate way to calculate sine and cosine for an angle is to measure a physical object. Want to know $\sin(40^\circ)$? Then get out your protractor, draw a right-angled triangle with a $40^\circ$ angle, and divide the measured length of the opposite side by the hypotenuse.

Finding $\sin(40^\circ) \approx$ 6cm/10cm through measurement

During the all-too-brief reign of the analogue calculator, you could effectively do this electro-mechanically by measuring the induction in a coil of wire angled $40^\circ$ out of phase with another coil — but unless your calculator was salvaged from the navigation computer of a 50s Boeing bomber aircraft, this is not how your calculator does it. Nor does your calculator consult tables of values painstakingly hand-derived from the angle addition and half-angle trigonometric identities, as was the norm for mathematicians, scientists, and engineers until the mid-century.

If you’re like me, you assumed that modern calculators approximate sine and cosine with polynomial functions using techniques from calculus and analysis. (If you’re very like me, you told a high school student this in your first year of teaching, struggling to make the key ideas of Taylor series accessible without referencing calculus.) However, these algebraic approximations prove slow to converge. A sophisticated computer can take a shortcut by storing the old immense tables in memory and then Chebyshev-approximating to get the last few digits of accuracy. But what about your pocket or scientific calculator, or, for that matter, your TI graphing calculator — where adding that architecture would be an expensive hassle?

A weirdly capitalised acronym

Enter CORDIC, the COordinate Rotation DIgital Computer — an algorithm designed by Convair’s Jack Volder to exploit the strengths of the then-emerging digital computers to their fullest.

The idea that Volder laid out in “Binary Computation Algorithms for Coordinate Rotation and Function Generation” is simple: Program the computer to be able to perform a set of progressively smaller rotations, which it can then apply on one of the points of a known right-angled triangle—say, the $45^\circ-45^\circ-90^\circ$ isosceles right triangle with hypotenuse $1$—until it reaches the angle, and thus the measurements, of desired triangle.

Rotating a vertex to find $\sin(75^\circ) \approx 0.97\ldots/1$.

By itself, this eliminates the need to store an immense table—roughly speaking, each new smaller rotation refines the result to an additional binary digit of accuracy, and all that needs to be stored are the instructions for rotating by that angle. Indeed, similar methods were used for those hand-generated tables: the method described so far is a geometric perspective on using the angle-sum trigonometric identities. Volder’s algorithm, however, doesn’t stop there. It adds in two crucial details that computers just adore:

  • Don’t choose your set of rotations by progressively halving the angle—choose them by halving their tangents: $\tan(45^\circ)=1$, $\tan(26.56\ldots^\circ)=\frac{1}{2}$, $\tan(14.03\ldots^\circ)=\frac{1}{4}$…
  • Instead of performing a true rotation, attach the side of a right triangle with the desired angle to the old hypotenuse, creating what Richard Parris calls a fan

Building a fan to approximate a $40^\circ$- angle.

Both of these refinements to the scheme would seem to make our lives more difficult; after all, we lose both the nice rational angles and the hypotenuse that stays obligingly fixed at length 1. We shall see, however, that the actual computations are more straightforward, and are even simpler in binary arithmetic. If you are particularly fond of transformation matrices, you can pause your reading right now to work out why this is on your own (or read it in Richard Parris’ excellent “Elementary Functions and Calculators“)—but if you’d like to see a more purely geometric explanation, read on!

CORDIC: A geometric justification

Let’s look at a simple example of these rules in action. Say we have a right-angled triangle with sides of length $a$, $b$, and $c$, following well-trod convention. Let $c$ be the hypotenuse, and let side $a$ be adjacent to an angle $\theta$:

A right-angled triangle.

We then attach to the hypotenuse a triangle with a tangent ratio of $\frac{1}{2}$—that is, such that the side opposite the angle $\varphi$ is half the length of the side next to it. This opposite side, then, has length $\frac{c}{2}$:

Attaching a triangle with a tangent ratio of $\frac{1}{2}$.

And what of the triangle we want—a right-angled triangle with angle $\theta+\varphi$? Consider a vertical drawn from the opposite angle of the new triangle, perpendicular to side $a$, and a horizontal from the opposite angle of the original triangle perpendicular to side $b$:

A triangle with angle $\theta + \varphi$.

We then have the marked congruent angles—so the right triangle created by the intersection of the vertical and the horizontal is similar to the original triangle, and indeed is simply a triangle half the size, rotated by $90^\circ$! Thus, the dimensions of a right triangle with angle $\theta+\varphi$ can be $a-\frac{b}{2}$ on the adjacent side, and $b+\frac{a}{2}$ on the opposite side:

The side-lengths of the triangle with angle $\theta + \varphi$.

Similarly, we find sides of $a+\frac{b}{2}$ and $b-\frac{a}{2}$ for the triangle with angle $\theta-\varphi$, and would find $b+\frac{a}{2^n}$ and $a-\frac{b}{2^n}$ if we had sought $\varphi$ with a tangent halved n times. The change in the side lengths will always be given by that little triangle, which — as its sides are constructed parallel to those of the original triangle — will always be similar to the original triangle, with its scale determined by the tangent ratio of the new triangle in the fan.

What your calculator (maybe) does

To build out the fan and track the coordinates of the point, we only need to repeat this little divide-and-add process until we get close enough to the desired angle. For a binary computer, this is easy. Dividing by two is a simple matter of moving the decimal over by one place; dividing by $2^n$, moving the decimal point over by $n$ places. Many simpler calculators use binary-coded decimal instead of pure binary—storing each digit of a decimal number individually in binary representation—which adds some wrinkles, but follows fundamentally the same principle. All that remains is addition.

For calculation of the sine and cosine ratios, we need only one further piece of information: the length of the hypotenuse. Here the “fan” is helpful, especially if we make one further proviso—we never leave an angle, or triangle, out. Then the component triangles of the fan are fixed, and in return for losing a bit of speed in narrowing in on the correct angle, we can have the computer memorise the length of the hypotenuse of the final, thinnest triangle in the fan—that same line will be the hypotenuse of the desired triangle!

Let us walk through this process, in binary, with the example a four-step fan for $40^\circ$ illustrated above. We start with an isosceles right triangle with legs of length 1. This gives us our initial coordinates $\left(x_0,y_0\right)$ of $\left(1,1\right)$. We then subtract the the half-tangent right triangle, about $26^\circ$ (below, a subscript “$d$” indicates the number is in base-10):
\[x_1 = x_0+\frac{y_0}{2_d^{1_d}} = 1+\frac{1}{2_d} = 1+0.1=1.1\]
\[y_1 = y_0-\frac{x_0}{2_d^{1_d}} = 1-\frac{1}{2_d} = 1-0.1 = 0.1\]
Then we add the quarter-tangent triangle, about $14^\circ$:
\[x_2 = x_1-\frac{y_1}{2_d^{2_d}} =1.1-\frac{0.1}{4_d}= 1.1-0.001=1.011\]
\[y_2 = y_1+\frac{x_1}{2_d^{2_d}} =0.1+\frac{1.1}{4_d} = 0.1+0.011 = 0.111\]
And finally, we add the eighth-tangent triangle, or about $7^\circ$, to arrive at an angle of $39.6^\circ$:
\[x_3 = x_2-\frac{y_2}{2_d^{3_d}} =1.011-\frac{0.111}{8_d}= 1.011-0.000111=1.010001\]
\[y_3 = y_2+\frac{x_2}{2_d^{3_d}} =0.111+\frac{1.011}{8_d} = 0.111+0.001011 = 1.000011\]
Transitioning back into decimal, this gives us an $x$-coordinate of about 1.27 and a $y$-coordinate of about 1.047. Repeated application of the Pythagorean theorem, meanwhile, tells us that the length of the hypotenuse of the eighth-tangent triangle—shared by the hypotenuse of the combined $39.6^\circ$ triangle—is about 1.64. So, $\sin(40^\circ)\approx \frac{1.047}{1.64} = 0.638$. This is pretty close to the actual three-place value of 0.643—but it should be noted that $40^\circ$ is one of the more convenient angles to reach in this fashion. A more usual implementation of CORDIC would be set to halve the tangent twenty or thirty times to ensure accuracy past five decimal places.

So, we can calculate since and cosine with only one computationally costly task: dividing by a set number at the end. Those computational costs, though, have been decreasing, and CORDIC’s clever algorithmic thriftiness has begun to fall from favour. Intel’s CPUs haven’t used CORDIC since the days of the 486, and even some modern graphing calculators have dropped the method in favour of the polynomial approach. But even though CORDIC may someday cease to be a tool people use themselves, its incredible simplicity, cheap implementation, and proven accuracy will keep it in use in dedicated processors and purpose-built machines for as long as speciality electronics needs to know how to measure triangles.

An exercise for the reader

As the hyperbolic trigonometric functions share many basic properties with their circle-trigonometric counterparts, it may come as little surprise that CORDIC can also evaluate $\sinh$, $\cosh$, $\tanh$, and the rest of the hyperbolic ratios — though values on hyperbola can shift fast enough to leave ‘gaps’ that hyperbolic-tangent–halving alone can’t reach. Curiously, though, the fact that $\cosh(x)+\sinh(x)=e^x$ means that the basic CORDIC method can even be adapted to evaluate exponents and logarithms. If you can describe a geometric justification for the hyperbolic, exponential, or logarithmic variants like the circular case above, please let me know — I’m tired of looking at matrices.

post

Counting all the numbers between zero and one

Heavy as the setting sun
Oh, I’m counting all the numbers
between zero and one
Happy, but a little lost
Well, I don’t know what I don’t know
so I’ll kick my shoes off and run

Sir Sly, &Run

There’s a song popular on the radio right now (‘&Run’ by Sir Sly) that contains the lyric, “I’m counting all the numbers between zero and one.” The first time I heard it, I thought, that’s not going to take very long. I assumed the singer was referring to integers, of which there are none strictly between zero and one. Was he trying to tell the woman he was singing to that he was impatient to see her again? Or suggesting that they were as close as two adjacent integers, with literally nothing keeping them apart?

The second time I heard the song, though, it occurred to me that he might be referring to the real numbers, of which there are an infinite number between zero and one. Counting those would keep him busy for, well, ever. Was he expressing his (infinite) patience? Or was he in despair at an impossible task? It all depends on what Sir Sly means by ‘numbers.’ (Also ‘counting’, and even ‘between’.) Continue reading

post

Unknown pleasures: pulsars and the first data revolution

Many of the 20th century’s most famous albums are as celebrated for their artwork as they are for their music. This is particularly true of albums from the 1970’s: think of Bowie’s Aladdin Sane,  Fleetwood Mac’s Rumours, or Pink Floyd’s Dark side of the moon. The 1970’s were a golden era for concept albums in popular music, meaning that the world’s biggest artists spent a lot of time and money producing beautiful covers to fit the sound and message of the songs within.

A recurring theme in artistic images from that decade is space. In the age of the moon landing, when much of technological development was focused on pushing the human frontier, cosmic images were everywhere in popular culture. The original Star Trek series was first broadcast in 1966, the first Star Wars film was released in 1977, and E.T. followed five years later. Similarly, Parliament’s Mothership connection (1975) and Supertramp’s Crime of the century (1974) both feature space-inspired covers. With space comes science, so it’s no surprise that many of the most famous album covers have an interesting scientific tale to tell.

One spacey image with a particularly rich backstory comes from Joy Division’s 1979 debut, Unknown pleasures. The cover of the album features an array of wavy, organic-looking lines on a black background, with no information suggesting where they might come from. (Neither the title of the album nor the name of the artist appears on the front cover.) In fact the image is a ‘stacked plot’ depicting radiation emitted by a pulsar, a type of star that had been discovered 12 years earlier, and gives a glimpse into the transformative effect that early computers had on scientific research.

The cover of Unknown pleasures.

Continue reading

post

Talkdust, episode 4

It’s time for episode four of Talkdust!

You can listen to the podcast using the player below, or download an mp3, or search for us in your in favourite podcast app (or add us to your app manually using the RSS feed).

The presenters of this episode of Talkdust are Sean Jamshidi and Eleanor Doman. Music and editing by Matthew Scroggs, and announcements by Tom Rivlin. In this episode:

  • Eleanor and Sean talk about the launch of issue 09.
  • Stephen Muirhead tells us about his article in issue 09.
  • Eleanor and Sean talk some more about the launch of issue 09.
  • Eleanor and Sean play a game in which they try to describe mathematical words to each other and take the second place position on the leaderboard.
post

Issue 09

Our latest edition, Issue 09, is available now. Enjoy the articles online or scroll down to view the magazine as a PDF.

Features

Fun

Printed versions

or

Download Issue 09 as a PDF

post

When Truchet met Chladni

While catching up on past issues of Chalkdust over the Christmas break, I was intrigued to see that issue 07 featured an article on Chladni figures (On the cover: Chladni figures of a square drum by James Cann), followed in issue 08 by an article on Truchet tiles (Too good to be Truchet by Colin Beveridge). This coincidence fascinated me because, although not the focus of the articles, there is a remarkable conjecture that links these two apparently unrelated objects, via the mathematics of percolation theory. Continue reading

post

Playing billiards with cue-bics

Icy patches sit in wait and bare trees shiver in anticipation but spring is still dawdling, likely enjoying a final cuppa before going back to work. What are we to do while days are dreary and the wind rummages through empty branches? Why, stay inside and play with geometry software, of course! Yet winter was long and snowy, and after one too many hours indoors the treasure trove of maths is perhaps running low.

What to do once ancient theorems are re-proved and the excitement of a parametric plot has wilted? Well, there is still a nugget of algebra that could flourish into hours of exploratory fun. So grab your Geometer’s Sketchpads, your Geogebra, or simply some transparencies and coloured markers, and let’s play billiards with polynomials. Continue reading