3.6. Algorithms and Efficiency

At this point we have covered enough topics that we should introduce the concept of algorithms and efficiency. Although the word sounds complicated, the concept is quite simple. An algorithm is a step-by-step problem-solving method, especially one that is an established method for solving a problem in a finite number of steps. Using a very loose interpretation of the word, every program we write to solve a problem is an algorithm. However, we usually reserve it for, as the definition says, some established method of solving a problem. Many well-known algorithms are extensively documented in various textbooks for solving problems that tend to recur in programming (such as sorting an array in ascending or descending order). We will cover many of these algorithms in Unit II. For now, we will simply introduce the concept of designing an algorithm.

Often, it is easiest to describe an algorithm in pseudocode before trying to code it. Pseudocode is pseudo because it has no defined syntax. In other words, we simply describe the steps of an algorithm in plain spoken-language terms. For example, the following is the pseudocode algorithm for finding a mean:

Set variable Sum to 0
Loop until reaching end of list:
  Add each value in the list to Sum
Divide Sum by total number of items in list

One advantage of pseudocode is that it is immediately obvious what the steps of the algorithm are without placing it into any programming language (which in turn makes it easy to translate into any programming language). Pseudocode can essentially be anything you want (since it has no defined syntax). The pseudocode above is written in very plain English, but we could write it in a more mathematical form:

Every algorithm generally must meet two requirements (the first is obvious):

It must successfully solve the problem it is meant to solve for all possible cases of input.
It should solve the problem in the most computationally efficient manner possible.

The first requirement states that it must sucessfully solve the problem for all possible cases of input. For example, consider our function for finding the mean from the previous section:

function Mean(const A : TRealArray;
  Count : Integer) : Real;
var
  K : Integer;
  Sum : Real;
begin
  Sum := 0;
  For K := 0 to Count-1 do
    Sum := Sum+A[K];
  Result := Sum/Count;
end;

This algorithm successfully computes the mean for everything except an empty array. If Count is 0 then it fails because you can't divide by 0. A more robust algorithm would be the following:

function Mean(const A : TRealArray;
  Count : Integer) : Real;
var
  K : Integer;
  Sum : Real;
begin
  if Count > 0 then
  begin
    Sum := 0;
    For K := 0 to Count-1 do
      Sum := Sum+A[K];
    Result := Sum/Count;
  end
  else Result := 0;
end;

Excercise 3-10.

Solve the following problems.

Say we have two variables and . Write pseudocode for an algorithm to swap the values in the two variables.
The pseudcode could technically be anything. The following are a couple of examples. The key is that the value in one of the variables must be stored in another variable.
Store A's value in Buffer
Set A to the value in B
Set B to the value of Buffer
The following is also valid pseudocode:

Show Solution
Using the pseudocode from above, write a procedure in Object Pascal that swaps two integer variables.
To successfully swap the two integers, you will need to pass them by reference using the var directive.
Show Solution
Although it is fairly trivial, the swap algorithm is quite fundamental so you should remember it.

The second requirement of an algorithm is that it solves the problem in the most efficient way possible. Computational efficiency can often be tricky to define. As a general rule, it is simply the algorithm that executes the fewest statements (more acurately the fewest number of efficient assembly statements when the high level language is translated to machine code, but this is beyond the scope of this unit). However, having the smallest number of statements does not always mean you have the most efficient algorithm. For example, consider this variation of computing the mean:

function Mean(const A : TRealArray;
  Count : Integer) : Real;
var
  K : Integer;
begin
  if Count > 0 then
  begin
    Result := 0;
    For K := 0 to Count-1 do
      Result := Result+A[K]/Count;
  end
  else Result := 0;
end;

This certainly has fewer statements as well as fewer variables by dividing each A[K] by Count. It achieves the exact same result. However, it is much less efficient than the previous algorithm. The reason is that a real number division is one of the most computationally expensive operations the processor can perform. The way the algorithm is written now, it will perform one division for every item in the array instead of one division per call to the function Mean. Thus, in terms of faster code, the previous formulation of the algorithm is more efficient.

Excercise 3-11.

In Section 2.10 we wrote a simple loop algorithm that computes the greatest common factor (gcf) of two numbers by testing the expression Factor1 mod Factor2 = 0 all the way from 2 to min(Factor1,Factor2). Although this algorithm accomplishes what it sets out to do, it is not actually the most efficient way to find the gcf of two numbers. The fastest algorithm known for finding the gcf is Euclid's algorithm. If you remember from mathematics, Euclid was the Greek mathematician who developed much of the theory behind modern geometry over 2000 years ago. This makes Euclid's algorithm one of the oldest (possibly even the oldest) known algorithm. As with most improvements of algorithmic efficiency, the algorithm comes from an insight about the properties of two integers with respect to their gcf: the gcf of two numbers does not change if the smaller number is subtracted from the larger. For example, 8 is the gcf of 40 and 16. (40-16) = 24 and the gcf of 24 and 16 is still 8. This is easy to see when we rewrite 40 and 16 in terms of their gcf's: 8*5-8*2 = 8*(5-2). If we replace the larger number with the difference and continue this loop, the difference will eventually be 0 because the larger number will always decrease by an integer multiple of one of its factors:

