Department of Mathematics

Math 300: Mathematical Computing

Algorithm Example

As an example of the use of programming constructs, let's formulate an algorithm for converting a decimal number to base 2.

As a first pass at the algorithm, let's recall how we go about doing this conversion by hand. Remember that to convert e.g. 241 to base 2, we have to find numbers a0, a1, ... an such that

241 = a020+a121+ ... + an2n

 Evidently the first thing we have to do is find the value of n. We know that n is the largest integer such that 2n < 241. Once we find n, we put a "1" in the 1st digit of the binary number, and find the remainder when we subtract 2n from 241. Then we can test to see whether 2n-1 is smaller than that remainder. If it is, then we put a "1" in the 2nd digit of the binary number. If not, we put a zero there. Next, we subtract out that 2n-1 (if we can), and find the remainder, and then check to see whether 2n-2 is smaller than that new remainder. If it is, we put a "1" in the 3rd digit of the binary number. We continue this until we are down to 20. Thus, our first stab at an algorithm is something like this.

Find the largest n such that 2n < 241
Let an = 1
Let R = 241 - 2n
If 2n-1 < R then let an-1 = 1 and let S = R - 2n-1
Otherwise let an-1 = 0 and let S = R
If 2n-2 < S then let an-2 = 1 and let T = S - 2n-2
Otherwise let an-2 = 0 and let T = S
Continue this process until we find a0
Print the resulting binary number: "anan-1...a0"

While humans who know some mathematics will be able to follow and carry out this process, computers will have a hard time. The vague instruction to continue until done is not helpful to the computer, and the computer will not know what to name the other remainders it computes as it goes along. On the other hand, we see that there are some repetitive processes in there that computers love to do. We will repeat the If...Otherwise steps for 2n-1, 2n-2, ..., 20, so what we need here is a "for" loop, as discussed in the programming page. We also note that whenever we compute a new remainder, we don't need the old one any more, so we could just replace the new remainder in the old variable. We write

Find the largest n such that 2n < 241
Let an = 1
Let R = 241 - 2n
For i=n-1 to 0, counting backwards, do the following
   If 2i < R, then
      Replace R by R - 2i
      Set ai = 1
   Else
      Set ai = 0
   End If
End For
Print the resulting binary number: "anan-1...a0"

Thus time we have indented the code inside the For and If constructs, just to make it a little clearer to the reader when we are doing conditional actions.

On closer inspection, this looks more solid, but that statement "Find the largest..." is still quite vague for the computer. How is it going to do that? We know that the thing to do is to try 20 to see whether it is larger than 241, and when it is not, then we try 21, continuing until we get to 28, which is larger than 241. We then know that the integer before 8 (yes, 7, of course) was the n we wanted. We could do this in our algorithm using a "While" construct.

Set i=0
While 2i < 241, do the following
   Set n = i
   Replace i by i+1
End While
Let an = 1
Let R = 241 - 2n
For i=n-1 to 0, counting backwards, do the following
   If 2i < R, then
      Replace R by R - 2i
      Set ai = 1
   Else
      Set ai = 0
   End If
End For
Print the resulting binary number: "anan-1...a0"

This has evolved considerably from our first attempt, but we have now produced an algorithm that could be programmed onto a computer.


The "final exam" for this course will take place at 8:00 AM on Tuesday, 12 December. This will be an ordinary 50 minute test. It will be comprehensive, but weighted toward the latter half of the semester. As always, paper notes will be permitted, but no electronic devices will be allowed.




A Solution example is available for the quiz.




Assignment A is posted.

Department of Mathematics, PO Box 643113, Neill Hall 103, Washington State University, Pullman WA 99164-3113, 509-335-3926, Contact Us
Copyright © 1996-2015 Kevin Cooper