UIT2201: CS & the IT Revolution

Remarks on Division and on Print-Formatting [Jan '08; Rev: Feb '08]

For UIT2201, students can assume that the following are primitive pseudo-code instructions:

My reason for not getting into the nitty-gritty details of these (often) messy operations is precisely that -- they are nitty-gritty and messy. And, they do not add very much intellectual content to CS/IT. I prefer the students to focus on the overall process, the flow of the algorithms, rather than to be "hung-up" on some small technical detail.

(A programmer/computer scientist will certainly need to know all these nitty-gritty, messy details to program a computer, but we (in UIT2201) don't need to know all that to understand the process and to give the algorithm in pseudo-code. We can assume that these are primitive operations (and they are). As an analogy, we often say "start the car and drive from Block ADM to Clementi Central" without having to know all the details of what really make a car run after you turn the ignition key on and start the engine.)

Not withstanding the above, there will always be students who cannot live with not knowing these technical details (sigh!) -- and some will get visibly/audibly irritated until these are somehow addressed. So, I am writing this document to try to explain it (without getting too technical about it). [Be forewarned, you may be further confused by it.]

LeongHW, January 2008

Division and Division, and the Resulting Confusion

While most basic arithmetic operations, namely, +, -, and * (multiply) are easily and directly translated from the world of mathematics to the world of computers and programming, there is one operation that causes no end of confusion --- including some experienced programmers. Yes, I am talking about division.

Consider the question -- "What should the result of 9 divided by 4?" On most calculators, the result is 2.25. For students who first learnt integer division, "9 divided by 4 gives a quotient of 2 and a remainder of 1". As you will soon see, for computers, the result can be either 2.25 or 2 and it depends on several things and it can be quite messy!

Divide for Real Numbers: Most programming languages (actual languages used to write programs for real computers) operates with two types of numbers -- integers (whole numbers) and reals (numbers with decimal points). Real numbers in computer are very similar to numbers on your calculators (with decimal points). Similar to calculators, the symbol used to represent "divide" in most programming language is almost always the "/" symbol. And for all real numbers, "9 / 4 = 2.25".

Divide for Integers: In the integer "world", there is no way to represent fractions or the decimal parts of a number. Everything must be expressed in integers! So, "integer 9 divided by integer 4 gives integer 2". (The decimal parts are "thrown away".) In some programming languages (like Pascal), the divide operation for integers is given a different symbol (which is a good thing since things are clearer that way). In Pascal, the symbol for divide is div, and so "9 div 4 = 2" (and the remainder is automagically thrown away) and "9 / 4 = 2.25". This is clear; different operations on different types of integers gives different results.

However, in many programming languages (like C, C++, Java, C#, perl), the symbol for integer division is also the same as the one given for division of real numbers (which is a bad thing since things become confusing now)! Namely the symbol "/" now represents both "real-division" and integer-division! The meaning of "/" in "a / b" depends on whether a and b are real numbers or a and b are integers! So, "9 / 4 = 2" (here 9 and 4 are integers), while "9.0 / 4.0 = 2.25" (here, numbers with decimal points are automagically real numbers). Same symbol, different results depending on the type of data it is processing -- now that is confusing (urgh!).1

----------
1       I am sure you can tell what my opinion is on this messy issue! [Aside: Actually, things can get even more confusing when you mix up the number types, say in "c <-- a / b" and the types of a, b, and c are not either "all integers" or "all real numbers". I will not get into this here. People who really want to know, come see me during office hours! I'll gladly discuss it with you, without potentially confusing the other students.]

Finding the Remainder: On a related note, some programming language also provide a "remainder" function. Of course, the "remainder" function only works for integers. In Pascal, the symbol for "remainder" is mod, and so "9 mod 4 = 1" (the remainder when 9 is divided by 4 is 1). In other programming languages (C, C++, Java, etc), the symbol for "remainder" is "%", and so "9 % 4 = 1". Luckily, there is no confusion on this issue since remainder works only for integers.

How to "Divide by 2 and throw away the remainder"

So, as stated above, there is a primitive operation to do "divide by 2 and throw away the remainder" in almost all programming languages. In Pascal, it is the div operator; while in many other programming languages, it is the (slightly confusing) integer-divide "/" (make sure the numbers you send in are integers). For UIT2201, you can just use div. Now, I hope that clears up the issue.

On Print-Formatting"

Controlling how your output that looks like is called "print formatting". Most programming provide very detailed primitives to control exactly how everything should look like when it is printed out. There are primitives to specify

The basic "print" statement:
The details of the actual print-formatting primitives vary across different programming languages. For UIT2201, we shall use a simplified "print" pseudo-code statement (or just simply called "print" statement) defined as follows:

      print item1, item2, ..., lastitem;

and this "print" pseudo-code statement will print out

      item1, item2, ... lastitem

The "print" statement prints out (the value of) a number of items, each item is separated by a "," (comma). Each item can be a variable or a message-string. A message-string is a message that is enclosed with quotes, as in "Welcome to my Program". A message-string is printed out literally (without change). Message-strings are very important as they make the computer output more readable to humans. Below, we give some examples of the print primitive (assuming values of a,b, c are 5, 2, 3).

Code-fragment Output
  print "Welcome to my Program"  
  print "---------------------"  
  print a;
  print a, b, c;  
  print " The value of n is :", n;  
  print " # of repeated-div :", Count;   		  Welcome to my Program
  ---------------------
    5
    5 2 3  
    The value of n is   : 20
    # of repeated-div   :  5  
(Note the absence of the quotes in the printed message). We can also print a mixture of variables and message-strings to give more readable output, as shown in the last two examples.

Field-width: First, let's tackle the issue of field-width which specifies how many characters to use when printing out an item. The field-width is very useful when we want the output on different rows to "line-up" nicely in table forms. In UIT2201, we'll use this print statements

      print count (with field-width 4);
      print count (fw 4);

will print out the value of count using a field-width of 4. (The second version is a concise version of the first.) If I use "b" to mean the blank character, then

Value of Count Output
  if count=8
  if count=88
  if count=888
  if count=8888  
  if count=88888  
  bbb8
  bb88
  b888
  8888  
  88888  
If no field-width is specified, then the default field-width is 4 (at least in UIT2201). If the field-width is too small, then the print primitive will just use more spaces to the right, as much space as needed. (See the last entry in the above table, for example.) This may mess things up if you had wanted things to "line up" -- so choose your field-width carefully. Field-width can also be used when printing out message-strings and real-numbers (be careful, the decimal point counts as one character too). Note that both the message-string and the value for Cost are right justified. For example, if Cost=22.01, then
Code-fragment Output
  print "Unit cost: " (fw 13), Cost (fw 6);     bbUnit cost:bb22.01  
Printing on the same line and producing tables:
If you have been observant, you will notice one thing -- in all the above print statements, every print statement starts with a new line.

This is fine most of the time. But, once in a while, we like to print some stuff now and then later print some-more stuff on the same line. For example, to output the following sequence

        1 2 4 8 16 ...

on the same line. To achieve this, we may want an iterative algorithm that starts with "p <-- 1", "print p" (for initialization-block) and then in the iterative block we will "multiply p by two" and "print p" on the same line in the output.




To achieve "printing on the same line", we define (in UIT2201) the following modified print primitives

      print x (and then new line); // prints x and then goto new line.
      print x (and no new line);   // prints x and stay on same line.

The first primitive is the default one, meaning that
     "print x" = "print x (and then new line);".
The "print x (and no new line)" statement will print out the value of x on current line and not go to the next line. So the next print statement will continue to print on the same line. For example, if Count=4, then we have the following (b means space):

Code-fragment Output
  print Count (and no new line);
  print 2*Count (and then new line);  
  print 3*Count (and no new line);
  print 4*Count (and then new line);
  bbb4bbb8  
  bb12bb16  
So, to obtain the original sequence as output, we can use the following pseudo-code:
Code-fragment Output
 1. p <-- 1;      // init. 
 2. print p (and no new line);
 3. while (p < 16) do begin
 4.   p <-- p * 2; 
 5.   print p (and no new line);   
 6. endwhile
 7. print; 
 8. print "End of Program";
 8. stop;
  1 2 4 8 16  
  End of Program  
Note that in line 7, the command "print;" is equivalent to "print (and then new line);", which effectively, just moves to a new line, namely, prints out nothing (no item listed) and go to a new line. The print something (and no new line); primitive is especially useful for producing tables of all kinds. For example, the following produces a 2x2 table.
Code-fragment Output
  print 2 (and no new line); 
  print 4;
  print 6 (and no new line); 
  print 8; 
   2   4 
   6   8













Putting it all together now...

Alg-T2-D3(a): [Repeated-Division]
Algorithm to read in a positive integer N, and computes the number of times we divide it by 2 until we reach the number 0. 
Algorithm Repeated-Division;
 1. print "Welcome to my Repeated-Div Program";
 2. print "----------------------------------";
 3. print "  Please enter a positive integer N";
 4. Read in the number N;
 5. k <-- N;      // Do not "destroy" the var N. 
 6. count <-- 0;  // initialize count
 7. while (k > 0) do begin
 8.   k <-- k div 2;  // div by 2, throw away remainder
 9.   count <-- count + 1; 
10. endwhile
11. print "  The value of N is ", N;
12. print "  The number of repeated division is ", count;
13. print "--- End of Repeated-Div Program ---";
14. stop;
Alg-T2-D3(b): [Repeated-Doubling]
Algorithm to read in a positive integer N, and then starting with 1, computes the number of times we repeatedly double it until we get a number that is greater than or equal to N. 
Algorithm Repeated-Doubling;
 1. print "Welcome to my Repeated-Doubling Program";
 2. print "---------------------------------------";
 3. print "  Please enter a positive integer N";
 4. Read in the number N;
 5. p <-- 1;      // Start with 1. 
 6. count <-- 0;  // initialize count
 7. while (p < N) do begin
 8.   p <-- p * 2;  // double it
 9.   count <-- count + 1; 
10. endwhile
11. print "  The value of N is ", N;
12. print "  The number of repeated doubling is ", count;
13. print "--- End of Repeated-Doubling Program ---";
14. stop;

Finally, Polling and Feedback.

After you finish reading this document, do the following: (1) Goto course IVLE page and take the poll [poll comes under "Survey" in IVLE] (to indicate you have read this), and (2) Send me a short email to give me some feedback on this document. Thanks.

UIT2201: CS & IT Revolution; (Spring 2008); A/P Leong HW