We all know arithmetic — numbers, addition, subtraction, multiplication, division, and so forth — from school. Unfortunately, that does not do us much good when we deal with computers. Computers use different numbers, and different arithmetic, than we do. This section is about numbers and arithmetic as these are understood by computers.
Here in people land, we use what is called decimal numbers. These numbers are written with ten symbols: 0 1 2 3 4 5 6 7 8 and 9. We write numbers as a sequence of digits using what is called radix 10 positional notation: the digit string “123” is interpreted as 1×102 + 2×101 + 3×100 = 100 + 20 + 3, or 123. When we use numbers other than integers, we frequently use either rational numbers (such as “3 1/16 inches”) or what is called fixed point representation (such as $7.15, but generally not $7.151).
In computer land, most computers use binary numbers. These numbers are written with two symbols: 0 and 1. These numbers are represented in radix 2 positional notation: the digit string “1111011” is interpreted as 1×26 + 1×25 + 1×24 + 1×23 + 0×22 + 1×21 + 1×20 = 64 + 32 + 16 + 8 + 0 + 2 + 1 = 123. (What a coincidence!) When computers use numbers other than integers, they frequently use what is called floating point representation. This representation has a fractional part, such as .111101102, and an exponent part, such as 01112 (7 in decimal). The value of such as number is the fractional part, times two to the exponent part, or in this case .111101102×27, or 1111011.02, or 123 (again, pure coincidence). The fraction and the exponent parts can be positive or negative, independently of one another.
The calculator uses decimal numbers, but floating point representation. Each number is a fraction times a power of ten: 1.230×102, or 123.0.
There are two things to understand about computer numbers: firstly, they are limited in the number of digits they can use. Secondly, they are (frequently) binary.
The number of square centimeters in a square mile is exactly expressible in decimal, because all the numbers going into it — 5280 feet per mile, 12 inches per foot, and 2.54 centimeters per inch — are exactly expressible in decimal. However, a binary number cannot exactly represent the fraction 0.36. In binary, 0.36 is the repeating fraction 0.010111000010111000010111000... It repeats with a period of nine binary digits. The number 0.1 is also not exactly expressible in binary: it is .0001100110011... It repeats with a period of four binary digits. The closest a 24-bit precision number can get to 0.1 is 13421773/134217728, or about 0.100000001490116.
If you start with 0, and keep adding 0.1, then in decimal arithmetic you will (after ten such additions) reach exactly 1. In binary arithmetic, you will never reach exactly 1 — you will get very close to 1 (about 1.000000015 in single precision), and keep going.
This is not a defect in the binary number system. Our decimal number system has exactly the same problem. Represent 1/15 exactly in decimal. Ready? 0.0666666666666666... Are you tired yet? How about 1/7? 0.142857142857142857... Every number base has fractions it cannot represent exactly. In general, a number system can exactly represent fractions for which the denominator has only factors shared with the base of the number system. Base 12, for example, can exactly represent 1/2 (0.612), 1/3 (0.412), 1/4 (0.312), and 1/6 (0.212), but not 1/5 (0.24972497...12).
Let’s go back to starting at 0, and repeatedly adding 0.1. Even though we never get 1 exactly, we do get close. An unexpected thing, though, is that if we keep going, eventually (around 4194304 in single precision), adding 0.1 will quit making a difference, and the number will stay the same after that.
What’s that, you say? Zero, not one-tenth, is the additive identity? How can a+b, with b non-zero, be the same as a? Let’s do that addition the computer way: with 24 binary digits in our numbers, rounding up when the first dropped digit is 1.
4194304: 1000000000000000000000.00 0.1: 0.000110011001100110011001101 Sum: 1000000000000000000000.00
Yes, that is right. When a human adds 4194304 and 0.1, the human gets 4194304.1. The computer gets 4194304. Day to day arithmetic has the property that (a + b) – a = b; computer arithmetic does not. If b is very small compared to a, (a + b) – a = 0.
Let us look at another computer operation: 2097152, plus 0.1, minus 2097152. The answer we expect is 0.1, or 1/10. Let us see what we actually get:
2097152: 100000000000000000000.000 0.1: 0.000110011001100110011001101 Sum: 100000000000000000000.001 (rounding, remember!) 2097152: 100000000000000000000.000 Difference: 0.00100000000000000000000000
So 1/10 becomes 1/8, an error of one part in four — this in arithmetic that has 24 binary digits, capable of representing one part in 16777216. This is the result of what is called cancellation or loss of significance: when two numbers are very close together, their difference will have only a few digits of meaning.
All these effects are summed up in what is called round-off error. When the number of digits needed to exactly represent the result of an operation exceeds the number of digits available, the answer generated is approximate. How approximate will the answer be? That depends on the data and the computations — and is the subject of an entire field of study called numerical analysis.
Integers are more or less safe — as long as we keep within the range of numbers that can be represented. Oddly, multiplication and division are also more or less safe. We will occasionally nod to numerical analysis: we may compute subintervals of a to b, for example, as a + m(b-a)/n or ((n-m)a + mb)/n rather than repeatedly adding (b-a)/n to a. Mostly, however, we will ignore all the odd effects we just described.
There are two exceptions to this rule of simply ignoring round off. The first is when we have what is called a “stiff” problem. This means that small changes in the input result in large changes in the output. In this case, we pay strict attention to round off, with the goal of minimizing its effects. The second exception is when we depend upon round off, particularly to terminate what would otherwise be an infinite process.
Many functions are best computed through an infinite process. For example, the exponential function, ex, can be computed as the power series:
This is an infinite sum, and so would take an infinite time to calculate. However, the sum can be terminated early by waiting until two successive partial sums:
have the same value, due to round-off error. At that point, further terms would also make no difference in the computation, and there is no value in computing them. The last computed sum, Sj, can be used as the value of the exponential function.
Copyright © 2001 Brian Hetrick
Page last updated 30 December 2001.
Building Blocks I
Control Flow II
A First Program
Data Structures I
Building Blocks II
Data Structures II