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×10^{2} + 2×10^{1}
+ 3×10^{0} = 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×2^{6} + 1×2^{5} + 1×2^{4}
+ 1×2^{3} + 0×2^{2} + 1×2^{1} +
1×2^{0} = 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
.11110110_{2}, and an exponent part, such as 0111_{2}
(7 in decimal).
The value of such as number is the fractional part, times two to the
exponent part, or in this case .11110110_{2}×2^{7},
or 1111011.0_{2}, 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×10^{2},
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.

We here in people land can write use very precise numbers. A square mile is exactly 25899881103.36 square centimeters (in case you ever need to know that), but this number has 13 digits. The calculator is limited to 12 decimal digits — it actually uses 15, but the last three are “fuzzy.” A single precision number in Visual Basic for Applications has effectively 24 bits of precision, equivalent to about 7.22 decimal digits. Double precision numbers in Visual Basic for Applications, and numbers in JavaScript, use more bits and could represent the number of square centimeters in a square mile — except for the small matter of 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.6_{12}),
1/3 (0.4_{12}), 1/4 (0.3_{12}), and 1/6 (0.2_{12}),
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, *e*^{x},
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, *S*_{j}, can be used
as the value of the exponential function.

Finally, there is the matter of representing numbers.
The numbers used in computers come in two flavors, integers and
floating-point numbers.
Luckily, the days of having to enter numbers in binary are past: we
can use decimal representation.
However, it is inconvenient to enter, say, Avogadro’s number
(6.02×10^{23}) as 602000000000000000000000 —
instead of just looking at the exponent, we would have to count the
zeroes.
So the symbol “E” is used in numbers to indicate “times
ten to the power.”
6.02×10^{23} is then represented as 6.02E23.
In JavaScript and Visual Basic for Applications, the letter E is used
for both input and output.
In the calculators, the EXP key is used for exponent entry, and this
is displayed as a small capital E.
The E indicating the tens’ exponent may also be followed by a
sign (+ or – in JavaScript and VBA, or the (-) [change sign] key in
the calculator).
This allows both very large and very small numbers to be entered.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 30 December 2001.

Tutorial

Building Blocks I

Numbers

Control Flow II

Basic I/O

Algorithms

A First Program

Answers

Modularization

Data Structures I

Recursion

Program Attributes

Building Blocks II

Algorithm Analysis

Structuring

Data Structures II

Abstract Types

Objects

Problem Analysis

Reference Card