Block B

Numbers and their Representations

Tally Mark Arithmetic One measure of a number system's usefulness is the ease of arithmetic. This is a system for representing positive integers. How do you do the four basic operations?

Here are ideas for addition.

From Rujula Yete to Everyone: (10:26 AM) You count the total amount of tally
marks 

From Sourodeep to Everyone: (10:26 AM) just put both groups of tally marks
together and count them up 

From Anya Schrader to Everyone: (10:27 AM) You would put the groups together
and count them

In the end, they all suggest we just glue the two sets of tally marks together (that's called concatenation.

James suggested this to multiply

From James Li to Everyone:
(10:28 AM) for multiplication, draw out a vertical row with one multiplicand,
and a horizontal row with the other multiplicand, and fill in the space with
tally marks.  (then string them out in a single row)

Anya suggested this:

From Anya Schrader to Everyone: (10:28 AM) Subtraction-Pair off the tallies
together and however many are left is what you have [the result].

The mod squad chimes in

From James Li to Everyone: (10:32 AM) For n mod m, cross out the
tallies of n, m tallies at a time, until there are less than m
unmarked tallies left. The remaining unmarked tallies form the answer.

+ concatenate
- pair elements of the smaller number with the bigger and delete them. What's left is the difference.
* for each element of the first facgtor, make a copy of the second. Glue 'em all together.
// (integer division) to compute n//d, repeatedly delete d items from n until you can't. the number number of deletions is n//d the number of leftovers is n%d.
% (mod)

Here is NCSSM's enrollment.

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

What's the big shortcoming of this system? Keeping track of large numbers of things is pocket bread.

Denominational Numbering Systems Roman numerals and US currency are examples of this.

What are the advantages of Roman numerals over tally marks? What are the disadvantages?

Here are the Roman Numerals.

1 I
3 III
5 V
10 X
50 L
100 C
500 D
1000 M

MCMLVII

3785

MMMDCCLXXXV

Arithmetic? Pocket Bread (PITA) Compactness: pretty nice. It allowed the Romans to keep track of large numbers of things such as supplies, taxes, and armies.

It is interesting to note that the Mayan Numbering System is far superior to Roman numerals when it comes to arithmetic. It is based on 5 and 20.

Discussion Do you think there is a tie between number systems and human progress?

Exercise Given that US currency is issued in denominations of $1, $2, $5, $10, $20, $50, $100, write a procedure to count out an integer number of dollars using as few bills as possible

How succinctly can you write this procedure? Do you need to use any symbols at all?


Fromm Jonathan Jacob to Everyone: (10:48 AM) First use the highest bill
that is less than the amount you want. Keep adding that bill until you
cannot add another without going over the amount. Then, use the next
smallest bill that will not go over the amount and repeat until you have
reached the amount 


James Li to Everyone: (10:49 AM) Starting at the largest denomination bill
(100), integer divide the total number of bills by the value of the bill
to find the number of that bill needed, and take the modulus of the total
by the value of the bill to find what is left over. Repeat this with the
next largest denomination. From Sourodeep to Everyone: (10:49 AM) First,
find the largest bill that is less than the given amount. Then, subtract
that amount as many times as you can from the given amount, and record the
number of subtractions you did for that bill. Then use the remaining
amount and repeat the process until you get to 0. Finally, check to see
how many times you subtracted each bill and that will be the number of
bills you use.

From Sourodeep to Everyone: (10:49 AM) First, find the largest
bill that is less than the given amount. Then, subtract that
amount as many times as you can from the given amount, and
record the number of subtractions you did for that bill. Then
use the remaining amount and repeat the process until you get
to 0. Finally, check to see how many times you subtracted each
bill and that will be the number of bills you use. 

From Anya
Schrader to Everyone: (10:50 AM) Divide the amount by each
bill, starting from the highest ($100). Then, go down the line
until you are left with $0.
Ex. $348 has 3 $100, 0 $50, 2 $20, 1 $5, 1 $2, and 1 $3

We all agreed on the greedy algorithm , which says to start by using the largest possible bill and use as many as possible. You keep going down through the denominations doing this at each stage.

Binaria

In the land of Binaria, money comes in an infinitude of denominations, which are powers of 2: 1, 2, 4, 8, 16, 32, 64, ..... in a currency called a bit. Given an integer number of bits, how do you count out that amount using as few bills as possible?

How succinctly can you write this procedure? Do you need to use any symbols at all?

It's the greedy algorithm!


    Lets' try 285

    Largest bill we can use: 256 and we can use 1, leaving 29
    next largest bill is     128 and we can use 0, leaving 29
    next largest bill is      64 and we can use 0, leaving 29
    next largest bill is      32 and we can use 0, leaving 29
    next largest bill is      16 and we can use 1, leaving 13
    next largest bill is       8 and we can use 1, leaving 5
    next largest bill is       4 and we can use 1, leaving 1
    next largest bill is       2 and we can use 0, leaving 1
    next largest bill is       1 and we can use 1, leaving 0

Read down the bit column and 285 is 100011101 in base 2! Notice we never use more than one bill of any denomination.

Base Numbering Systems

Our Wormwoodean System

image of Miss Wormwood

A base numbering system has two parts, an alphabet of symbols and an integer called the base, which is an integer 2 or larger.

Decimal numbers constitute such a system. Here is the alphabet: {0,1,2,3,4,5,6,7,8,9}. Note that the base is the size of the alphabet. You can think of it as a denominational numbering system, where the denominations are powers of 10.

We use 10 because we have 10 fingers. There is nothing special about 10. We can use any base with an arbitrary alphabet of symbols, and arithmetic works pretty much the same as it did in your Miss Wormwood days. Let's try 285 in base 3. The largest bill we can use is a 243


    start with 285
    Use 1 243  and there is 42 left
    Use 0  81s and there is 42 left
    Use 1  27s and there is 15 left
    Use 1   9s and there is  6 left
    Use 2   3s and there is  0 left
    Use 0   1s and there is  0 left

    285 = 101120₃.

Notice we never use more than 2 of any "bill".

Exercise

This is called the "bigendian" method since it does the job from the big end down to the small.

Bigendian vs. Littleendian Methods

image of Swift's endians

Base numbering:  base (positive integer > 1)
 
alphabet

decimal:  {0,1,2,3,4,5,6,7,8,9} (same size as the base)

binary: {0,1}

octal:  {0,`1,2,3,4,5,6,7}

hexadecimal = {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}

0o  prefix means "octal"
0x  prefix means hexadecimal
0b  prefix means binary