Chapter 20Notes for the sixth week: digits, bases, and operations

Notes also available as PDF.

What we will cover from Chapter 4:

• Numbers and digits in different bases, with historical context
• Arithmetic, digit by digit

And additionally, I’ll give a brief summary of computer arithmetic.

20.1 Positional Numbers

A number is a concept and not just a sequence of symbols. We will be discussing ways to express numbers.

Before our current form of expressing cardinal numbers:

• Piles of rocks don’t work well for merchants.
• Marks on sticks, then marks on papyrus.

Marking numbers is costly. A large number becomes a large number of marks. Many marks lead to many errors. Merchants don’t like errors. So people started using symbols rather than plain marks.

An intermediate form, grouping:

• Egyptian: Different symbols for different levels of numbers: units, tens, hundreds. Grouping within the levels.
• Roman: Symbols for groups, with addition and subtraction of symbols for smaller groups.
• Greek (and Hebrew and Arabic): Similar, but using all their letters for many groups.
• Early Chinese: Denote the number of marks in the group with a number itself\mathop{\mathop{…}}

Getting better, but each system still has complex rules. The main problems are with skipping groups. We now use zero to denote an empty position, but these systems used varying amounts of space. Obviously, this could lead to trade disagreements. Once zeros were adopted, many of these systems persisted in trade for centuries.

Now into forms of positional notation, shorter and more direct:

• Babylonian:
• Two marks, tens and units.
• Now the marks are placed by the number of 60s.
• Suffers from complicated rules about zeros.
• (Using 60s persists for keeping time...)
• Mayan:
• Again, two kinds of marks for fives and units.
• Two positional types: by powers of 20, and by powers of 20 except for one power of 18.
• (Note that 18 ⋅ 20 = 360, which is much closer to a year.)
• Essentially equivalent to what we use, but subtraction in Mayan is much easier to see.
• (many other cultures adopted similar systems (e.g. Chinese rods)

Current: Hindu-Arabic numeral system

The characters differ between cultures, but the idea is the same. The characters often are similar as well. Originated in the region of India and was carried west through trade. No one knows when zero was added to the digits. The earliest firm evidence is in Arab court records regarding a visitor from India and a description of zero from around 776 AD. The first inscription found with a zero is from 876 AD in India. However, the Hindu-Arabic system was not adopted outside mathematics even in these cultures. Merchants kept to a system similar to the Greek and Hebrew systems using letters for numbers.

Leonardo Fibonacci brought the numerals to Europe in the 13th century (after 1200 AD) by translating an Arabic text to Latin. By 15th century, the numeral system was in wide use in Europe. During the 19th century, this system supplanted the rod systems in Asia.

The final value of the number is based on the positions of the digits:

 1234 = 1 ⋅ 1{0}^{3} + 2 ⋅ 1{0}^{2} + 3 ⋅ 1{0}^{1} + 4 ⋅ 1{0}^{0}.

We call ten the base. Then numbers becomes polynomials in terms of the base b,

 1234 = {b}^{3} + 2 ⋅ {b}^{2} + 3 ⋅ {b}^{1} + 4.

Here b = 10.

So we moved from marks, where 1000 would require 1000 marks, to groups, where 1000 may be a single mark but 999 may require dozens of marks. Then we moved to positional schemes where the number of symbols depends on the logarithm of the value; 1000 = 1{0}^{3} requires 4 = 3 + 1 symbols.

After looking at other bases, we will look into operations (multiplication, addition, etc.) using the base representations.

20.2 Converting Between Bases

Only three bases currently are in wide use: base 10 (decimal), base 2 (binary), and base 16 (hexadecimal). Occasionally base 8 (octal) is used, but that is increasingly rare. Other conversions are useful for practice and for seeing some structure in numbers. The structure will be useful for computing.

Before conversions, we need the digits to use. In base b, numbers are expressed using digits from 0 to b - 1. When b is past 10, we need to go beyond decimal numerals:

 Value: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Digit: 0 1 2 3 4 5 6 7 8 9 A B C D E F

Upper- and lower-case are common.

So in hexadecimal, DECAFBAD is a perfectly good number, as is DEADBEEF. If there is a question of what base is being used, the base is denoted by a subscript. So 1{0}_{10} is a decimal ten and 1{0}_{2} is in binary.

To find values we recognize more easily, we convert to decimal. Then we will convert from decimal.

20.2.1 Converting to Decimal

Converting to decimal using decimal arithmetic is straight-forward. Remember the expansion of 1234 with base b = 10,

\eqalignno{ 1234 & = 1 ⋅ 1{0}^{3} + 2 ⋅ 1{0}^{2} + 3 ⋅ 1{0}^{1} + 4 ⋅ 1{0}^{0} & & \cr & = {b}^{3} + 2 ⋅ {b}^{2} + 3 ⋅ {b}^{1} + 4. & & }

Each digit of \text{D}\text{E}\text{A}\text{D} has a value, and these values become the coefficients. Then we expand the polynomial with b = 16. In a straight-forwart way,

\eqalignno{ \text{D}\text{E}\text{A}\text{D} & = \text{D} ⋅ 1{6}^{3} + \text{E} ⋅ 1{6}^{2} + \text{A} ⋅ 1{6}^{1} + \text{D} & & \cr & = 13 ⋅ 1{6}^{3} + 14 ⋅ 1{6}^{2} + 10 ⋅ 16 + 13 & & \cr & = 13 ⋅ 4096 + 14 ⋅ 256 + 10 ⋅ 16 + 13 & & \cr & = 57005. & & }

We an use Horner’s rule to expand the polynomial in a method that often is faster,

\eqalignno{ \text{D}\text{E}\text{A}\text{D} & = ((13 ⋅ 16 + 14) ⋅ 16 + 10) ⋅ 16 + 13 & & \cr & = (222 ⋅ 16 + 10) ⋅ 16 + 13 & & \cr & = 3562 ⋅ 16 + 13 & & \cr & = 57005. & & }

Let’s try a binary example. Convert 110{1}_{2} to decimal:

\eqalignno{ 110{1}_{2} & = (((1 ⋅ 2 + 1) ⋅ 2 + 0) ⋅ 2 + 1 & & \cr & = (3 ⋅ 2 + 0) ⋅ 2 + 1 & & \cr & = 6 ⋅ 2 + 1 & & \cr & = 13. & & }

Remember the rows of a truth table for two variables? Here,

\eqalignno{ 1{1}_{2} & = 2 + 1 = 3, & & \cr 1{0}_{2} & = 2 + 0 = 2, & & \cr 0{1}_{2} & = 0 + 1 = 1,\text{ and} & & \cr 0{0}_{2} & = 0 + 0 = 0. & & }

20.2.2 Converting from Decimal

To convert to binary from decimal, consider the previous example:

\eqalignno{ 13 & = 8 + \mathbf{5} & & \cr & = 8 + 4 + \mathbf{1} & & \cr & = 1 ⋅ {2}^{3} + 1 ⋅ {2}^{2} + 0 ⋅ {2}^{1} + 1 ⋅ {2}^{0} & & \cr & = 110{1}_{2}. & & }

At each step, we find the largest power of two less than the remaining number. Another example for binary:

\eqalignno{ 293 & = 256 + \mathbf{37} & & \cr & = 256 + 32 + \mathbf{5} & & \cr & = 256 + 32 + 4 + 1 & & \cr & = 1 ⋅ {2}^{8} + 1 ⋅ {2}^{5} + 1 ⋅ {2}^{2} + 1 & & \cr & = 10010010{1}_{2}. & & }

\eqalignno{ 293 & = 256 + \mathbf{37} & & \cr & = 1 ⋅ 256 + 2 ⋅ 16 + 5 & & \cr & = 12{5}_{16}. & & }

You can see why some people start remembering powers of two.

If you have no idea where to start converting, remember the relations {b}^{{\mathop{log}\nolimits }_{b}x} = x and {\mathop{log}\nolimits }_{b}x =\mathop{ log}\nolimits x∕\mathop{log}\nolimits b. Rounding {\mathop{log}\nolimits }_{b}x up to the larger whole number gives you the number of base b digits in x.

The text has another version using remainders. We will return to that in the next chapter. And conversions to and from binary will be useful when we discuss how computers manipulate numbers.

20.3 Operating on Numbers

Once we split a number into digits (decimal or binary), operations can be a bit easier.

We will cover multiplication, addition, and subtraction both

• to gain familiarity with positional notation, and
• to compute results more quickly and mentally.

Properties of positional notation will help when we explore number theory.

We will use two properties frequently:

• Both multiplication and addition commute (a + b = b + a) and re-associate (a + b) + c = a + (b + c).
• Multiplication distributes over addition, so a(b + c) = ab + ac.
• Multiplying powers of a common base adds exponents, so {b}^{a} ⋅ {b}^{c} = {b}^{a+c}.

20.3.1 Multiplication

Consider multiplication. I once had to learn multiplication tables for 10, 11, and 12, but these are completely pointless.

Any decimal number multiplied by 10 is simply shifted over by one digit,

\eqalignno{ 123 ⋅ 10 & = (1 ⋅ 1{0}^{2} + 2 ⋅ 1{0}^{1} + 3 ⋅ 1{0}^{0}) ⋅ 10 & & \cr & = 1 ⋅ 1{0}^{3} + 2 ⋅ 1{0}^{2} + 3 ⋅ 1{0}^{1} & & \cr & = 1230. & & }

Multiplying by 11 = 1 ⋅ 10 + 1 is best accomplished by adding the other number to itself shifted,

 123 ⋅ 11 = 123 ⋅ (10 + 1) = 1230 + 123 = 1353.

And for 12 = 1 ⋅ 10 + 2, you double the number,

 123 ⋅ 12 = 123 ⋅ (10 + 2) = 1230 + 246 = 1476.

Multiplying longer numbers quickly follows the same pattern of shifting and adding. We can expand 123 ⋅ 123 = 123 ⋅ (1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3) to

 1 2 3 × 1 2 3 3 6 9 2 4 6 0 1 2 3 0 0 1 5 1 2 9

Another method expands the product of numbers as a product of polynomials, working one term at a time. This is essentially the same but not in tabular form:

\eqalignno{ 123 ⋅ 123 & = (1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3) ⋅ (1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3) & & \cr & = (1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3) ⋅ (1 ⋅ 1{0}^{2} + 2 ⋅ 10) + (1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3) ⋅ 3 & & \cr & = (1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3) ⋅ (1 ⋅ 1{0}^{2} + 2 ⋅ 10) + (3 ⋅ 1{0}^{2} + 6 ⋅ 10 + 9) & & \cr & = \mathop{\mathop{…}} & & }

This form splits the sums apart as well; we will cover that next.

Bear in mind that short-term memory is limited to seven to eight pieces of information. Structure mental arithmetic to keep as few pieces in flight as possible. One method is to break multiplication into stages. In long form, you can group the additions. For example, expanding 123 ⋅ 123 = 123 ⋅ (1 ⋅ 1{0}^{2}) + (123 ⋅ 23) = 123 ⋅ (1 ⋅ 1{0}^{2}) + (123 ⋅ 2 ⋅ 10 + 123 ⋅ 3),

 1 2 3 × 1 2 3 3 6 9 2 4 6 0 2 8 2 9 1 2 3 0 0 1 5 1 2 9

Assuming a small number uses only one slot in your short-term memory, need track only where you are in the multiplier, the current sum, the current product, and the next sum. That leaves three to four pieces of information to use while adding.

One handy trick for 15% tips: divide by ten, divide that amount by two, and add the pieces. We can use positional notation to demonstrate how that works,

\eqalignno{ x ⋅ 15% & = (x ⋅ 15)∕100 & & \cr & = ((x ⋅ (10 + 5))∕100 & & \cr & = ((x ⋅ 10) + (x ⋅ (10∕2)))∕100 & & \cr & = x∕10 + (x∕10)∕2 & & }

Digit-by-digit addition uses the commutative and associative properties:

\eqalignno{ 123 + 456 & = (1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3) + (4 ⋅ 1{0}^{2} + 5 ⋅ 10 + 6) & & \cr & = (1 + 4) ⋅ 1{0}^{2} + (2 + 5) ⋅ 10 + (3 + 6) & & \cr & = 579. & & }

Naturally, when a digit threatens to roll over ten, it carries to the next digit. Expanding the positional notation,

\eqalignno{ 123 + 987 & = (1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3) + (9 ⋅ 1{0}^{2} + 8 ⋅ 10 + 7) & & \cr & = (1 + 9) ⋅ 1{0}^{2} + (2 + 8) ⋅ 10 + (3 + 7) & & \cr & = 10 ⋅ 1{0}^{2} + 10 ⋅ 10 + 10. & & }

Because the coefficients are greater than b - 1 = 9, we expand those coefficients. Commuting and reassociating,

\eqalignno{ 123 + 987 & = 10 ⋅ 1{0}^{2} + 10 ⋅ 10 + 10 & & \cr & = (1 ⋅ 10 + 0) ⋅ 1{0}^{2} + (1 ⋅ 10 + 0) ⋅ 10 + (1 ⋅ 10 + 0) & & \cr & = 1 ⋅ 1{0}^{3} + 1 ⋅ 1{0}^{2} + 1 ⋅ 10 + 0 & & \cr & = 1110. & & }

However, when working quickly, or when the addition will be used in another operation, you do not need to expand the carries immediately. This is called a redundant representation because numbers now have multiple representations. You can represent 13 as 1 ⋅ 10 + 3 or simply as 13.

If you work that way mentally, you need to keep the intermediate results in memory. So during multiplying, you only need to work out the carries every three to four digits\mathop{\mathop{…}}

20.3.3 Subtraction

In systems with signed numbers, we know that subtracting a number is the same as adding its negation: a - b = a + (-b). So we expect the digit-by-digit method to work with each digit subtracted, and it does. Because - a = -1 ⋅ a, we can distribute the sign over the digits:

\eqalignno{ 456 - 123 & = (4 ⋅ 1{0}^{2} + 5 ⋅ 10 + 6) - (1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3) & & \cr & = (4 ⋅ 1{0}^{2} + 5 ⋅ 10 + 6) + (-(1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3)) & & \cr & = (4 ⋅ 1{0}^{2} + 5 ⋅ 10 + 6) + (-1 ⋅ 1{0}^{2} + -2 ⋅ 10 + -3) & & \cr & = (4 - 1) ⋅ 1{0}^{2} + (5 - 2) ⋅ 10 + (6 - 3) & & \cr & = 333. & & }

As with carrying, borrowing occurs when a digit goes negative:

\eqalignno{ 30 - 11 & = (3 ⋅ 1{0}^{1} + 0) - (1 ⋅ 1{0}^{1} + 1) & & \cr & = (3 - 1) ⋅ 1{0}^{1} + (0 - 1) & & \cr & = 2 ⋅ 1{0}^{1} + -1 & & \cr & = 1 ⋅ 1{0}^{1} + (10 - 1) & & \cr & = 1 ⋅ 1{0}^{1} + 9 & & \cr & = 19. & & }

Again, you can use a redundant intermediate representation of 2 ⋅ 1{0}^{1} - 1 if you’re continuing to other operations. And if all the digits are negative, you can factor out - 1,

\eqalignno{ 123 - 456 & = (1 ⋅ 1{0}^{2} + 2 ⋅ 10 + 3) - (4 ⋅ 1{0}^{2} + 5 ⋅ 10 + 6) & & \cr & = (1 - 4) ⋅ 1{0}^{2} + (2 - 5) ⋅ 10 + (3 - 6) & & \cr & = (-3) ⋅ 1{0}^{2} + (-3) ⋅ 10 + (-3) & & \cr & = -(3 ⋅ 1{0}^{2} + 3 ⋅ 10 + 3) & & \cr & = -333. & & }

20.3.4 Division and Square Root: Later

We will cover these later with number theory.

20.4 Homework

• Problem Set 3.1 (p154)
• 8, 16
• 32, 34, 35
• Problem Set 3.2 (p161)
• 3, 4, 5, 6, 8, 11, 20
• Problem Set 3.3 (p177)
• 10, 12, 20 (the zeros are indicators; find the least base where the sum is correct)
• Problem Set 3.4 (p188)
• 5
• 17 (this is Napier’s method; he made physical rods to accelerate the process)
• 19, 33