EE/CS 51 Homework 0 Notes

Homework 0 - Base conversion and program design

Due: 2006-01-06

Notes on hexadecimal

Some of you unfamiliar with hexadecimal notation may be wondering how to represent digits about 9. The answer is you use letters: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.

For example, the number 3162 in hexadecimal is C5Ah, since 3162 = 12 × 162 + 5 × 162 + 10 × 160. The convention is that we put a lowercase 'h' after the number to let the reader know the number is in hexadecimal in case no letters appear. Also, for other bases, it is customary to subscript a number with the base when base 10 is not used, e.g. 5227 = 261.

Notes on number conversion

Realize that the digit representation (sequence of digits) of a number in a given base is the coefficients of the powers of base that need to be added together. For example in ordinary base 10,

N = 34825 = 3 × 104 + 4 × 103 + 8 × 102 + 2 × 101 + 5 × 100

An alternate, and perhaps more useful way of interpreting a digit representation (in the context of this homework), is to think of the sequence as a set of remainders. Given a number N and its digit representation anan-1an-2…a1a0 of N in base B,

N = an × Bn + an-1 × Bn-1 + … + a1 × B1 + a0 × B0 = Σi=0…n(ai Bi)

Suppose we now divide through by a power of B,

N ÷ B = (an × Bn-1 + an-1 × Bn-2 + … + a1 × B0) + a0 × B-1 = Integer(N ÷ B) + Remainder(N ÷ B) × B-1

So from the above, we see that the lowest digit was extracted: a0 = Remainder(N ÷ B). If we repeat this process with the integer part that we got, we would then extract the next digit, and so on.

Therefore, we develop a general algorithm for finding the digits of a number:

  1. Let N be the number for which we want to find the digit representation in base B.
  2. Divide N by B, write down the quotient (integer part) and remainder.
  3. Set N equal to the integer quotient found above and go to step 2 unless the new N is zero, then go to step 4
  4. The remainders written down are the reverse of the digit representation

For a concrete example, see "Change of radix," under this Wikipedia article.

Notes on program design

Glen should have covered how to effectively describe a program or algorithm in class. You should also already have an example (FACTOR) to give you an idea of what we're looking for. The idea is to describe the method by which you will accomplish a task, in enough detail that anybody given your description can perform the calculations. Of course, you must describe the method using basic operations; the factor algorithm uses only basic arithmetic operations, storage operations, comparison operations, etc.

In the above example, the operation of "divides" is not basic enough, since a computer cannot do that operation. In reality, when describing a complicated algorithm, you can often make use of such abstract operations, but we are working with mathematical algorithms and assembly language. Because we are very close to implementing the program, we want to describe the program in low level terms and primitive operations.