Difference between revisions of "CSC103: DT's Notes 1"

From dftwiki3
Jump to: navigation, search
Line 68: Line 68:
  
 
Ok, now an important point in the counting process.  We have written all 10 digits in the right-most position of our number.  Because we could increment this digit, we didn't have to change the digits on the left.  Now that we have reached 9, we need to ''roll over'' the list of digits.  We have to go from 9 back to 0.  Because of this roll-over, we have to ''increment'' (that means adding 1) the digit that is ''directly to the left of the one rolling over.''   
 
Ok, now an important point in the counting process.  We have written all 10 digits in the right-most position of our number.  Because we could increment this digit, we didn't have to change the digits on the left.  Now that we have reached 9, we need to ''roll over'' the list of digits.  We have to go from 9 back to 0.  Because of this roll-over, we have to ''increment'' (that means adding 1) the digit that is ''directly to the left of the one rolling over.''   
 +
 +
  0  0  9
 +
      !  |          the |-symbol shows 9 ''rolling over'' to 0
 +
      !  |          the !-symbol shows that as 9 rolls over, its left neighbor gets incremented by 1
 +
  0  1  0
 +
 +
Let's continue:
  
 
  010
 
  010
Line 89: Line 96:
 
  ...
 
  ...
  
The first thing we have done is to pad all the numbers with leading zeros so that they all have 3 digits. Then we start at 0 and keep counting.  What we do implicitly is go through a table of 10 digits we know by heart, 0 through 9, and at every new line with change the right most digit to be the next number in the table.  When that last digit reaches 9, we have to ''roll over'' and start back at 0 in our table of 10 digits.  We illustrated this in the list above by a line of dashes.  But what else do we do when we ''roll over'' the right most digit?  We also change the digit to its left, and make it become the next digit in that table of 10 digits we know by heart.  so from 009 we pass to 010. 
+
   
  
Then after a while we reach 019.  The right-most digit has to ''roll over'', which makes it become 0, and the digit to its left must change by 1.  It becomes 2, and we get 020.
+
Notice that after a while we reach 019.  The right-most digit has to ''roll over'' again, which makes it become 0, and the digit to its left must be incremented by 1.  From 1 it becomes 2, and we get 020.
  
At some point, applying this rule we reach 099.  Let's just apply our simple rule: the right most digit must roll over, so it becomes 0, and the digit to its left increments by 1.  Because this second digit is also 9 it, too, must roll over and become 0.  And because the 2nd digit rolls over, then the third digit, the one to the left of the 2nd digit increments by 1.  We get 100.  Does that make sense?  We are so good at doing this by heart without thinking of the process we use that sometimes it is confusing to deconstruct such knowledge.
+
At some point, applying this rule we reach 099.  Let's just apply our simple rule: the right most digit must roll over, so it becomes 0, and the digit to its left increments by 1.  Because this second digit is also 9 it, too, must roll over and become 0.  And because the 2nd digit rolls over, then the third digit increments by 1.  We get 100.  Does that make sense?  We are so good at doing this by heart without thinking of the process we use that sometimes it is confusing to deconstruct such knowledge.
  
So let's remember this simple rule; it applies to counting in all number systems, whether they have 10 digits (like our decimal system) or some other number:
+
So let's remember this simple rule; it applies to counting in all number systems, whether they are in base 10 or some other base:
  
 
<tanbox>When counting, we always increment the right-most digit by 1.  When this digit must roll-over back to 0, we do so, and increment the digit to its left.  If this one rolls over to 0 as well, then we do so and increment the digit to its left, and so on.
 
<tanbox>When counting, we always increment the right-most digit by 1.  When this digit must roll-over back to 0, we do so, and increment the digit to its left.  If this one rolls over to 0 as well, then we do so and increment the digit to its left, and so on.
 
</tanbox>
 
</tanbox>
  
Let's now count in ''base'' 2, in binary.  This time our "internal" table contains only 2 digits: 0, 1.
+
=====Counting in Binary=====
 +
 
 +
Let's now count in ''base'' 2, in binary.  This time our "internal" table contains only 2 digits: 0, 1.  So, whatever we do, we can only use 0 and 1 to write numbers.  And the list of numbers we use and from which we'll "roll-over" is simply: 0, 1.
 
   
 
   
 
  00000
 
  00000
  
Good start!  That's zero.  It doesn't matter that we used 5 0s to write it.  Leading 0s do not change the value of numbers, in any base whatsoever.  We apply the rule: modify the right-most digit and increment it.  0 becomes 1.  No rolling over.
+
Good start!  That's zero.  It doesn't matter that we used 5 0s to write it.  Leading 0s do not change the value of numbers, in any base whatsoever.  We use them here because they help see the process better. 
 +
 
 +
We apply the rule: modify the right-most digit and increment it.  0 becomes 1.  No rolling over.
  
 
  00001
 
  00001
  
Good again!  One more time: we increment the rightmost digit, but because we have reached the end of the available digits, we must roll over.  The right-most digit becomes 0, and we increment the 2nd digit from the right:
+
Good again!  One more time: we increment the rightmost digit, but because we have reached the end of the available digits, we must roll over.  The right-most digit becomes 0, and we increment its left neighbor:
  
 
  00010
 
  00010
Line 133: Line 144:
 
Let's put the numbers we've generated in decimal and in binary next to each other:
 
Let's put the numbers we've generated in decimal and in binary next to each other:
  
  decimal       binary
+
  decima       binary
 
  000            00000
 
  000            00000
 
  001            00001
 
  001            00001
Line 147: Line 158:
 
  ...
 
  ...
  
 +
=====Exercise=====
 +
 +
How would we count in base 3?  The answer is that we just need to modify our table of available digits to be 0, 1, 2, and apply the rule we developed above.  Here is a start:
 +
 +
0000
 +
0001
 +
0002
 +
0010
 +
...
 +
 +
Does that make sense?  Continue and write all the numbers until you reach 1000, in base 3.
  
 +
Write the first 10 numbers starting at 0 base 3.  Use as many leading 0s as makes the process easier. 
  
  

Revision as of 08:59, 31 January 2012

--© D. Thiebaut 08:10, 30 January 2012 (EST)


This section is only visible to computers located at Smith College