Unkown Blogger Pursues a Deranged Quest for Normalcy

  • Logo

    ubpdqn
  • Unknown Blogger

  • March 2011
    M T W T F S S
    « Feb   Apr »
     123456
    78910111213
    14151617181920
    21222324252627
    28293031  
  • Recent Posts

  • Pages

  • Categories

  • Archives

  • Meta

  • Blog Stats

    • 10,595 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.

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

»
 
%d bloggers like this: