# Unkown Blogger Pursues a Deranged Quest for Normalcy

• ## Blog Stats

• 10,700 hits

## Euclid and the Golden Ratio

Posted by ubpdqn on March 20, 2011

I have been motivated by browsing through many blogs (esp. John D Cook’s bl0g).

The Euclidean algorithm is related to continued fractions.  Consider two integers $a >b$. The Euclidean algorithm can be summarised as follows:

$\begin{array}{lll} \frac{a}{b}&=&q_0 +\frac{r_0}{b}\\ \frac{b}{r_0}&=&q_1 +\frac{r_1}{r_0}\\&\vdots& \\\frac{r_{j-1}}{r_j}&=&q_{j+1} +\frac{r_{j+1}}{r_j}\\&\vdots&\\ \frac{r_{N-2}}{r_{N-1}}&=&q_N\end{array}$

The continued fraction representation of this ratio follows:

$\frac{a}{b}=q_0 +\cfrac{1}{q_1+\cfrac{1}{q_2+\cfrac{1}{\ldots+\cfrac{1}{q_N}}}}$

or using the list notation:

$\frac{a}{b}=[q_0,q_1,\ldots,q_N]$

Using Mathematica to create a list density plot of the length of the Euclidean algortithm for $y/x$ and cycling through the gradient color schemes is the following graphic. The thick red lines are $\frac{y}{x} =\phi$ and $\frac{y}{x} = \frac{1}{\phi}=1-\phi$ where  $\phi$ is the Golden Ratio.

The relevance of these lines is that the represent the boundary (worst case) for Euclidean algorithm length (number of steps).

I liked the gradient schemes “CherryTones” and “SunsetColors” of the 51 available.

For an irrational perspective see Pi and Phi.