History of the Binary System

The Binary System of numeration is the simplest of all positional number systems. The base - or the radix - of the binary system is 2, which means that only two digits - 0 and 1 - may appear in a binary representation of any number. The binary system is of great help in the Nim-like games: Plainim, Nimble, Turning Turtles, Scoring, Northcott's game, etc. More importantly, the binary system underlies modern technology of electronic digital computers. Computer memory comprises small elements that may only be in two states - off/on - that are associated with digits 0 and 1. Such an element is said to represent one bit - binary digit.

The first electronic computer - ENIAC which stood for Electronic Numerical Integrator And Calculator - was built in 1946 at the University of Pennsylvania, but the invention of the binary system dates almost 3 centuries back. Gottfried Wilhelm Leibniz (1646-1716), the co-inventor of Calculus, published his invention in 1701 in the paper Essay d'une nouvelle science des nombres that was submitted to the Paris Academy to mark his election to the Academy. However the actual discovery occurred more than 20 years earlier.

According to the Oxford Encyclopedic Dictionary (see Earliest Known Uses of Some of the Words of Mathematics), an entry BINARY ARITHMETIC first appeared in English in 1796 in A Mathematical and Philosophical Dictionary.

Binary numbers are written with only two symbols - 0 and 1. For example, a = 1101. Since symbols 0 and 1 are also a part of the decimal system and in fact of a positional system with any base, there's an ambiguity as to what 1101 actually stands for. To avoid confusion, the base is often written explicitly, like in a = (1101)2 or b = (1101)10. In the decimal system, 1101 is interpreted as 1 thousand 1 hundred 1, which is just a sum of powers of 10 with coefficients that are the digits of the number. More accurately,

(1101)10 = 1·103 + 1·102 + 0·10 + 1

To represent numbers, the decimal system uses the powers of 10, whereas the binary system uses in a similar manner the powers of 2.

(1101)2 = 1·23 + 1·22 + 0·2 + 1

The numbers are different. In fact,

(1101)2 = 8 + 4 + 1 = 13    ( = (13)10.)

There are several problems with using more than one number system at the same time. Should we read (1101)2 as 1 thousand 1 hundred 1 in binary? Or, after some mental calculations, just 13 without mentioning the base? The latter possibility is overtaxing and unreasonable: why to use a system other than the decimal in writing while depending on the decimal in speech? The former is inappropriate altogether for etymological reasons. We might say thousand to indicate a 1 in the fourth position from the right regardless of the base of the system in use, but this would conflict with the etymology of the word thousand, and the same is true of the word hundred. Both are related to the base 10 and no other.

In Words of Mathematics we find the following entries:

hundred (numeral): a native English compound. The first element, hund, actually means "ten." It comes from dekt-tom, an extension of the more basic Indo-European root dekm "ten." The second element is from the Old English rad "number", so that hundred means literally the "tens-number" in the sense that it is ten times ten.

and

thousand (numeral): actually an English compound, thus-hund. The first component is related to English thumb and thigh, and means "swollen, large." The Indo-European root is teu- "to swell." Related borrowings from Latin are tumor and tumulus. The second component is the root found in hundred (q.v.), which is based on the Indo-European root dekm- "ten." The literal meaning of thousand is "a swollen or big hundred" because it is ten times a hundred.

So how does one read (1101)2? In practice, the not-so-glamorous "one one zero one" does a reasonably good job. One adds the word "binary" if the meaning is not clear from the context. This is probably close to the Ancients' usage. Just think of how the Romans pronounced, say MCMLXXXII?

Now let me ask a couple of deceptively simple questions. Is it true that every number has a binary representation? And if so, is the binary representation of a number unique?

Here's one possible answer. For a given number, there exists an algorithm that outputs its binary representation. Therefore every number has a binary representation. Since the algorithm is reversible, the binary representation defines the number uniquely. (The algorithm works for integers. Another one works for fractions.)

There is a problem though. The algorithm assumes that the given number has been already somehow represented, so that it receives one representation of the number and outputs another. If the original number was decimal, the algorithm performs conversion between its decimal and binary representations. It appears that the answer we gave in the preceding paragraph is conditional: if a number has a decimal representation, it also has a binary representation. If the former is unique, so is the latter.

However, does every number have a decimal representation? To be more specific, does every counting number have a decimal representation? This question is either silly or plain artificial. For is it not how we count the numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, and so on. Who would doubt that in this manner we count all numbers? This is in fact the definition of counting numbers (The Penguin Dictionary of Mathematics):

counting number a number used in counting objects; i.e. one of the set of positive integers: 1, 2, 3, 4, an so on.

The sample sequence is short, but of course the intention is to the sequence of decimal representations: 1, 2, 3, 4, ..., 10, 11, 12, ... We count the numbers sequentially and, as we go along, we give them names according to certain rules. Those rules are the basis of the positional (decimal) system representation:

  1. Use decimal symbols 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 (in a cyclic order).
  2. Decimal representations of numbers during their counting change with the right-most digit changing the fastest.
  3. Whenever a digit becomes 0, its neighbor to the left is replaced with its successor in the sequence of decimal symbols. If necessary, this step applies recursively.
  4. If need be, i.e. whenever the left-most digit becomes 0, 1 is prepended to the previous representation.

