Number Systems and the Foundation of Computing
Initially, computers and computing devices were developed to deal with numbers. They later made their way into the realm of text handling and information processing. This is done through
encoding. When properly coded, all text can be represented as numbers—codes—and all ways of manipulating text can be accomplished through operations on those codes. Number systems and operations on numbers
are really a basic foundation of computing and modern computers.
We all know numbers, and the number system we have known since childhood is base-10, which is represented using 10 digits from 0 to 9. A base-10 number such as 2539867 can be written as
2 * 106 + 5 * 105 + 3 * 104 + 9 * 103 + 8 * 102 + 6 * 101 + 7 * 100
In general, an n-digit number dn−1dn−2…d1d0 (where n is any positive integer and each d ∈ [0, 1, 2, …, 9], where 0 < i < n ) in
a base-10 number system can be rewritten as
dn−1 * 10n−1 + dn−2 * 10n−2 + … + d1 * 101 + d0 * 100
In fact, a number system can be based on any whole number other than 0 and 1. There is a base-7 system for weeks, a base-12 system for the Chinese zodiac and imperial foot and inch, and a base-24 number
system for the 24-hour clock. A long list of different numbering systems that have appeared since prehistory can be found at https://en.wikipedia.org/wiki/List_of_numeral_systems.
In general, a base-Q number system will require Q unique symbols representing 0, 1, … Q−1, respectively. The base-10 equivalence of an n-digit base-Q number
dn−1dn−2…d1d0 can be represented as
dn−1 * Qn−1 + dn−2 * Q−2 + … + d1 * Q1 + d0 * Q0
The evaluation of the expression above will result in its base-10 equivalence. This is how we convert a number from base-Q to base-10.
For Q = 2, the numbers 0 and 1 are used to represent digits; for Q = 3, the numbers 0, 1, and 2 are used; for Q = 8, the numbers 0, 1, 2, 3, 4, 5, 6, and 7 are used; for Q = 16, the numbers 0, 1, 2, 3, 4, 5,
6, 7, 8, 9, a/A, b/B, c/C, d/D, e/E, and f/F are used.
The expression above also shows how to convert a number from base-10 to base-Q: divide the number by Q repeatedly, and the remainders will be the digits. The details of these conversions can be found on the
internet.
For a number dn−1dn−2…d1 d0 in a base-Q number system, it is often necessary to add Q as a subscription of the sequence, as shown below:
dn−1dn−2…d1d0Q or (dn−1dn−2…d1d0)Q
This explicitly indicates that the number is in a base-Q number system. For example, number
657 in a base-8 number system will be written as 6578 or (657)8, especially if the context does not indicate which number system the number is in.
All number systems have the same operations that we are already familiar with in a base-10 system, such as addition, subtraction, multiplication, and division. The only difference is that in a base-Q number
system, a 1 carried to or borrowed from a higher digit is equal to Q instead of 10.
For example, in a base-2 number system, 101 can be written as 1 * 22 + 0 * 21 + 1 * 20, and its 10-base equivalence is 1 * 4 + 0 + 1 = 5, and for 101 + 110, the operation is
101 + 110 ______ 1011 | 110 − 101 ______ 001 |
Given the four basic mathematical operations—addition, subtraction, multiplication, and division—it is very simple to prove that multiplication can be done by repeated addition, whereas division can be done
by repeated subtraction. Therefore, if you know how to do addition and subtraction and are able to count, you will be able to do multiplication and division as well.
More importantly, because a − b can be rewritten as a + (−b), you may be able to eliminate subtraction if you can represent −b without the minus sign. In a base-Q number system, (a − b) can be conveniently
handled through a + b′, in which b′ is the Q-complement of b representing (−b).
Given a negative number, −N, in which N is called the magnitude of −N, how do you get N′, the Q’s complement to N? It turns out to be very easy.
For a number N written as dndn−1…d0 in a base-Q number system, its Q-complement N′ is a number, also in a base-Q number system, such that N + N′ = Qn, and N′ can
be easily calculated in the following two steps:
- 1. For each di in dn−1dn−2…d0, find ti such that di + ti = Q−1, to get
tn−1tn−2…t0
- 2. Add 1 to tn−1tn−2…t0 to get N’s complement cn−1cn−2…c0
For b in a − b, if b has fewer digits than a, add 0s to the left of b to make up the missing digits before working on the above steps. For example, for 768 − 31, do 768 + (−31) or 768 + the 10’s
complement of 31.
To get 10’s complement of 31, first add one 0 to the front of 3 to get 031, then find out the 10’s
complement of 031, which is 968 + 1 = 969. Then do 768 + 969 to get 1737, and ignore the last carried digit, 1, to get 737, which is the result of 768 − 31.
It is easy to see that if C is N’s complement, then N is C’s complement as well. Using the notation given above, this can be written as (N′)′ = N.
What about floating-point numbers—that is, numbers with fractions, such as 3.1415926?
In a base-Q number system, a floating-point number can be represented much like integers, as shown below:
dn−1 * Qn−1 + dn−2 * Qn−2 + … + d1Q1 + d−1 * Q−1 + d−2 * Q−2 + … +
d−mQ−m
This may give us a hint that a floating-point number can be represented by two sequences of digits: one for the integer portion and the other for the fraction portion. If floating-point numbers are
represented this way in computers, addition and subtraction could be performed on the two portions separately, but with a mechanism to deal with carrying from the fraction to the integer in the case of
addition, and a mechanism to deal with borrowing from the integer to the fraction in the case of subtraction. This would be rather clumsy, and it would be even more clumsy when doing multiplication and
division.
In reality, floating-point numbers are represented in scientific notation, such as 1.3 * 102 in a base-10 or decimal system, where 1.3 is called the fraction, 2 is called the exponent, and 10 is
the radix. In a base-2 system, the radix would be 2.
In scientific notation, arithmetic operations on floating-point numbers can be easily done, especially if the fractions of all floating-point numbers are normalized—that is, if the number of digits before
the radix point is fixed for all floating-point numbers. For example, to perform the addition or subtraction of two floating-point numbers, all you need to do is shift the digits of one floating-point number
based on the difference of the two exponents, then perform addition or subtraction in the same way as on integers. More surprisingly, multiplying and dividing floating-point numbers in scientific notation is
much easier than adding and subtracting. There is no need to shift the digits because
a * rm * b * rn = a * b * rm+n
and
a * rm / b * rn = a / b * rm−n
All you need to build a computer capable of adding, subtracting, multiplying, and dividing in a base-Q number system is the ability to add and count, which is needed for multiplication and division. Moreover, counting itself can be done by addition when counting up or subtraction when counting down. This is very
encouraging.
The following discoveries are even more encouraging:
- • Many mathematical and scientific problems can be represented and reformulated based on the basic mathematical operations discussed above.
- • If we can build a computing device capable of doing basic mathematical operations, the machine can solve many computing and information processing problems.
The remaining question is how to make such a machine work faster. On a computing machine with only an addition and counting unit, if each step of an operation has to be enabled by a human, the
computation would be very slow because it would have to wait for the human to input instructions and data. To speed things up, the entire problem solving process needs to be automated. This requirement has
led to the introduction of memory to computing machines to store both the operating instructions (the program) and data needed during the computation. For the central processing unit (CPU) and memory (RAM) to
communicate and work together, a communication channel and control unit need to be added. For human users to communicate with the computing machine, input and output units are also needed. Together these
include everything described in Von Neumann’s architecture for modern computers.
Computability and Computational Complexity
Now comes the question of how powerful the computing machine described above can be. In particular, we should ask,
- • What problems can or cannot be computed with a computing machine?
- • How difficult is it to solve a given problem with a computing machine, assuming that the machine can take as many steps and use as much memory as needed to solve the problem?
Answering the first problem is the study of computability. Answering the second question is the study of computational complexity.
A well-known computability problem was raised by David Hilbert, a very famous German mathematician in the 19th century. The 10th problem in his list of 23 important mathematical problems he published in 1900
is the decidability problem, which is about finding an algorithm that can determine whether a Diophantine
equation such as xn + yn = zn, where n is an integer and greater than 2, has integer solutions. It was proved in 1970 that such an algorithm doesn’t exist, meaning that the
problem of deciding whether a Diophantine equation has integer solutions is unsolvable, or incomputable.
Between the 1930s and 1940s, before the existence of modern computers, Alan Turing invented a simple yet powerful abstract machine called the Turing machine. He proved that the abstract machine could
simulate the logic of any given algorithm and further determine whether an algorithm is computable. The operation of the machine will halt if the algorithm is incomputable. During the same time, computability
was also well studied by Alonzo Church based on lambda calculus. The two works later intertwined in a formal theory of computation known as the Church-Turing thesis.
In computer science, the computational complexity of an algorithm devised to solve a problem is about the number of resources—CPU time and memory, in particular—needed to run the algorithm on a computer. A
problem may be solved in different ways using different algorithms with different computational complexities. Sometimes it is necessary to find a better algorithm that runs faster and/or uses less memory.
The time required to run an algorithm is also related to the size of the problem to be solved. For example, finding someone in a classroom would be much easier than finding someone in a city. If you denote
the size of a problem with n, then in computer science, O(f(n))—called the big O of f(n)—is used to describe asymptotically the upper bound of running time: the time complexity of an algorithm for solving the
problem.
For example, assume you want to sort the numbers in a list. The size of the problem will be the number of numbers in the list. One algorithm is called selection sort, which begins with selecting the smallest
number from the list, then selecting the smallest number from the remaining of the list, and so on. Assume the size of the list is n. The first time it will need to do n − 1 comparisons. The second time it
will need n − 2 comparisons. When these are only two numbers left in the list, only one comparison is needed to finish. So the complexity of the algorithm in terms of the total number of comparisons needed
will be
(n − 1) + (n − 2) + (n − 3) … + 2 + 1 = (n − 1 + 1) / 2 * (n − 1) = n * (n − 1) / 2 = (n2 − n) / 2 = O(n2)
You may have noted in the big-O notation that we have kept only the highest-order term and have removed the constant ½ as well. This is because, with the big-O asymptotic notation, only the scale of
complexity increased when the size of the problem increases is of interest.
In computer science, problems can be classified as P (for polynomial), NP (for nondeterministic
polynomial), NP-complete, or NP-hard problems. A problem is said to be in P if it can be solved using a deterministic algorithm in polynomial time—that is, if the complexity is a big O of a polynomial. A
problem is said to be in NP if it can be solved with a nondeterministic algorithm in polynomial time. A problem is NP-complete if a possible solution can be quickly verified but there is no known algorithm to
find a solution in polynomial time. A problem is NP-hard if every NP problem can be transformed or reduced to it within polynomial time.
In the above, a deterministic algorithm refers to the one in which, given the same input, the output would always be the same, whereas a nondeterministic algorithm may give different outputs even for the
very same input.
The complexity of algorithms, which is closely related to the response and processing speed of programs and computer systems, is the concern of good programmers, especially when dealing with
resource-intensive applications. It is also an important topic to be studied in senior or graduate courses in computing and computer science. When writing a program or just a function for assignments or an
application, always think about the time and space complexity and ask yourself, Is there a better way to get the job done?
The Construction of Modern Computers
In general, computers can be categorized into two types: analog computers and digital computers. The computers in use today are almost all digital computers. But analog computers do have their
advantages.
Analog Computers
As a computing machine, an analog computer uses the properties of certain objects or phenomena to directly analogize the values of variables (such as the speed of a vehicle) of a problem to be
solved. Examples of the properties include the voltage and amperage of electricity, the number of teeth of a gear, or even the length of a wood or metal stick.
Analog computing machines were often built for some special purpose, with a very wide range of difficulties and complexities. A simple analog computer could be built with three gears for addition and
subtraction. For addition, using both operands to drive the third gear in the same direction will yield the sum of the two operands on the third gear, whereas for subtraction, the difference can be
calculated by driving the two gears in two different directions.
Historically, even as early as 100 BC, complicated analog computing machines were built for various applications, from astronomy in ancient Greece to the differential machine for solving differential
equations in the late 1800s and early 1900s. Some of the most complicated analog computing machines in
modern history include those for flight simulation and gunfire control. Analog computing machines continued well into the early age of modern digital computers because the special applications analog
computers were developed for were still too hard for digital computers in the 1960s or even 1970s.
Digital Computers
Different from analog computers, digital computers use sequences of digits to represent the values of variables involved in the problems to be solved. In digital computers, the machine
representation of a problem is often abstract, with no analogy to the original problem.
Theoretically, in accordance with the earlier discussion about general number systems, digital computers’ digits can be in any base, from 2 up. Hence a digital computer could be base-2, base-3, … base-10,
base-16, and so on. The digital computers we are using today are all base-2, or binary, computers, although it has been proved that base-3 computers would be even more efficient than base-2 computers.
This is because it is more convenient and cheaper to build components with the two easily distinguishable states needed to represent base-2 numbers.
Also, in a binary system, signed numbers can be naturally represented using the highest sign bit: 0 for positive numbers and 1 for negative numbers, for example. Moreover, the addition and subtraction of
signed binary numbers can be easily done by using 2’s complements to represent negative numbers.
For example, to do −2−3, we would do
or
(−00000010)b + (−00000011)b
Next, we need to convert (−00000010)b and (−00000011)b into their 2’s complement representations. According to the two steps we described in the section above, “Number Systems and the
Foundation of Computing,” with Q = 2, you first get 1’s complement of the magnitude of each negative number above by flipping each bit, then adding 1 to 1’s complement, as shown below:
(00000010)b (1’s complement by flipping each bit) → (11111101)b (then + 1) → (11111110)b
(00000011)b (1’s complement by flipping each bit) → (11111100)b (then + 1) → (11111101)b
The addition above will become
(11111110)b + (11111101)b
which is equal to
The 1 on the highest bit of the result means that the result is 2’s complement representation of a negative number. Interestingly, the magnitude of the negative number is the complement of
(11111011)b, which is
(11111011)b (1’s complement by flipping each bit) → (00000100)b (then + 1) → (000000101)b,
which is 5, meaning that the result of −2−3 is −5.
It is very easy to calculate the 2’s complement of a binary number. Adding a negative number can be done by adding its 2’s complement. That is the advantage that the binary system has offered for the
construction and development of modern digital computers.
As such, in principle, the key component needed in our modern digital computers for computing and information processing is a unit to add two binary numbers, since the three other basic arithmetic
operations can be done based on addition, using respective algorithms or routines such as the ones mentioned above. In the real implementation and construction of digital computers, all basic arithmetic
operations, including bitwise operations on integer binary numbers such as the operations needed to find 2’s complements, are hardwired into a unit called the arithmetic logic unit (ALU), which is the core
of the central processing unit (CPU) that you have heard about often.
A digital computer also needs to compute real or floating-point numbers as well as process graphics. To get these two jobs done more efficiently, modern computers also have a floating-point unit (FPU) for
floating-point numbers, and a graphics processing unit (GPU) for graphics.
Mechanic-Based Components
Mechanical components such as levels, gears, and wheels can be used to build analog computers. In fact, digital computers can also be built with mechanical components. The earliest
special-purpose mechanic-based digital computer was the difference engine designed by Charles Babbage. A general-purpose mechanic-based digital computer, called the analytical engine, was also first
proposed by Charles Babbage. In the design, the machine has memory and CPU. It would have been programmable and, therefore, would have become a general-purpose digital computer, if ever actually built.
Vacuum Tube–Based Components
Invented in 1904 by John Ambrose Fleming of England, a vacuum tube is a tube made of glass with gas/air removed, with at least two electrodes inserted for allowing or controlling the flow of
electrons. Vacuum tubes can be made to be switches or amplifiers. As switches, the two states of on and off can be used to represent the 0 and 1 of binary arithmetic or Boolean logic. When the state of
output can be controlled by input or inputs, the switch is made to be a gate to perform different logical operations. That’s how vacuum tubes could be used to implement modern computers; as amplifiers, they
found their uses in many electronic devices and equipment such as radio, radar, television, and telephone systems. It was the vacuum tube that made electronic computers and other electronic devices possible
for the first time. Vacuum tubes played very important roles in the development and construction of all electronic devices and systems in the first half of the 20th century.
However, vacuum tubes disappeared from computers and most other electronic devices soon after transistors were developed at the Bell Laboratories by John Bardeen, Walter Brattain, and William Shockley in
1947 because, compared to transistors, vacuum tubes were too big, too heavy, too unreliable and consumed too much power to operate. That limited the construction and uses of vacuum tube–based computers and
devices.
Transistors
Recall that in the construction of computers, the ALU or CPU requires two-state switches to represent 0 and 1 and logical gates to perform additions and subtractions of binary number systems.
Vacuum tubes could be made to construct electronic computers, but the computers became too bulky and too heavy to be more useful.
Integrated Circuits and Very Large-Scale Integrated Circuits
Integrated circuits (ICs) are chips with many electronic circuits built in, while very large-scale integrated (VLSI) circuits are those with millions and even billions of electronic circuits
built into very small semiconductor chips. According to Moore’s law (attributed to Gordon Moore, the cofounder and former CEO of Intel), the number of transistors in a dense integrated circuit doubles about
every two years. This has been the case over the last few decades since 1975, though advancement in VLSI technology has slowed since 2010.
Today, computers are all using VLSI chips. That is why computers have become smaller and smaller, while computing power has increased exponentially in accordance with Moore’s law.