Ancient Greek mathematician, Euclid not only developed the rigorous way of doing proof that we use today to check software is correct, he also developed algorithms for drawing shapes. His most famous algorithm called ‘Euclid’s algorithm” is important in cryptography.

Rigorous Proof

Ancient Greek mathematician, Euclid, is most famous for the way he developed an important foundation of mathematics in his set of books, Elements. He set about proving theorems (ie facts guaranteed by logic) about geometry. Most of the theorems were actually already known. The really special thing about it was the really rigorous way he did it. In particular, he allowed himself to use only a small set of initial ‘facts’ or axioms. He built new theorems using only logical reasoning applied to these axioms and theorems he had already proved.

It is this framework of rigorous proof that is his most notable achievement. It is the way maths is done today. It is also the basis of how we verify that safety critical software and hardware is correct. Without this approach code would be much more buggy … and more dangerous. Whereas he used initial facts about geometry, we base proofs about code on the semantics (the mathematical meaning) of what the language constructs do.

Drawing Shapes

Euclid was interested in geometry, so two of his axioms boil down to the starting facts that you can draw a straight line between two points with a straight edge (a ruler but without distances marked on it), and you can draw a circle from a central point with a compass. Modern computer-aided design programs, used to design pretty well everything now a days have the rules of euclidean geometry built in to them. It also is used in computer graphics and ensuring 3D virtual worlds work the way the real world appears to us.

Whilst he was doing maths, he was also writing out algorithms. To prove things existed he wrote out algorithms that created them. Mathematicians call this ‘constructive mathematics’. To a computer scientist it is just what we do: inventing useful algorithms. Once you have an algorithm, others can use them to create the same things for themselves.

For example, one of Euclid’s proofs is that given any line (between points A and B) an equilateral triangle exists with the line as one of it’s sides. How do you prove this? Well if you can give an algorithm that does it then it must be true… so here goes.

An algorithm to draw an equilateral triangle

To draw an equilateral triangle with base the line A – B:

1. Draw a Line, marking the ends A and B.
2. Draw a circle centred on A with radius AB:
   1. Place a compass point at one end of the line (point A).
   2. Place the pencil point of the compass on the other end of the line (point B).
   3. Draw a circle.
3. Draw a circle centred on B with radius AB:
   1. Place the compass point at point B.
   2. Place the pencil point of the compass at point A.
   3. Draw a circle.
4. Make a new point, C, where the two circles meet.
5. Draw a straight line from A to C.
6. Draw a straight line from B to C.

You have drawn an equilateral triangle.

Invent your own algorithm

Can you invent an algorithm, just using a pencil, compass and ruler to create a regular  hexagon in a similar way? Have a go before reading on.

An algorithm to draw a regular hexagon

Here is Euclid’s algorithm…

To draw a regular hexagon centred on a point A:

1. Draw a circle centred on A
2. Draw a line through A cutting the circle in both directions (giving new points B, C).
3. Draw a circle centred on C with radius AC and make new points, D and F, where the two circles meet.
4. Draw a straight line from D, through A crossing the circle to make a new point E.
5. Draw a straight line from F, through A crossing the circle to make a new point G.
6. Draw lines joining adjacent points round the original circle: C-D-G-B-E-F-C.

You have drawn a regular hexagon.

A more artistic algorithm to draw a regular hexagon (and a flower)

Of course Euclid was only interested in maths but maths and art go hand in hand especially when symmetry is involved. A slightly different algorithm for drawing a hexagon gives a rather beautiful geometric flower pattern if you keep the working lines.

To draw a regular hexagon containing a flower:

1. Draw a circle centred on A
2. Pick a point B on the circumference and draw a circle of the same size centred on B.
3. Draw a third circle centred on the point where the second circle crosses the original circle.
4. Draw a fourth circle centred on the point where the third circle crosses the original circle.
5. Draw a fifth circle centred on the point where the fourth circle crosses the original circle.
6. Draw a sixth circle centred on the point where the fifth circle crosses the original circle.
7. Draw a seventh circle centred on the point where the sixth circle crosses the original circle.
8. Draw lines joining adjacent points round the original circle.

Create your own version, symmetrically colouring in each separate area different colours.

This is the seed of the idea behind the highly geometric patterns of Islamic geometric art – that geometry can be artistic as well as mathematical. Can you create your own pattern based around constructing several hexagons?

Drawing a right-angled triangle

We’ve seen how to draw an equilateral triangle. Can you now work out an algorithm to draw a right angled triangle using only a compass and straight edge.

• An algorithm for constructing a right-angled triangle

Drawing a square

Can you draw a square with only a straight edge and a compass? Have a go at working out your own algorithm before you look at ours. Find out too how something called decomposition helps.

• An algorithm for constructing a perfect square

 

More to follow

---

Ancient Greek Computer Science

Computer Science and History

---

This work was supported by the Institute of Coding, which is supported by the Office for Students (OfS).