Notes also available as PDF.
What we will cover from Chapter 4:
And additionally, I’ll give a brief summary of computer arithmetic.
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:
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:
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:
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.
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.
Converting to decimal using decimal arithmetic is straight-forward. Remember the expansion of 1234 with base b = 10,
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,
We an use Horner’s rule to expand the polynomial in a method that often is faster,
Let’s try a binary example. Convert 110{1}_{2} to decimal:
Remember the rows of a truth table for two variables? Here,
To convert to binary from decimal, consider the previous example:
At each step, we find the largest power of two less than the remaining number. Another example for binary:
And in hexadecimal,
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.
Once we split a number into digits (decimal or binary), operations can be a bit easier.
We will cover multiplication, addition, and subtraction both
Properties of positional notation will help when we explore number theory.
We will use two properties frequently:
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,
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:
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,
Digit-by-digit addition uses the commutative and associative properties:
Naturally, when a digit threatens to roll over ten, it carries to the next digit. Expanding the positional notation,
Because the coefficients are greater than b - 1 = 9, we expand those coefficients. Commuting and reassociating,
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{…}}
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:
As with carrying, borrowing occurs when a digit goes negative:
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,
We will cover these later with number theory.