Euclid’s Algorithm

Euclid was a very prolific mathematician, and it is probably a mistake to be surprised that his name resides in yet another algorithm – one used to determine the greatest common divisor. This is commonly known as Euclid’s Algorithm. This algorithm is very simple (only 2 steps), but it can seem subtle at first.

The greatest common divisor (GCD) is the largest number that two integers can divide by. For instance, the greatest common divisor of 16 and 12 is 4. In this post, we consider only nonnegative integers.

Consider the following illustration (left side only – the one labeled “Euclid’s example”), where the two black bars represent the integers for which we seek the greatest common divisor.

Illustration of Euclid’s Algorithm

The black bars are those labeled AB and CD. Suppose we craft the bars so that CF (blue) is in fact the greatest common divisor of AB and CD. Let AB be 10 times the length of CF, and CD be 7 times the length of CF.

Suppose that the length of AB is larger than the length of CD. The trick in the algorithm is that the difference, or d, between AB and CD (AB – CD) will always be greater than the GCD, unless AB = CD (in which case AB or CD is the GCD).

The reason why d will always be greater than the GCD is because both AB and CD must be a factor of GCD, and the difference between AB and CD must be a factor GCD. Therefore, GCD is a factor of d, so d must be greater than or equal to GCD.

The steps to the algorithm are as follows, if AB and CD are the two nonnegative integers we wish to find the GCD for:

Step 1: Let AB be the larger of the two numbers. Then set d = AB – CD

Step 2: If d = 0, then CD is the GCF. If d is not 0, then repeat Step 1 with AB = CD, and CD = d

However, the subtraction method can take many steps if the two values AB and CD are far apart. It has been common to reduce the number of steps by calculating the remainder between AB and CD. The same logic still applies, however, except we remove the many factors of CD in the difference d between the two numbers AB and CD for each loop.

We can now let the code do the talking!

Sieve of Eratosthenes

The Sieve of Eratosthenes is often one of the first algorithms taught in
computer science books. This simple algorithm showcases the ability
to calculate primes numbers through the power of a computer without learning
much of the nuts and bolts of a programming language. Finding the
first 100 prime numbers can be done in a fraction of a second, and the
first 1000 prime numbers performed in a split second. It definitely proves to have a
computer around to aid in computation!

From Wikipedia, here is an animation of how the algorithm works:

Animation showing the Sieve of Eratosthenes

The above animation uses the Sieve of Eratosthenes to find all prime
numbers up to 120.

The number 2 is chosen first as the starting point and first prime. Then, all multiple values of 2
are crossed off (in red) from being prime numbers. Next, number 3 is chosen as a
prime number, and all multiple values of 3 (in green) are crossed off from being
possible prime numbers. Since the number 4 is already marked off as red from being
a multiple of 2, the number 5 is chosen as the next starting point and saved as a prime. This continues
until all positions are either chosen as prime or crossed off.

If n is the value that we want to check prime numbers until, then we will ever cross off
multiples up to sqrt(n), because all multiples of sqrt(n) above sqrt(n) are larger than n.
(This is because we would only ever multiple sqrt(n) by values larger than sort(n) by the
time we get there, since values smaller than sqrt(n) have been crossed off).

The mod operation comes to mind when checking for prime numbers.
Here is the Sieve of Eratosthenes using the mod operation:

And here it is without using mod!

Gruff – Ruby Plotting Library

I’ve been looking around to find a Ruby plotting library in order
to play with some data. The scientific community has gathered more
around Python, and it seems like Ruby has a ways to go before catching up.
It took some digging, but I’ve settled on Gruff, which seems
to be a well-maintined plotting tool.

I’m also starting to look at the Introduction to Statistical Learning course offered online
by Stanford. I think the textbook and lectures are excellent, though
admittedly I’ve been following the textbook more closely than the lectures.

My goal is to do everything in Ruby, since I like Ruby so much!

There is a free online textbook for the course, and all the data is available
on the textbook’s website.

I like this textbook, because in addition to being pedagogical, the authors chose R
as the language to showcase statistical techniques.

To start things off, I used gruff to graph one of the first datasets, Advertising.csv.

Here is the graph (click for larger version):

And the code to produce the graph!

RSpec Test for POSTing a JSON file and Obtaining Correct Response

I wasn’t able to find my exact problem from a Google search,
so I’m posting this here in case it helps someone.

I’d like to create an RSpec test that posts a JSON file to
a Rails API controller, and ensure that the correct
output exists.

The particular use case for me is that my JSON response
must always be the same if the same JSON request is posted.

Here is the code to do it:

The squish method takes care of whitespaces and newlines.
The eql? method tests for equality of the value of an object.

Have a better way or would like to criticize? Please let me know in the comments!

Using Gist with WordPress on DreamHost

DreamHost makes it incredible easy to fire up a WordPress app on your domain.

DreamHost has “one-click installs,” which include several open-source tools for a website – including WordPress. It’s free if one has the fully-hosted plan.

One just adds the WordPress app. Once the WordPress app is installed, syntax highlighting can be performed through embedding Gists. It seems to be a simple option for introducing syntax highlighting in code.

I’m using oEmbed Gist, which allows you to paste the URL on it’s own line in the WordPress editor:

`https://gist.github.com/8589700`

…and, voilĂ !

The code is included, syntax highlighting and all!