Unkown Blogger Pursues a Deranged Quest for Normalcy

  • Logo

  • Unknown Blogger

  • March 2011
    M T W T F S S
    « Feb   Apr »
  • Recent Posts

  • Pages

  • Categories

  • Archives

  • Meta

  • Blog Stats

    • 10,700 hits
  • Advertisements

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:


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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: