Last Time Any questions about course procedure?

• We discussed number and noted that a number and its representation are two different things.
• We learned about the world of tally mark arithmetic. It's butt-simple, but large numbers become hideously unwieldy.

Denominational Numbering

Roman Numeral Values

• M is 1000
• D is 500
• C is 100
• L is 50
• X is 10
• V is 5
• I is 1

Borrowing Thesea are the allowable borrowing combinations.

• CM is 900
• CD is 400
• XC is 90
• XL is 40
• IX is 9
• IV is 4

parse (v. i.) to derive meaning [from symbols]

Parsing We add up the values, using the borrowing conventions when we can.

MCMLVII = 1957

     M    CM    L    V   II
   1000  900   50    5   2    → 1957

Base Numbering Systems

GREED IS GOOD

US paper currency comes in denominations 1, 2, 5, 10, 20, 50 and 100. Describe a scheme for counting out an amount of money using as few bills as possible.

We all agreed this is the optimal strategy. Start with the biggest bill you can and use as many as possible. Repeat this through the lower denominations. You might say this algorithm is "greedy."

Binary Numbers

We can use the greedy algorith to convert a decimal number to binary. What are the "bills?" They are powers of 2.

We will look at 368.

First list powers of 2 until you are at or a past your number, in this case 368.

1
2
4
8
16
32
64
128
256
512

Now make three columns. Note the bottom row; we can't use a 512 so we list 0 of those and still have 368

denom quantity  remainder
1     
2     
4     
8     
16    
32    
64    
128   
256   
512     0         368

We can use a 256, so we do so and have 112 left.

denom quantity  remainder
1      
2      
4      
8      
16     
32     
64     
128    
256     1        112
512     0        368

We can't use a 128. So mark a 0 and leave remainder alone.

denom quantity  remainder
1      
2      
4      
8      
16     
32     
64     
128     0        112
256     1        112
512

Continue this; the remainder is guaranteed to whittle down to 0.

denom quantity  remainder
1       0
2       0
4       0
8       0          0
16      1          0
32      1         16
64      1         48
128     0        112
256     1        112
512     0        368

Now read up the middle column to get the binary expansion for 368; it''s 10111000.

Let's unpack it for all of you doubting Thomases out there.

   101111000
   1   0   1   1   1   0   0   0   0
 256  128  64  32  16  8   4   2   1

 256
  64
  32 
  16

This works for any base. Let's try 3 on 368.

denom qty   rem
1      2     0
3      2     2
9      1     8
27     1    17
81     1    44
243    1   125
729    0   368

111223 = 368

This is the BIGENDIAN method, since we start at the big end. Is there a LITTLEENDIAN method? Yep.

Let us make a simple observation Integer divide a decimal number by 10. What happens?

368//10 = 36

This amputates the last digit.

Now mod by 10.

368%10 = 8

This hands you the last digit.

There is noting special about 10. If x is an number,

• x//b is x with its last base-b digit chopped off.
• x%b is x's last base-b.

Here, let's try this on 368₃.

368%3 = 2   *2           The * is a wildcard standing for a glob of {0,1,2}
368//3 = 122
122%3 = 2    *22         Here we see the second to last digit
122//3 = 40
40%3 = 1     *122    we continue this
40//3 = 13 
13 % 3 = 1   *1122
13//3 = 4
4%3 = 1      *11122
1//3 = 0     11122      we know we are done by the 0 you see here.

Convention We use the prefix 0b to say "this is a binary number. So, we have

368 = 0b101110000.

368%4 = 0   *0
368 // 4 = 92

92 % 4 = 23
23 % 4 = 3   *30