Ancient Wisdom: Unary and Binary

One of the key insights in problem solving is that we don't have to stick with the representation in which we encounter a problem. Instead, we can always seek a more useful, equivalent representation of the same problem. Indeed, one of the keys to computer science is finding the right representation to solve a given problem. Don't let the problem choose the representation.

Number Representations

We can view numbers in many different, but corresponding ways. It's important to understand the relationship between different representations of the same idea. Let's take a historical view of these abstract representations.

Dating back to about 30,000 B.C., we can find evidence of counting and numbers in scratch marks on bones. Paleolithic people used one scratch or mark to represent 1, two marks to represent 2, three marks to represent 3, four marks to represent 4, and so on. There is only one symbol—the mark. Hence, we can call these representations unary numbers.

1: ●
2: ● ●
3: ● ● ●
4: ● ● ● ●

However, isn't unary too literal to be a representation? Does it deserve to be viewed as an "abstract" representation? In fact, it is important to respect the status of each representation, no matter how primitive. Unary is a perfect lesson. For certain problems, it is the right representation and helps illustrate the value of visual proofs.

Dot Proofs

Consider the problem of finding a formula for the sum of the first n numbers. We have previously used induction to verify that the answer is .

Here is the standard high school algebra proof.

The same argument can be restated using a unary representation, where the sum is represented as a triangular array of dots.

● ● ● ● ● ●
● ● ● ● ●
● ● ● ●
● ● ●
● ●
●
n . . . . . 2 1

Similarly, we can represent the sum as a second array of dots.

● ● ● ● ● ●
● ● ● ● ● ○
● ● ● ● ○ ○
● ● ● ○ ○ ○ n+1
● ● ○ ○ ○ ○
● ○ ○ ○ ○ ○
○ ○ ○ ○ ○ ○
n

We then combine the two triangles to form a rectangle in which each row contains dots and each column contains dots, for a total of dots in the grid. Because this total is , we can conclude that the sum of the first n numbers is:

The unary representation brings out the geometry of the problem and makes each step look very natural.

Here is another example. Recall that the nth triangular number, , is:

We can use a dot argument to show that the nth square number, , equals the sum of the two consecutive triangular numbers and :

● ● ● ● ● ●
● ● ● ● ● ○
● ● ● ● ○ ○
● ● ● ○ ○ ○ n
● ● ○ ○ ○ ○
● ○ ○ ○ ○ ○
n

Let's take another look at square arrays of dots, breaking up the pattern in an alternative way.

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ○ ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ○ ○ ● ● ● ● ○ ● ● ●

● ● ● ● ● ● ● ● ● ● ○ ○ ○ ● ● ● ● ○ ● ● ● ● ○ ● ●

● ● ● ● ● ○ ○ ○ ○ ● ● ● ● ○ ● ● ● ● ○ ● ● ● ● ○ ●

○ ○ ○ ○ ○ ● ● ● ● ○ ● ● ● ● ○ ● ● ● ● ○ ● ● ● ● ○

From the sequence of diagrams, it is evident that . The sum of the first five odd numbers is 5 squared. We can conclude that the sum of the first n odd numbers is .

Here is an alternative dot proof of the same sum, involving square and triangular numbers. Recall that .
○ ○ ○ ○ ●
○ ○ ○ ● ●
○ ○ ● ● ●
○ ● ● ● ●
● ● ● ● ●

We can rearrange the dot diagram to get the following configuration.
○
○ ○
○ ○ ○
○ ○ ○ ○
●
● ●
● ● ●
● ● ● ●
● ● ● ● ●

○
○
○ ○
○ ○
● ○ ○
● ● ○
● ● ● ○
● ● ● ●
● ● ● ● ●
9 7 5 3 1

Notice that each column now contains an odd number of dots. Hence, the sum of the first n odd numbers is the nth square number.

We can also demonstrate the same relationship involving the sum of odd numbers using simple algebraic notation.

Now, we can apply the relationship to another interesting problem. In this case, instead of drawing square arrays of dots, we can simply use areas.

Consider the area of a square that has width . Suppose that we enlarge the square so that its width is now .

The area of the new square is . The difference in area between the new square and the old square is or, in terms of the pieces added to the old square, .

Hence, the new area can be expressed as . But itself can be expressed as . So,

and so on. In general,

or

We saw earlier that

This means that

Thus, we now have a formula for the first n cubes.

Exercise

Find a formula for the sum of the first n squares. The Babylonians needed this sum to compute the number of blocks in their pyramids and other structures.

A Brief History of Number Representations

Unary is cumbersome, especially when we get to large numbers. The ancients grappled with problems of abstraction in representation and reasoning. Let's look back to the dawn of symbols.

Sumerians [modern Iraq]

• 8000 BC Sumerian tokens use multiple symbols to represent numbers
• 3100 BC Develop cuneiform writing
• 2000 BC Sumerian tablet demonstrates:
  • base 10 notation (no zero)
  • solving linear equations
  • simple quadratic equations

Biblical timing: Abraham born in the Sumerian city of Ur.

Babylonians absorb Sumerians

• 1900 BC Sumerian/Babylonian tablet
  • Sum of first n numbers
  • Sum of first n squares
  • "Pythagorean theorem"
  • "Pythagorean triples", e.g., 3-4-5
  • some bivariate equations

• 1600 BC Babylonian tablet
  • Take square roots
  • Solve system of n linear equations

Egyptians

• 6000 BC Multiple symbols for numbers
• 3300 BC Developed hieroglyphics
• 1850 BC Moscow papyrus
  • Volume of truncated pyramid

• 1650 BC Rhind papyrus [Ahmes/Ahmose]
  • Binary multiplication/division
  • Sum of 1 to n
  • Square roots
  • Linear equations

Biblical timing: Joseph is governor of Egypt.

Harrappans [Indus Valley Culture], Pakistan/India

• 3500 BC Perhaps the first writing system?!
• 2000 BC Had a uniform decimal system of weights and measures

China

• 1200 BC Independent writing system (surprisingly late)
• 1200 BC I Ching [Book of Changes]
  • Binary system developed to do numerology

The Rhind Papyrus

The Rhind papyrus, dating to about 1650 B.C., is one of the oldest mathematical documents in existence, It was found in 1858 in Egypt by a Scottish antiquary named A. Henry Rhind, and it is now in the British Museum. It remains our main source of information as to how the ancient Egyptians counted, reckoned, and measured.

The document had been prepared by a scribe named Ahmose (or Ahmes), probably copied from an older manuscript. It is a collection of mathematical exercises and practical examples, along with a table of the division of 2 by odd numbers from 2/3 to 2/101. It begins somewhat cryptically as follows:

Correct method of reckoning, for grasping the meaning of things and knowing everything that is, obscurities and all secrets.

The Rhind papyrus contains about 85 problems, exhibiting the use of fractions, the solution of simple equations and progressions, and the measurement of areas and volumes. Here is one of the problems.

A man has seven houses, Each house contains seven cats, Each cat has killed seven mice, Each mouse had eaten seven ears of spelt, Each ear had seven grains on it. What is the total of all of these?

Solving this problem requires calculating the sum of the first five powers of 7.

Egyptian Multiplication

Egyptian arithmetic was essentially additive. The ancient Egyptians reduced multiplication and division to repeated additions and subtractions. The only multiplier they used, with rare exceptions, was 2. They did larger multiplications by successive duplications.

To multiply 19 by 6, for example, the Egyptians would double 19, double the result, and add the two products, as shown below.

	1	19
\	2	38
\	4	76
Total	6	114

The symbol "\" designates the sub-multipliers that add up to the total multiplier, in this case 6. In effect, this is a very early use of binary arithmetic. We can think of the Egyptian method as writing one of the two numbers being multiplied in base 2.

Example

In the Rhind papyrus, multiplying 23 by 27 would look like this:

\	1	27
\	2	54
\	4	108
	8	216
\	16	432
Total	23	621

Exercise

Use Egyptian multiplication to calculate 15 times 5.

Alphabets and Bases

Over millennia, different societies have chosen to use number systems with different bases. The Sumerians and Babylonians worked in bases 10, 60, and 360. The Egyptians used base 2, 3, 7, 10, and 60. African cultures have used number systems in base 5 and 10. The French numbering system relies on base 10 and 20, while the English numbering system works with base 10, 12, and 20.

To understand better how the ancient Egyptians represented numbers and solved arithmetic problems, largely in base 2, we need to look at some fundamental concepts involving symbols and the representation of numbers. We will also discover some striking advantages of the system used by the Egyptians.

One key relationship that we will be using is the geometric series.

For , we get

.
For , we get .
For , we get

One calculation that arises frequently is the following:

Note that multiplication by x is a shift; each exponent increases by 1:

These relationships are important when changing from one representation to another.

Numbers and their properties can be represented as strings of symbols. We take the ideas of symbol and sequence of symbols as primitive. Indeed, all of our representations are usually strings of symbols.

Let Σ be any fixed finite set of symbols. Σ is called an alphabet, or a set of symbols. Here are some examples of such alphabets:

• Σ={0,1,2,3,4}
• Σ={a,b,c,d,...,z}
• Σ= all typewriter symbols
• Σ= {, §, Щ, . . ., ۩}

A string is a sequence of symbols from Σ. Let s and t be strings. Then st denotes the concatenation of s and t; in other words, the string obtained by the string s followed by the string t. For example, if s = ab and t = bcd, st = abbcd.

Now define Σ+ by these inductive rules:

• x∈Σ⇒x∈Σ+
  
• s,t∈Σ+⇒st∈Σ+

Intuitively, Σ+ is the set of all finite strings that we can make using at least one letter from Σ.

We can go one step further by defining the set Σ*. We start by defining ε to be the empty string; in other words, the string xεy=xy for all strings x and y. We can also call ε the string of length 0. Then consider these inductive rules:

• ε∈Σ*
• s∈Σ, t∈Σ*⇒st∈Σ*

Intuitively, Σ*; is the set of all finite strings that we can make using letters from Σ, including the empty string.

Let's look at some examples.

Let DIGITS = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} be a symbol alphabet. Any string in DIGITS+ will be called a decimal number.
Let BITS = {0, 1} be a symbol alphabet. Any string in BITS+ will be called a binary number.
Let ROCK = {●} be a symbol alphabet. Any string in ROCK+ will be called a unary number.
Let BASE-X = {0, 1, 2, . . . , x – 1} be a symbol alphabet. Any string in BASE-X will be called a base-x number.

How do we go from numbers represented in one alphabet to numbers represented in another alphabet? We need to specify the map between sets of sequences and numbers. We can define these functions inductively.

To go from sequences of unary numbers to natural numbers:
      Inductively defined function f: ROCK+ →ℕ
      f(●)=1
      f(●x)=f(x)+1

To go from sequences of binary numbers to natural numbers:
      Inductively defined function f: BITS+ →ℕ
      f(0)=0; f(1)=1
      If |W|>1 then W=xb (b ∈ BITS)
      f(xb)=2f(x)+b

We can also express a sequence of binary numbers as a natural number non-inductively using the following relationship:

The symbol is called the "least significant" bit (or the "parity" bit), and if and only if is an even number.

Hence, we have two different ways of writing the same thing; in other words, two identical maps from sequences to numbers. At any given time, one form may be more useful or convenient to use than the other.

We next prove that each natural number has a representation as a binary number.

Theorem

Each natural number has a binary representation.
Base case: 0 and 1 do.
Induction hypothesis: Suppose all natural numbers less than n have a binary representation. Note that n=2m+b for some m<n,b = 0 or 1 (odd or even). Represent n as the left-shifted sequence for m concatenated with the symbol for b.
Note that a binary string that is either 0 or 1 or has length > 1 and does not have a leading zero belongs to NLZB (no leading zero binary). For example, 0, 1, 10, 100000001, and 1110000 are in NLZB. The binary numbers 01, 000001010111, and 0111111111 are not in NLZB.

Theorem

Each natural number has a unique NLZB representation.

Base case: 0 and 1 do.
Induction hypothesis: Every natural number less than n has a unique NLZB binary representation. Suppose n=2m+b has two NLZB representations W and V. Their parity bit b must be identical. Hence, m also has two distinct NLZB representations, which contradicts the induction hypothesis. So n must have a unique representation.
This can be generalized to any base x. So,

represents the number

We can write, for instance, that .

Examples

In base 2 (binary), 101 represents or, in unary, ● ● ● ● ●.

In base 7, 015 represents or, in unary, ● ● ● ● ● ● ● ● ● ● ● ●.

The largest number representable in base x with n digits is:

In binary, for example, the number 7 would require 3 bits (111); 8 would require 4 bits (1000). In general, the largest number representable in base 2 with n digits is .

Each of the numbers from 0 to is uniquely represented by an n-digit number in binary. A given number k uses ⌊log 2k⌋+1 digits in base 2. Analogously, each of the numbers from 0 to is uniquely represented by an n-digit number in base x. A given number k uses ⌊log 2k⌋+1 digits in base x.

A number n has length n in unary, but has length ⌊log 2k⌋+1 in binary. So, unary is exponentially longer than binary.

Egyptian Multiplication, Again

Recall that the Egyptians used decimal numbers but multiplied and divided in binary. Their method of multiplication involved repeated doubling.

Suppose we want to multiply 15 by 5. In binary, 5 has the three-bit representation 101. Starting with the larger number, 15, repeatedly double the largest so far to obtain the sequence 15, 30, 60. Add together all where . We get 15 + 60 = 75.

	15	*
	30
	60	*
Total	75

In general, when multiplying a times b, we note that b has some n-bit representation . Then, starting with a, we repeatedly double the largest number obtained so far to get the sequence . Then we sum the members of this sequence for which .

Why does this method of multiplication work?

Consider that b can be represented as

Hence, the product is So, if is 1, then is in the sum. Otherwise, the term will be 0.

Exercise

Use Egyptian multiplication to find 12 times 12.

How did the Egyptians do the part where they converted b to binary when they did not have the concept of binary numbers? They used repeated halving to do base conversion.

The following program demonstrates the Egyptian method of base conversion by halving. Sometimes the Egyptians combined the base conversion by halving and the multiplication by doubling into one algorithm.

Here is the calculation of 70*13. Note that 13 in binary is 1101=23+22+20.

Doubling	Halving	Odd	Running total
70	13	*	70
140	6
280	3	*	350
560	1	*	910

70⋅13=70⋅23+70⋅22+70⋅20=910

Exercise

Use Egyptian multiplication to find 30⋅5.

The method of repeated doubling can also be used for division. Suppose that we wanted to divide 184 by 17. We can proceed as follows.

Doubling
17	1
34	2	*
68	4
136	8	*

We stop at 136 because the next double exceeds 184.

The Egyptians would first check off the last row and subtract 136 from 184 to obtain 48. They would then check off the row containing 34, the largest multiple of 17 less than 48. Because 48 – 34 = 14 is less than 17, they would now add up all the marked entries in the second column: 2 + 8 = 10. Thus, the answer has a quotient of 10 and a remainder of 14.

184 = 17*8 + 17*2 + 14 184/17 = 10 with remainder 14

Egyptian multiplication (and division) is also sometimes known as the "Russian peasant" multiplication (and division) algorithm. In either guise, this method is essentially a form of standard binary multiplication.

Example

Egyptian Base 3

The ancient Egyptians also used base-3 to represent numbers, but with a twist. In conventional base-3, each digit can be 0, 1, or 2. In Egyptian base 3, the digits were -1, 0, or 1. For example, the Egyptian base-3 number would be equivalent to

(in base 10).

Similarly, the Egyptian base 3 number would be equivalent to

In general, the number with each represents the number

As with practically any other representation, we can ask the following questions (as we did for binary numbers): Can every number be represented using this representation? Is every number representable uniquely? How many bits does it take to represent any number in this representation? Is there an efficient algorithm to convert to and from this representation?

Using negative values: how and why

Recall that the Egyptians did not have the concept of negative numbers (negative numbers first appeared in the writings of the Hindu mathematician Brahmagupta around 628 A.D), but we claim that Egyptian base-3 used negative numbers in the representation. How can this be possible? Well, for the Egyptians, the concept was implicit, since it used a balance or set of scales. A balance is a weighing apparatus with a central pivot, a beam, two scales and a set of counterweights that are placed in one of the scales. Such a weighing device can tip either way, so one side could be regarded as positive and the other as negative.

What set of counterweights to choose? It is easy to see that one can use a binary system of weights that would include a counterweight for each power of 2: 1, 2, 4, 8, 16, and so on. Using these, we could weight every object of integer mass in the right hand scale by just placing these counterweights in the left-hand scale. However, the crucial insight was that counterweights could be placed on both scales, with counterweights placed on the same side as the object counting as negative ones, and the counterweights on the other side counting as positive ones.

Example

Suppose that we want to weigh bags of flour, which have weight anywhere from 1 to 40 kilograms. How can we do this using just six counterweights? Can we do it using only 4 counterweights?

Suppose we used "base-2" counterweights of 1, 2, 4, 8, 16, and 32 kilograms, we can weigh any integral load from to kilograms. Why? Because that is the same as saying that every natural number less than can be expressed uniquely as the sum of distinct powers of . Hence we can measure out any bag of weight at most kilograms. Note that fewer than binary weights would not suffice, since using 5 binary weights we would be able to measure at most kilograms.

However, if we used a Egyptian base-3 system, we would have a standard weights for each power of 3 --- the weights would be 1, 3, 9, and 27 kilograms. In this case, any integer between and can be written in the Egyptian base-3, which would be useful since merchants would have to lug around fewer standard weights.