Euclid’s algorithm = continued fractions = squares in a rectangle

[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day. – Donald Knuth
euclid 220 over 117

This picture is of squares in a 200×117 rectangle.
It represents:

1. What you would get if you (using just compass and straight edge) drew the biggest square you could in the rectangle (117×117), then again (83×83) in the space left, then simply kept repeating as long as possible. No calculation needed! Clearly there are 1, 1, 2, 2, 3, 1, 3 of each size square.

2. What you get if you turn 117/200 into a continued fraction. i.e.

    \begin{align*} \frac{117}{200}\quad&=\quad\cfrac{1}{\frac{200}{117}}\quad=\quad\cfrac{1}{1+\frac{83}{117}} \quad=\quad\cfrac{1}{1+\cfrac{1}{\frac{117}{83}}} \quad = \quad \cfrac{1}{1+\cfrac{1}{1+\frac{34}{83}}}\\ &=\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2+\frac{15}{34}}}} \quad = \quad \cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{2+\frac{4}{15}}}}}\\ &=\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{3+\frac{3}{4}}}}}} \quad = \quad \cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{1+\frac{1}{3}}}}}}}\\ \end{align*}

3. What you get if you apply Euclid’s algorithm to 200 and 117.

i.e. 200/117 = 1 with 83 remainder.
117/83 = 1 with 34 remainder.
83/34 = 2 with 15 remainder.
34/15 = 2 with 4 remainder.
15/4 = 3 with 3 remainder.
4/3 = 1 with 1 remainder.
3/1 = 3 with 0 remainder.

200/117 ‘just happens’ to = 1000/585, which is derived from to 1585/1000, the decimal value of log 3/log 2 rounded to 3 places. It is a number involved in constructing musical notes/scales/tunings – see Why 12 notes in an octave?

1000/585 may seem a very different number from 1585/1000.. but if I had used that as the big rectangle, first step would be to draw a 1000×1000 square..
and then I’m left with 1000/585 in the next step of Euclid’s algorithm. And everything after is exactly the same.

Leave a Reply

Your email address will not be published.