# 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 a_{0}, a_{1}, ... a_{n}
such that

241 = a_{0}2^{0}+a_{1}2^{1}+
... + a_{n}2^{n}

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

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

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 2^{n-1}, 2^{n-2}, ..., 2^{0}, 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 2 ^{n} < 241
Let a_{n} = 1
Let R = 241 - 2^{n}
For i=n-1 to 0, counting backwards, do the following
If 2^{i} < R, then
Replace R by R - 2^{i}
Set a_{i} = 1
Else
Set a_{i} = 0
End If
End For
Print the resulting binary number: "a_{n}a_{n-1}...a_{0}"
`

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 2^{0}
to see whether it is larger than 241, and when it is not, then we try
2^{1}, continuing until we get to 2^{8}, 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 2 ^{i} < 241, do the following
Set n = i
Replace i by i+1
End While
Let a_{n} = 1
Let R = 241 - 2^{n}
For i=n-1 to 0, counting backwards, do the following
If 2^{i} < R, then
Replace R by R - 2^{i}
Set a_{i} = 1
Else
Set a_{i} = 0
End If
End For
Print the resulting binary number: "a_{n}a_{n-1}...a_{0}"
`

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

Assignment 6 is posted.

The midterm exam will take place Monday, 16 October. As with all
exams, all paper notes may be used, but no electronic devices
are permitted. There is a sample exam
available.