University of Toronto
CSC 148S--Introduction to Computer Science, Spring 1998
Assignment 0: Number Systems

Due electronically: Wednesday 21 January, 6:00 p.m.

This assignment is worth 3 marks towards your grade in this course.

Number systems

Probably because humans have five fingers on each hand, we count and think using the decimal (or base 10) number system. Cartoon characters only have four fingers on each hand; they probably count in base 8. Because of the way computers store information, they use the binary (or base 2) system.  

Digits are combined to represent larger numbers. For example, the decimal number 637 is made up of a hundreds digit, 6, a tens digit, 3, and a units digit, 7. The position of each digit in the number along with its value indicates how much it contributes to the value of the number. Each position represents a power of the base. In the decimal system, the rightmost digit is the digit, the next digit to the left is the digit, the next , etc.  

In general, a positive integer with digits in base , .

Consider the binary example 10110111, which equals .

With numbers that have a base greater than 10, we run out of numeric characters to represent digits equivalent to the decimal values for 10, 11, etc. The convention is to represent digits with uppercase letters of the alphabet, starting with ``A'' representing the digit equivalent of 10, ``B'' representing 11, etc. In base 16 for example, the characters used to represent digits are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Converting between bases

You are to write a program for converting a number from one base to another. There are many possible algorithms; the following is the one that you will use. It assumes the number to be converted is .

 
	Repeatedly do ``integer division'' on the number being converted, as follows:
		Let nb be the new base, and ob be the old base.
		i = 0
		p = the number to be converted
		Repeat
			divide p by nb, using ``integer division'' (see below) in base ob
		 	p = result of the division
		 	  remainder from this division
		 	increment i by 1
		Until p = 0
	The final answer is    (for some   ).

``Integer division'' just means that we produce an integer result, rather than a real-valued one. Any remainder is discarded. The ``integer remainder'' operation (also called ``modulus'') can be used to get the remainder. For example, 14/4 = 3 and 14 modulus 4 = 2; 14/7 = 2 and 14 modulus 7 = 0; 3/7 = 0 and 3 modulus 7 = 3. Make sure you are comfortable with integer division.  

Now try using the base conversion algorithm: convert 315 in base 8 to the equivalent number in binary, base 2. Here's the solution:

 
			315 / 2		 result 146	remainder 1
			146 / 2 	 result 63	remainder 0
			63 / 2 		 result 31	remainder 1
			31 / 2 		 result 14	remainder 1
			14 / 2 		 result 6	remainder 0
			6 / 2 		 result 3	remainder 0
			3 / 2 		 result 1	remainder 1
			1 / 2		 result 0 	remainder 1

If the integer division result values don't look right in the above example, remember this is integer division in base 8. For example, dividing 315 by 2 in base 8 goes as follows:

 
		      146 	(This is the result.)
		 2 )  315
		      2
		      11 	 (This is the equivalent of 9 in base 10.)
		      10
		       15 	 (This is the equivalent of 13 in base 10.)
		       14
		 	1 	 (This is the final remainder.)

Do some more examples, by hand, to convince yourself that the conversion algorithm works. To keep things simple, start with decimal numbers. You can always check your answer by using the algorithm to convert the answer back to decimal. Several other examples are provided on the course web page.

Your task

We have written much of the program for you. It includes two files, containing a class called NIB, and a main class to test it. They are available on the web page. Use your web browser to save the files so that you can work on them.  

The NIB class stores a number in a specified base. The number is stored as an array of individual digits, plus an integer indicating the base. NIB methods include:

• divide: integer division,
• remainder: remainder (modulus),
• toString: convert a number to a string so that it can be printed,
• convertTo: convert a number from one base to another,
• subtract: subtract one number from another in the same base.

The input to the program consists of three integer values, each on a separate line: the base of the number to be converted, the base of the answer, and the number to be converted. The output is the converted number. The program assumes that (1) the number to be converted is , (2) all bases are between 2 and 16 inclusive, and (3) any input or result is at most 20 digits in length.  

Your task is simply to complete the convertTo and subtract methods. The rest of the program is complete.  

Caution: You must use our starter code, and you must not make any alterations to it. In particular, do not change the existing (or add new) input or output statements. For example, do not add prompts. You may, however, find it convenient to break down the missing methods into smaller subtasks. Feel free to add additional methods. They should be labelled ``private'', since they are just helper methods and will never be called from outside the class.

Some useful advice

Begin by studying the class that is provided. Especially read the comments that are included in the code. (You may want to write small ``tester'' programs that feed values to the methods in the class and print the result.) Once you understand the problem and the partial solution provided, write your code out on paper and trace it by hand before you go near a computer, in order to get rid of as many errors as possible.  

Even if you plan to develop your program at home, you will have to use the university's CDF-PC computers to hand in your final program. Make sure you log in and get comfortable with our computers well before the due date. Try to get your assignment finished early. The computers are likely to be very crowded near the due date.  

This assignment is unusual in comparison to the rest of the assignments in CSC148. First, it is far less difficult than the assignments to come. Second, you will hand it in electronically, whereas future assignments will generally be handed in on paper. Finally, only the correctness of your code will be evaluated. Future programs will be evaluated also for programming style, documentation, and testing, and will require a report. These aspects may be worth as much as 75% of future programming assignments.

How to hand in your assignment

For this assignment, your solution will be marked by a computer program, which will put it through a thorough set of test cases. We will not tell you what these tests are. Because the assignment is simple, the marking scheme will be tough. You should therefore test your code very thoroughly before handing it in.  

Because this assignment is to be marked by a program, you will hand it in electronically rather than on paper. When you are convinced of the correctness of your code, export class NIB into a single text file called NIB.java and hand it in electronically using the ``Hand in (submit)'' command, found under the ``File Utilities'' icon on the PCs in our lab. Do not hand in the main class, since you will not have changed it.

If you hand in a solution more than once, we will have only a copy of your most recent version; our copy of the older ones will be erased.

The program that will mark your assignment is not terribly clever, and can only compare your program's output character for character with what we tell it is the correct output. If your output is different in any way from the expected output, it will be considered wrong, and your mark will be zero. For this reason, we are providing, among other things, the statements that perform input and output. If you modify these in any way, or add other input or output statements (for example, if you add prompts) your mark will be zero. In addition, you must use the file name NIB.java when you hand in your assignment, or your mark will be zero.  

Check the 148 web site

Remember that it is your responsibility to regularly check the course web site for announcements. There we often post answers to common questions concerning assignments, and sometimes post corrections to assignments.

Having problems with Java?

If you are having problems with the language, using classes, defining and using methods, or creating objects, consider taking CSC 108 before CSC 148.