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
—