Iteration 1: (40-16) = 8*5-8*2 = 8*(5-2) = 8*3 = 24
Iteration 2: (24-16) = 8*3-8*2 = 8*(3-2) = 8*1 = 8
Iteration 3: (16-8) = 8*2-8*1 = 8*(2-1) = 8*1 = 8
Iteration 4: (8-8) = 8*1-8*1 = 8*(1-1) = 8*0 = 0

Write pseudocode for that specifies the algorithm described above.
There are multiple ways to write pseudocode since it has no defined syntax. Here is one (assigning A to X at the beginning instead of B will work too):

Show Solution
Implement the pseudocode from the previous problem in Object Pascal. Our previous algorithm from Section 2.10 is given below. Compare it to Euclid's algorithm by placing a global variable counter in each that counts the number of iterations. Test both implementations on GCF(40,16) and GCF(8704,22016) by printing the returned values and iteration counts to the screen (Remember: You'll need the unit Math for the Min function in following code).
function SlowGCF(A,B : Integer) : Integer;
var
K : Integer;
begin
for K := Min(A,B) downto 1 do
begin
    if (A mod K = 0) and (B mod K = 0) then
    begin
      Result := K;
      Break;
    end;
end;
end;
When you run this program you will see that SlowGCF and GCF both return the correct answer, but GCF using Euclid's algorithm runs with fewer loop iterations. In the case of 40 and 16, SlowGCF takes 9 iterations since 8 is the gcf and the loop starts at 16 (it's 9 and not 8 because 16 has to be checked too). GCF finds it in 4 iterations (for the reasons we showed above in the list of iterations). For 40 and 16, the difference between GCF and SlowGCF isn't very significant. However, for 8704 and 22016 Euclid's GCF takes 12 iterations and our SlowGCF takes 8,193 iterations. Clearly as the numbers become large enough Euclid's GCF algorithm is far preferable to our simpler slow one.
Show Solution
In the previous problem we implemented Euclid's algorithm using subtractions. Is there a better way? Think about how 40-16 = 24 and then 24-16=8. We subtracted 16 twice. Is there a way we can save iterations by doing an operation only once? In other words, given 40 and 16 we could find some X such that 40-16*X = SomeNum where SomeNum is the next value to be used in the iteration? Hint: Think about what would happen in this situation if X = 3. Then think about what simple operation between 40 and 16 would give 8. Really: think about this before looking at the solution.
When X = 3 we overshoot by 8 and would get 40-16*3 = -8. When X = 2 we undershoot by 8 so we get 40-16*2 = 8. Thus, 40 divided by 16 is 2 with a remainder of 8. Since mod gives us the remainder, 40 mod 16 = 8. Another nice thing about using mod is that 16 mod 40 is 16. This is because 16 divided by 40 is 0 with a remainder of 16. This means that not only can we eliminate iterations, but we can also drop the if statement and swap operation on each iteration because mod essentially does a swap for us. Also keep in mind that on every iteration in the previous algorithm we obtained two numbers that share a gcf.
Show Solution
Given what we discovered in the previous problem, write the pseudocode for an even faster version of Euclid's algorithm. Start with the iterations we used before and think about how we eliminate iterations.
Iteration 1: (40-16) = 8*5-8*2 = 8*(5-2) = 8*3 = 24
Iteration 2: (24-16) = 8*3-8*2 = 8*(3-2) = 8*1 = 8
Iteration 3: (16-8) = 8*2-8*1 = 8*(2-1) = 8*1 = 8
Iteration 4: (8-8) = 8*1-8*1 = 8*(1-1) = 8*0 = 0
To begin with, we no longer need the swap operation. For example, if A = 16 and B = 40 then A mod B = 16. We can then assign B to A and 16 to B which has effectively swapped the integers. Perhaps not surprisingly, the anatomy of this pseudocode will look very similar to the anatomy of the swap algorithm.

Show Solution
Implement the pseudocode from the previous problem in Object Pascal as a function called FastGCF. Include an iteration counter and then compare all three algorithms with 40 and 16 as well as 8704 and 22016.
Again this algorithm returns the correct answers 8 and 512, but for the former it obtains the gcf 8 in only 2 iterations as compared to 4 in our subtraction Euclid GCF and 9 in SlowGCF. The savings become even more significant with 8704 and 22016 where FastGCF finds the solution in 5 iterations, the subtraction GCF takes 12, and SlowGCF takes 8,193. Another point to note is that the algorithm is incredibly elegant. Without the IterCount variable, it consists only of a loop with 3 lines of code and 3 variables with a simple mod operation.
Show Solution
Take this exercise one step further by writing one line of code that will give the least common multiple (LCM) in terms of the greatest common factor. Hint: Think about what it would mean for two numbers to have a least common multiple. For example, the lcm of 2 and 4 is 4 because 4 is evenly divisible by 2. But for 5 and 7 it's 5*7 = 35 because they have no common factors. What about 10 and 15. Is it 10*15 = 150? This is a common multiple but it is not the least common multiple because 10 and 15 share 5 as a common factor. So given this knowledge, how would we find the least common multiple when we know the greatest common factor.
The reason we cannot multiply 10 and 15 and say that 150 is the lcm is that 5 is a common factor. The solution then is to eliminate the common factors of the two numbers by dividing by the gcf. Since we know that two numbers are always evenly divisible by their gcf's, we can use the div operator in Object Pascal for integer division since this is more efficient than floating point division:
Show Solution