With the relevant rule noted in parentheses, let's count and see how the rules apply: 1, 2 (#2), 3 (#2), ..., 8 (#2), 9 (#2), 10 (##3-4), 11 (#2), ..., 18 (#2), 19 (#2), 20 (#3), ..., 98 (#2), 99 (#2), 100 (#3-4, one recursion), ...

The question of what a (counting) number is is quite delicate. Numbers can be defined axiomatically, which guarantees their existence independent of any naming convention. Numbers may also be thought of as collections of drum beats we produce while counting: one drum beat per count. Naming them was a great human invention. Naming them according to a positional system of numeration was probably a single most important mathematical achievement over the space of some 1000 years.

Whether one may skip a number while tapping a drum may deserve a philosophical discussion. I assume this is not possible. Rules 1-4 guarantee that all possible (decimal) number names will eventually be assigned in proper order. Going one step further with this line of reasoning, I claim that any positional numeration is exhaustive in the sense that any (counting) number has a unique representation in every base and any such representation corresponds to a certain number. Rules 1-4 must of cause be adapted to a specific base of numeration. In particular, the naming rules for the binary system appear as

  1. Use binary symbols 1, 0 (in a cyclic order).
  2. Binary representations of numbers during their counting change with the right-most digit changing the fastest.
  3. Whenever a digit becomes 0, its neighbor to the left is replaced with its successor in the sequence of binary symbols. If necessary, this step applies recursively.
  4. If need be, i.e. whenever the left-most digit becomes 0, 1 is prepended to the previous representation.

The binary counting then goes thus: 1, 10 (##3-4), 11 (#2), 100 (##3-4, one recursion), 101 (#2), ..., 111 (#2), 1000 (##3-4, 2 recursions), ...

The foregoing discussion presents a longwinded argument to the effect that there is not that much difference between the decimal and the binary systems. Decimal representations are shorter than their binary counterparts, but, as far as the counting process is concerned, the name assignment follows essentially the same rules.

Binary representation, just because it only uses two digits has an interesting interpretation. Binary representation of a number is a sum of powers of 2. A power of two is included into the sum if the corresponding digit in the representation is 1. For example,

(13)10 = (1101)2 = 23 + 22 + 20.

The fact that every number has a unique binary representation tells us that every number can be represented in a unique way as a sum of powers of 2. I wish to give an independent proof due to L. Euler (1707-1783) [Dunham, p 166] of the latter result.

Euler was a master of infinite series and products. Their theory have been developed in the 19th century, but Euler used them with great skill a century earlier to obtain many remarkable results. So, here's one example.

Let P(x) = (1 + x)(1 + x2)(1 + x4)(1 + x8)..., which is an infinite product. Multiplying out the terms of the product results in an infinite series:

(1 + x)(1 + x2)(1 + x4)(1 + x8)... = 1 + αx + βx2 + γx3 + δx4 + ...

where the coefficients α, β, γ, δ, ... are yet to be determined. Note that

P(x)/(1 + x) = (1 + x2)(1 + x4)(1 + x8)...

which is just P(x²). In other words,

P(x) = (1 + x)(1 + αx2 + βx4 + γx6 + δx8 + ...)

Cross-multiplication yields another identity

P(x) = 1 + x + αx2 + αx3 + βx4 + βx5 + γx6 + γx7 + ...

Compare this with the original expansion P(x) = 1 + αx + βx2 + γx3 + δx4 + ... As with finite polynomials, if two series are equal, their coefficients must coincide termwise. Wherefrom we obtain, α = 1, β = α, γ = α δ = β ε = β, ... which means all the coefficients in the expansion of P(x) are equal to 1. Therefore,

(1 + x)(1 + x2)(1 + x4)(1 + x8)... = 1 + x + x2 + x3 + x4 + x5 + ...

But what is the meaning of coefficients α, β, γ δ, ε, ...? Each tells us in how many ways the corresponding term (a power of x) can be obtained as the product of powers of x with exponents 1, 2, 4, 8, 16, ... Since, xaxb = xa + b and all the coefficients were found to equal 1, this is the same as saying that every (counting) number - exponents on the right - have a unique representation as a sum of powers of 2.

References

  1. W. Dunham, Euler: The Master of Us All, MAA, 1999
  2. S. Schwartzman, Words of Mathematics: An Etymological Dictionary of Mathematical Terms Used in English, MAA, 1994

Related material
Read more...

  • Expansion of Integers in an Integer Base
  • Base (Binary, Decimal, etc.) Converter
  • Base Converter
  • Implementation of Base Conversion Algorithms
  • Conversion of Fractions in Various Bases
  • Scoring: the simplest of the impartial games
  • Calculation of the Digits of pi by the Spigot Algorithm of Rabinowitz and Wagon
  • Addition and Multiplication Tables in Various Bases
  • |Contact| |Front page| |Contents| |Algebra|

    Copyright © 1996-2017 Alexander Bogomolny

     62644054

    Search by google: