Art of Computer Programming: Euclid’s Algorithm

Math is fun!

So here’s the first algorithm from the Art of Computer Programming written in php.

With small irritation over the fact that the code tag in WordPress removes indentations.

Which I was able to solve with a few non-breaking spaces aka & nbsp ; because code needs indenting. Like poetry (all writing really) its legibility depends on formatting.

echo 'Euclid\'s Algorithm 1.1E ';
$number1 = 125;
$number2 = 15;

$m = $number1;
$n = $number2;

echo “Given two numbers m = $m and n = $n, find the greatest common divisor. “;
echo ‘Find the remainder using the php modulus function (%). ‘;

$remainder = $m % $n;

echo “The remainder is $remainder “;
echo ‘Is the remainder zero? ‘;

if ($remainder == 0) {
    echo ‘Yes! The remainder is zero! ‘;
} else {
    echo ‘Nope. Reduce. (Here Knuth says in mathematical notation set m to what n is and n to what the remainder is.) ‘;
}

Thanks to an online code runner it’s easy to see the output is:

Euclid’s Algorithm 1.1E
Given two numbers m = 125 and n = 15, find the greatest common divisor.
Find the remainder using the php modulus function (%).
The remainder is 5
Is the remainder zero?
Nope. Reduce. (Here Knuth says in mathematical notation set m to what n is and n to what the remainder is.)

Notice that I stopped with “Reduce.” That’s because this seemingly simple last step is recursion and insanely vital to programming but also challenging.

When writing code from scratch not algorithms in a book the code often hits the point where the next step involves recursion and then the code needs to be modified. As a result I think it’s interesting to look at the pre-recursion code and then add the recursion.

I prepared to recurse by starting with Number1 and Number2 instead of calling them “m” and “n” which I had other plans for. Now all I have to do is add a bit here and there and change a little there and here. Watch…

echo 'Euclid\'s Algorithm 1.1E';

$number1 = 125;
$number2 = 15;

function littleEuclid($m, $n) {
    echo “Given two numbers m = $m and n = $n, find the greatest common divisor. “;
    echo ‘Find the remainder using the php modulus function (%). ‘;

    $remainder = $m % $n;

    echo “The remainder is $remainder “;
    echo ‘Is the remainder zero? ‘;

    if ($remainder == 0) {
        echo “Yes! The remainder is zero! n is the answer! The answer is $n “;
    } else {
        echo ‘Nope. Reduce. (Here Knuth says in mathematical notation set m to what n is and n to what the remainder is.) ‘;
        littleEuclid($n,$remainder);
    }
}
littleEuclid($number1,$number2);

I just put in a function name where I had been setting $m and $n and then closed the function off.

Where Knuth said “Reduce” I made a call to that function and would continue to make the call until the greatest common divisor is found.

All I had to do to get it started was call my littleEuclid function with Number1 and Number2 at the bottom of the page. Too beautiful.

Euclid’s Algorithm 1.1E
Given two numbers m = 125 and n = 15, find the greatest common divisor.
Find the remainder using the php modulus function (%).
The remainder is 5
Is the remainder zero?
Nope. Reduce. (Here Knuth says in mathematical notation set m to what n is and n to what the remainder is.)
Given two numbers m = 15 and n = 5, find the greatest common divisor.
Find the remainder using the php modulus function (%).
The remainder is 0
Is the remainder zero?
Yes! The remainder is zero! n is the answer! The answer is 5

Categories: algorithms, books, geeky, math, php, programming | 4 Comments

Post navigation

4 thoughts on “Art of Computer Programming: Euclid’s Algorithm

  1. =) That was fun: https://gist.github.com/notbenh/8277250

    First I re-implemented littleEuclid() in perl and then built microEuclid() to just return the correct value.

    • I plan on posting all the algorithms as I go through the book. I should probably set up a git repo for it. Doing just the correct value is a good final version. I just like all the messy versions (with code echoes to be turned into comments) that build up to it. I’ll post the github repo when I do the next one. :)

    • But if you want a quick preview it will all go here: https://github.com/rebekahgolden/i-heart-knuth

      Yes, I created an empty project called PMS-on-Rails. No, I do not remember if I was sober at the time. Yes, I still think it’s funny.

  2. It’s nice to see about the algorithm. However it would be good if PHP code is formatted in a nice way. Hope wordpress offers it soon

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

Blog at WordPress.com.

%d bloggers like this: