\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsfonts}
\usepackage{epsfig}
\setlength{\topmargin}{-.55in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.1in}
\newcommand{\br}{\mathbf {R}}
\newcommand{\bq}{\mathbf {Q}}
\newcommand{\bz}{\mathbf {Z}}
\newcommand{\bn}{\mathbf {N}}
\newcommand{\z}{$\circ$}
\newcommand{\lph}{$\leftharpoondown$}
\begin{document}
\title{Binary Arithmetic: From Leibniz to von Neumann}
\author{Jerry M. Lodder\footnote{Mathematical
Sciences; Dept. 3MB, Box 30001; New Mexico State University; Las
Cruces, NM 88003; {\tt jlodder@nmsu.edu}.}}
\date{}
\maketitle
\section*{The Era of Leibniz}
Gottfried Wilhelm Leibniz (1646--1716) is often described as the last
universalist, having contributed to virtually all fields of scholarly
interest of his time, including law, history, theology, politics,
engineering, geology, physics, and perhaps most importantly,
philosophy, mathematics and logic \cite{JLAiton, JLHollingdale, JLJolley}.
The young Leibniz began to teach
himself Latin at the age of 8, and Greek a few years later, in order
to read classics not written in his native language, German. Later in
life, he wrote:
\begin{quote}
Before I reached the school-class in which logic was taught, I was
deep into the historians and poets, for I began to read the historians
almost as soon as I was able to read at all, and I found great
pleasure and ease in verse. But as soon as I began to learn logic, I
was greatly excited by the division and order in it. I immediately
noticed, to the extent that a boy of 13 could, that there must be a
great deal in it \cite[p.\ 516]{JLGerhardt1}.
\end{quote}
His study of logic and intellectual quest for order continued
throughout his life and became a basic principle to his method of
inquiry. At the age of 20 he published {\em Dissertatio de arte
combinatoria} (Dissertation on the Art of Combinatorics) in which he
sought a {\em characteristica generalis} (general characteristic) or a
{\em lingua generalis} (general language) that would serve as a
universal symbolic language and reduce all debate to calculation.
Leibniz maintained:
\begin{quote}
If controversies were to arise, there would be no more need of
disputation between two philosophers than between two accountants.
For it would suffice to take their pencils in their hands, to sit down
to their slates, and to say to each other: $\ldots$ Let us calculate
\cite[p.\ 170]{JLRussell}.
\end{quote}
The Leipzig-born scholar traveled extensively with diplomatic visits
to Paris and London, and extended trips to Austria and Italy to
research the history of the House of Brunswick. The years 1672--1676
were spent in Paris in an attempt to persuade King Louis XIV
(1638--1715) not to invade Germany, but Egypt instead, although
Leibniz was never granted an audience with the French king. During
this time in Paris, however, the young German became acquainted with
several of the leading philosophers of the day, acquired access to
unpublished manuscripts of Blaise Pascal (1623--1662) and Ren\'e
Descartes (1596--1650), and met the renowned Christiaan Huygens
(1629--1695), from whom he learned much about contemporary mathematics.
During these years he laid the foundation of his calculus and the core
of what would become his philosophical legacy.
Leibniz's invention of the differential and integral calculus is, in
part, a product of his search for a universal language. Questions in
the calculus can be reduced to the rules of calculation which the
symbols for derivative, $d$, and integral, $\int$, satisfy. Sadly a
priority dispute with Isaac Newton (1642--1727) over the invention of
calculus cast a pall over Leibniz's later years. Moreover, he became a
subject of ridicule with his philosophy that this is the best of all
possible worlds bitterly satirized in Voltaire's (1694--1778) play
{\em Candide}.
Let's turn to the universal genius's 1703 publication ``Explication de
l'arithm\'etique binaire, qui se sert des seuls caract\`eres 0 et 1,
avec des remarques sur son utilit\'e, et sur ce qu'elle donne le sens
des anciennes figures Chinoises de Fohy'' \cite[p.\ 223--227]{JLGerhardt2}
(An Explanation of Binary
Arithmetic Using only the Characters 0 and 1, with Remarks about its
Utility and the Meaning it Gives to the Ancient Chinese Figures of
Fuxi), which originally appeared in the journal {\em Memoires de
l'Acad\'emie Royale des Sciences} \cite{JLLeibniz1703}.
Here again, with the reduction of arithmetic
to expressions involving only zeroes and ones, we see a possible
candidate for Leibniz's {\em characteristica generalis}. Of binary
numeration, he writes ``it permits new discoveries [in]
$\ldots$ arithmetic $\ldots$ in geometry, because when the numbers are
reduced to the simplest principles, like 0 and 1, a wonderful order
appears everywhere.'' Concerning the binary
calculations themselves `` $\ldots$ these operations are so easy that we
shall never have to guess or apply trial and error, as we must do in ordinary
division. Nor do we need to learn anything by rote.''
Certainly Leibniz was not the first to experiment with binary numbers
or the general concept of a number base \cite{JLGlaser}. However, with
base 2 numeration, Leibniz witnessed the confluence of several
intellectual ideas of his world view, not just the {\em
characteristica generalis}, but also theological and mystical ideas of
order, harmony and creation \cite {JLSwetz}.
Additionally his 1703 paper \cite{JLLeibniz1703}
contains a striking application of binary numeration to the ancient
Chinese text of divination, the {\em Yijing} ({\em I-Ching} or
{\em Book of Changes}).
Early in life Leibniz developed an interest in China,
corresponded with Catholic
missionaries there, and wrote on questions of theology concerning the
Chinese. Surprisingly he believed that he had found an historical
precedent for his binary arithmetic in the ancient Chinese lineations or
64 hexagrams of the {\em Yijing}. This, he thought,
might be the origin of a universal symbolic language. A hexagram
consists of six lines atop one another, each of which is either solid or broken,
forming a total of 64 possibilities, while a grouping of only
three such lines is called a trigram [cova]. Leibniz lists the eight
possible trigrams in his exposition on binary arithmetic, juxtaposed with
their binary equivalents.
He had been in possession of his ideas concerning binary
arithmetic well before his 1703 publication. In 1679 Leibniz outlined
plans for a binary digital calculating machine, and in 1697 he sent a
congratulatory birthday letter to his patron Duke Rudolph August of
Brunswick, in which he discusses binary numeration and the related
creation theme with 0 denoting nothing and 1 denoting God
\cite{JLSwetz}. Furthermore, Leibniz sent the French Jesuit Joachim
Bouvet (1656--1730) an account of his binary system while Bouvet was
working in China. The Jesuits are an educational order of Catholic
priests, who, while in China, sought the conversion of the Chinese
to Christianity, hopefully by the identification of an ancient theology
common to both religions. Bouvet began a study of the {\em Yijing},
viewing this text as the possible missing link between the two
religions \cite{JLSwetz}. It was from this Jesuit
priest that Leibniz received the hexagrams attributed to Fuxi, the
mythical first Emperor of China and legendary inventor of Chinese
writing. In actuality, the hexagrams are derived from the philosopher
Shao Yong's (1011--1077) {\em Huangji jingshi shu} (Book of Sublime
Principle Which Governs All Things Within the World).
Shortly after receiving Bouvet's letter
containing the hexagrams and Bouvet's identification of a relation
between them and binary numeration, Leibniz submitted for publication
his 1703 paper ``Explanation of Binary Arithmetic'' \cite[p.\ 44]{JLChing}.
\medskip
\noindent
Here is the first question of the student module:
\noindent
1. Concerning the utility of the binary system, Leibniz cites an
application to weighing masses. Suppose that a two-pan balance is
used for weighing stones. A
stone of unknown (integral) weight is placed on the left pan, while
standard weights are placed only on the right pan until both sides
balance. For example, if standard weights of 1, 4, 6 are used, then a
stone of weight 7 on the left pan would balance the standard weights 1
and 6 on the right. Two standard weights with the same value cannot
be used. Leibniz claims that all stones of integral weight
between 1 and 15 inclusive can be weighed with just four standard
weights. What are these four standard weights? Explain how each
stone of weight between 1 and 15 inclusive can be weighed with the
four standard weights. Make a table with one column for each of
the four standard weights and another column for the stone of unknown
weight. For each of the 15 stones, place an ``X'' in the columns for
the standard weights used to weigh the stone.
\medskip
Let's now read from an ``Explanation of Binary Arithmetic,'' using
a modified version of the Ching-Oxtoby translation \cite[p.\ 81--86]{JLChing}.
\bigskip
\bigskip
\begin{quote}
{\sf
\begin{center}
\bf{An Explanation of Binary Arithmetic \\
Using only the Characters 0 and 1, with Remarks \\
about its Utility and the Meaning it Gives to the \\
Ancient Chinese Figures of Fuxi} \\
\end{center}
\smallskip
\begin{center}
By G.W. Leibniz
\end{center}
\bigskip
Ordinary arithmetical calculations are performed according to a
progression of tens. We use ten characters, which are 0, 1, 2, 3, 4,
5, 6, 7, 8, 9, that signify zero, one and the following numbers up to
nine, inclusive. After reaching ten, we begin again, writing {\em ten} with
10, and ten times ten or {\em one hundred} with 100, and ten times one
hundred or {\em one thousand} with 1000, and ten times one thousand with
10000, and so on.}
\end{quote}
\medskip
\noindent
2. Write the numbers 1, 10, 100, 1000 and 10000 as powers of ten.
Express your answer in complete sentences or with equations. What
pattern do you notice in the exponents? (Question one appears just
before the excerpt from Leibniz).
\medskip
\begin{quote}
{\sf But instead of the progression by tens, I have already used for
several years the simplest of all progressions, that by twos, having
found that this contributes to the perfection of the science of
numbers. Thus I use no characters other than 0 and 1, and then,
reaching two, I begin again. This is why {\em two} is written here as 10,
and two times two or {\em four} as 100, and two times four or {\em eight} as 1000,
and two times eight or {\em sixteen} as 1000, and so on.}
\end{quote}
\noindent
3. Write the numbers 1, 2, 4, 8 and 16 as powers of two. Express
your answer in complete sentences or with equations. What pattern do
you notice in the exponents? How do the exponents compare with those
in question 2? How does the progression by twos compare with the
standard weights in question 1?
\medskip
\noindent
\begin{quote}
{\sf Here is the {\em Table of Numbers} according to this pattern, which we
can continue as far as we wish.}
\end{quote}
\noindent
4. Compare the entries from 1 to 15 in Leibniz's ``Table of
Numbers''on the following page with the table for weighing
stones that you constructed previously in question 1.
Today a number written only with the characters 0 and 1 according
to Leibniz's ``progression of twos'' is said to be written in binary
notation, or base 2. Find the binary equivalents of the (base 10)
numbers
$$ 34, \ \ \ 64, \ \ \ 100, \ \ \ 1015 \, . $$
Be sure to explain your work.
\begin{quote}
{\sf At a glance we see the reason for the {\em famous property
of the double geometric progression} in whole numbers, which states that given
only one of these numbers in each degree, we can form all other whole
numbers below the double of the highest degree. Since, as we would
say, for example, 111 or 7 is the sum of four, two and one, and that
1101 or 13 is the sum of eight, four and one.
$$\begin{tabular}{ccc||cccccc||r}
1 & 0 & 0 & 4 & \ \ \ & 1 & 0 & 0 & 0 & 8 \\
\ & 1 & 0 & 2 & \ \ \ & \ & 1 & 0 & 0 & 4 \\
\ & \ & 1 & 1 & \ \ \ & \ & \ & \ & 1 & 1 \\
\cline{1-4} \cline{6-10}
1 & 1 & 1 & 7 & \ \ \ & 1 & 1 & 0 & 1 & 13 \\
\end{tabular}$$
This property is useful
to investigators for weighing all kinds of masses with just a few
weights or could be used in monetary systems to provide a range of
change with just a few coins.}
\end{quote}
\medskip
\begin{center}
{\sf
%\hskip0.5in
\begin{tabular}[htb]{c|ccccc||r}
\multicolumn{6}{r}{Table of Numbers} & \\
\z & \z & \multicolumn{1}{|c}{\z} & \multicolumn{1}{|c}{\z} &
\multicolumn{1}{|c}{\z} & \multicolumn{1}{|c||}{0} & 0 \\
\z & \z & \multicolumn{1}{|c}{\z} & \multicolumn{1}{|c}{\z} &
\multicolumn{1}{|c}{\z} & \multicolumn{1}{|c||}{1} & 1 \\ \cline{6-6}
\z & \z & \multicolumn{1}{|c}{\z} &
\multicolumn{1}{|c}{\z} & \multicolumn{1}{|c}{1} & 0 & 2 \\
\z & \z & \multicolumn{1}{|c}{\z} &
\multicolumn{1}{|c}{\z} & \multicolumn{1}{|c}{1} & 1 & 3 \\ \cline{5-6}
\z & \z & \multicolumn{1}{|c}{\z} & \multicolumn{1}{|c}{1} & 0 & 0 & 4 \\
\z & \z & \multicolumn{1}{|c}{\z} & \multicolumn{1}{|c}{1} & 0 & 1 & 5 \\
\z & \z & \multicolumn{1}{|c}{\z} & \multicolumn{1}{|c}{1} & 1 & 0 & 6 \\
\z & \z & \multicolumn{1}{|c}{\z} &
\multicolumn{1}{|c}{1} & 1 & 1 & 7 \\ \cline{4-6}
\z & \z & \multicolumn{1}{|c}{1} & 0 & 0 & 0 & 8 \\
\z & \z & \multicolumn{1}{|c}{1} & 0 & 0 & 1 & 9 \\
\z & \z & \multicolumn{1}{|c}{1} & 0 & 1 & 0 & 10 \\
\z & \z & \multicolumn{1}{|c}{1} & 0 & 1 & 1 & 11 \\
\z & \z & \multicolumn{1}{|c}{1} & 1 & 0 & 0 & 12 \\
\z & \z & \multicolumn{1}{|c}{1} & 1 & 0 & 1 & 13 \\
\z & \z & \multicolumn{1}{|c}{1} & 1 & 1 & 0 & 14 \\
\z & \z & \multicolumn{1}{|c}{1} & 1 & 1 & 1 & 15 \\ \cline{3-6}
\z & 1 & 0 & 0 & 0 & 0 & 16 \\
\z & 1 & 0 & 0 & 0 & 1 & 17 \\
\z & 1 & 0 & 0 & 1 & 0 & 18 \\
\z & 1 & 0 & 0 & 1 & 1 & 19 \\
\z & 1 & 0 & 1 & 0 & 0 & 20 \\
\z & 1 & 0 & 1 & 0 & 1 & 21 \\
\z & 1 & 0 & 1 & 1 & 0 & 22 \\
\z & 1 & 0 & 1 & 1 & 1 & 23 \\
\z & 1 & 1 & 0 & 0 & 0 & 24 \\
\z & 1 & 1 & 0 & 0 & 1 & 25 \\
\z & 1 & 1 & 0 & 1 & 0 & 26 \\
\z & 1 & 1 & 0 & 1 & 1 & 27 \\
\z & 1 & 1 & 1 & 0 & 0 & 28 \\
\z & 1 & 1 & 1 & 0 & 1 & 29 \\
\z & 1 & 1 & 1 & 1 & 0 & 30 \\
\z & 1 & 1 & 1 & 1 & 1 & 31 \\ \cline{2-6}
\multicolumn{6}{c||}
{1 \ \ 0 \ \ 0 \ \ 0 \ \ 0 \ \ 0} & 32 \\
\multicolumn{7}{c}{etc.} \\
\end{tabular} }
\end{center}
\medskip
\noindent
5. Using modern notation, Leibniz's ``double geometric progression''
or ``progression by twos''
would be written $2^0$, $2^1$, $2^2$, $2^3$, $\ldots$ , $2^n$.
Guess a simple formula for
$$ 2^0 + 2^1 + 2^2 + 2^3 + \cdots + 2^n $$
based on Leibniz's verbal description ``that given only one of these
numbers in each degree,'' we should be able to achieve all whole
numbers ``below the double of the highest degree.''
Prove that your guess is correct using only algebra (addition and
multiplication). Hint: Multiply $(2^0 + 2^1 + 2^2 + 2^3 + \cdots +
2^n)$ by 1, where 1 is written as $2-1$.
Leibniz continues:
\begin{quote}
{\sf This expression of numbers, once established, facilitates all
kinds of operations.
\bigskip
For example, addition (1)
\medskip
\begin{tabular}{cccc||rcccccc||rcccccc||r}
\ & 1 & 1 & 0 & 6 & $\ \ \ $ & \ & \ & 1 & 0 & 1 & 5 & $\ \ \ $ & \ &
1 & 1 & 1& 0 & 14 \\
\ & 1 & 1 & 1 & 7 & $\ \ \ $ & \ & 1 & 0 & 1 & 1 & 11 & $\ \ \ $ & 1
& 0 & 0 & 0 & 1 & 17 \\
. & . & & & & $\ \ \ $& . & . & . & . & & & &
& & & & & \\ \cline{1-5} \cline{7-12} \cline{14-19}
1 & 1 & 0 & 1 & 13 & & 1 & 0 & 0 & 0 & 0 & 16 & & 1 & 1 & 1 & 1 & 1 &
31 \\
\end{tabular}
\bigskip
For subtraction
\medskip
\begin{tabular}{cccc||rcccccc||rcccccc||r}
1 & 1 & 0 & 1 & 13 & $\ \ \ $ & 1 & 0 & 0 & 0 & 0 & 16 &
$\ \ \ $ & 1 & 1 & 1 & 1 & 1 & 31 \\
\ & 1 & 1 & 1 & 7 & $\ \ \ $ & \ & 1 & 0 & 1 & 1 & 11 & $\ \ \ $ & 1
& 0 & 0 & 0 & 1 & 17 \\ \cline{1-5} \cline{7-12} \cline{14-19}
\ & 1 & 1 & 0 & 6 & $\ \ \ $ & \ & \ & 1 & 0 & 1 & 5 & $\ \ \ $ & \ &
1 & 1 & 1& 0 & 14 \\
\end{tabular}
\bigskip
For multiplication (2)
\medskip
\begin{tabular}{cccc||rcccccc||rcccccc||r}
&\ & 1 & 1 & 3 & $\ \ \ \ \ \ $ & & & 1 & 0 & 1 & 5 & $\ \ \ $ &\ &\ & 1 & 0
& 1 & 5 \\
& & 1 & 1 & 3 & & & & & 1 & 1 & 3 & & & & 1 & 0 & 1 & 5 \\
\cline{3-5} \cline{9-12} \cline{16-19}
&\ & 1 & 1 & & $\ \ \ $ & & & 1 & 0 & 1 & & $\ \ \ $ &\ &\ & 1 & 0
& 1 & \\
& 1 & 1 & & & & & 1 & 0 & 1 & & & & 1 & 0 & 1& 0 & & \\
& . & & & & & & & & & & & & & . & & & & \\
\cline{1-5} \cline{8-12} \cline{14-19}
1 & 0 & 0 & 1 & 9 & & & 1 & 1 & 1 & 1 & 15 & & 1 & 1 & 0 & 0 & 1 & 25 \\
\end{tabular}
\bigskip
For division
\medskip
\begin{tabular}{r||cccccccc||c}
15 & $\not{1}$ & $\not{1}$ & 1 & 1 & $\ \ \ \ \ $ & 1 & 0 & 1 & 5 \\
3 & $\not{1}$ & $\not{1}$ & $\not{1}$ & 1 & \\
& & $\not{1}$ & 1 \\
\end{tabular}
\bigskip
\noindent
All these operations are so easy that we shall
never have to guess or apply trial and error, as we must do in ordinary
division. Nor do we need to learn anything by rote here, as must be
done in ordinary calculation, where, for example, it is necessary to
know that 6 and 7 taken together makes 13, and that 5 multiplied by 3
gives 15, following the so-called Pythagorean table{\footnote{This
is likely a reference to the multiplication table.}} that one times one
is one. But here everything is found and proven from the source,
just as we see in the preceding examples under the signs (1) and (2).}
\end{quote}
\medskip
\noindent
6. Using your knowledge of base 10 addition, explain the examples of
base 2 addition given above by Leibniz. What is the likely meaning of the
dot Leibniz includes in certain columns for addition? Using binary
arithmetic, compute $1101 + 1110$, without converting these numbers to
base 10. Explain the examples for binary
subtraction, multiplication and division above. Keep in mind that
these should be base 2 analogues of base 10 procedures. Since
Leibniz's example for division may be incomplete by today's standards,
you may wish to supplement his work with additional steps, indicating
clearly what multiples of 3 are subtracted from 15 in base 2.
Finally, using binary arithmetic, compute the following.
$$ 11010-1101, \ \ \ (1101)\cdot (11), \ \ \ 1101 \div 101 \, . $$
Be sure to explain your work. For the division problem, you may
state what the remainder is in terms of a binary whole number,
without writing it as a fraction.
\medskip
\begin{quote}
{\sf
However, I am not at all recommending this manner of counting as a
replacement for the ordinary practice of tens. For aside from the
fact that we are accustomed to this, there is no need to learn what we
have already memorized; the practice of tens is shorter, the numbers
not as long. If we were accustomed to proceed by twelves or by
sixteens, there would be even more of an advantage. As compensation
for its length, however, calculation by twos, that is by 0 and by 1,
is most basic for science; it permits new discoveries which become
useful even in the practice of arithmetic, and especially in geometry,
because when the numbers are reduced to the simplest principles, like
0 and 1, a wonderful order appears everywhere. For example, even in
the Table of Numbers, we see in each column those periods which always
reappear. In the first column it is 01, in the second 0011, in the
third 00001111, in the fourth 0000000011111111, and so on. Small
zeroes are put into the table to fill the void at the beginning of the
column, and to mark these periods better. Lines are also traced in
the table indicating that what these lines enclose always reoccurs
below them. The square numbers, cubes and other powers, as well
as the triangular numbers,\footnote{The sequence 1, 3, 6,
10, 15, $\ldots \, $, giving the number of dots in certain triangles
\cite[p.\ 49]{JLKatz} forms the triangular numbers.} pyramidal numbers,\footnote{The
sequence 1, 4, 10, 20, 35, $\ldots \, $, giving the number of dots in
certain pyramids \cite[p.\ 76]{JLYoung} forms the pyramidal numbers.} and
other figurate numbers, also have similar periods, so that one can
immediately write the tables without even calculating. A certain
tedium at the beginning, which later serves to spare us calculation and
to allow us to go by rule infinitely far, is extremely advantageous.
What is surprising in this calculation is that this arithmetic of 0 and
1 contains the mystery of lines of an ancient king and philosopher named
Fuxi, who is believed to have lived more than four thousand years ago
and whom the Chinese regard as the founder of their empire and of
their sciences. There are several figures of lines that are
attributed to him; they all go back to this arithmetic. But it is
enough to place here the so-called figures of the eight Cova [trigrams], which
are basic, and to add to these an explanation which is manifest, so
that it is understood that a whole line --- signifies unity or one,
and that a broken line -- -- signifies zero or 0.
\bigskip
\begin{tabular}{cccccccc}
-- -- & --- & -- -- & --- & -- -- & --- & -- -- & --- \\
-- -- & -- -- & --- & --- & -- -- & -- -- & --- & --- \\
-- -- & -- -- & -- -- & -- -- & --- & --- & --- & --- \\
0 & \lph & 0 & \lph & 0 & \lph & 0 & \lph \\
0 & 0 & \lph & \lph & 0 & 0 & \lph & \lph \\
0 & 0 & 0 & 0 & \lph & \lph & \lph & \lph \\ \hline
0 & 1 & 10 & 11 & 100 & 101 & 110 & 111 \\ \hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\end{tabular}
$\ldots$ [S]carcely two
years ago I sent to the Reverend Father Bouvet, the famous French Jesuit
living in Peking, my manner of counting by 0 and 1, and it was all he
needed to recognize that this holds the key to Fuxi's\footnote{The
mythical first Emperor of China.} figures. So he
wrote to me on November 14, 1701, sending me the great figure of this
princely philosopher which goes to 64. $\ldots$ }
\end{quote}
\bigskip
Although striking to Leibniz, the link between the 64 hexagrams of the
{\em Yijing} and binary numeration appears today as only an intellectual
curiosity. The base two system did not provide a common origin to
Christianity and Confucianism, as Leibniz and Bouvet had sought.
\section*{The Electronic Age}
John von Neumann (1903--1957) was a leading mathematician, physicist
and engineer of the twentieth century, having contributed
significantly to the foundations of quantum mechanics, the development
of the atomic bomb, and the logical structure of the electronic
digital computer \cite{JLGoldstine, JLJames}. Born in Budapest Hungary,
the young von Neumann
showed a gift for mathematics, received a doctorate in the subject
from the University of Budapest and a degree in chemical
engineering from the {\em Eidgen\"ossische Technische Hochschule}
(Swiss Federal Polytechnic) in Zurich. He met the renowned David
Hilbert (1862--1943) on a visit to G\"ottingen in 1926, after which he
was offered the position of a {\em Privatdozent} (an un-salaried
lecturer) at the University of Berlin and then at the
University of Hamburg. In 1930 he visited the United States,
accepting a salaried lectureship at Princeton University, a move which would
shape the rest of his life.
Becoming a Professor of Mathematics at the prestigious Institute for
Advanced Study (Princeton, New Jersey) in 1933, von Neumann was able
to devote his time to the study of analysis, continuous geometry,
fluid dynamics, wave propagation and differential equations. In 1943
he became a member of the Los Alamos Laboratory and helped develop the
atomic bomb. The particular problem he faced, the implosion problem,
was how to produce an
extremely fast reaction in a small amount of the uranium isotope
U$^{235}$ in order to cause a great amount of energy to
be released. In conjunction with Seth Neddermeyer, Edward Teller and
James Tuck, this problem was solved with a high explosive lens
designed to produce a spherical shock wave to cause the implosion
necessary to detonate the bomb.
Von Neumann's strength was his ability to model theoretical phenomena
mathematically and solve the resulting equations numerically \cite[p.\
181]{JLGoldstine}, which required adroit skills in calculation.
Meanwhile in 1941 John William Mauchly (1907--1980), as a newly
appointed Assistant Professor at the University of Pennsylvania's
Moore School of Electrical Engineering, began discussions with
graduate student John Presper Eckert (1919--1995) and others about the
possibility of an electronic digital computing device that would be
faster and more accurate than any existing machine, designed in part
to meet the computing needs of the Ballistics Research Laboratory
(BRL) of the Army Ordnance Department in Aberdeen, Maryland. With the
help of mathematician and First Lieutenant Herman Goldstine (1913--),
Mauchly's proposal for a high-speed vacuum-tube computer received
funding from the BRL in 1943. The device was dubbed the Electronic
Numerical Integrator and Computer (ENIAC). Tested in late 1945, and
unveiled in 1946, the ENIAC was a behemoth containing 18,000 vacuum
tubes and requiring 1,800 square feet of floor space for the computer
alone \cite[p.\ 133]{JLStern}.
Arithmetic on the ENIAC was performed using the base 10
decimal system, requiring the ability to store ten different values
for each digit of a numerical quantity. The multiplication table for all
digits between zero and nine was also stored on the machine.
The ENIAC was not programmable in the modern sense of a coded program,
and contained no sub-unit similar to a present-day compiler. To alter
its function, i.e., to implement a different numerical algorithm,
external switches and cables had to be repositioned. Designs for a
more robust machine may have been in place as the ENIAC went into
production, but the rush to meet the needs of the war effort took
precedence.
By serendipity, in the summer of 1944 Goldstine met von Neumann at a
railway station in Aberdeen, both working on separate highly classified
projects. Goldstine writes: ``Prior to that time I had never met
this great mathematician, but I knew much about him of course and had
heard him lecture on several occasions'' \cite[p.\ 182]{JLGoldstine}. After
a discussion of the computing power of the ENIAC, von Neumann became
keenly interested in this machine, and in late 1945 tested it on
computations needed for the design of the hydrogen bomb. Von Neumann
quickly became involved with the logical structure of the next
generation of computing machinery, the Electronic Discrete Variable
Automatic Computer (EDVAC), designed around the ``stored program''
concept. The instructions of an algorithm could be stored
electronically on the EDVAC and then executed in sequential order. In
this way, von Neumann had outlined a ``universal computing machine'' in
the sense of Alan Turing (1912--1954), with the universal character
referring to the machine's ability to execute any algorithmic procedure
that could be reduced to simple logical steps. Turing first
introduced a logical description of his universal computing machine in
1936 \cite{JLTuring36} as the solution to a problem posed by David Hilbert.
Von Neumann, who had studied logic early in his career, was certainly
aware of Turing's work, and in 1938 had offered Turing an assistantship
at the Institute for Advanced Study \cite[p.\ 271]{JLGoldstine}. In 1945 von
Neumann issued his white paper ``First Draft of a Report on the
EDVAC'' \cite{JLvonNeumann} under the auspices of the University of Pennsylvania
and the United States Army Ordnance Department. Although this draft
was never revised, the ideas therein soon became known as von Neumann
architecture in computer design. Let's read a few excerpts from this
paper \cite{JLvonNeumann} related to binary arithmetic.
\bigskip
\bigskip
\begin{quote}
{\sf
{\centerline{\bf{First Draft of a Report on the EDVAC}}}
\medskip
\noindent
2.2 First: Since the device is primarily a computer, it will have to
perform the elementary operations of arithmetic most frequently.
There are addition, subtraction, multiplication and division: $+$,
$-$, $\times$, $\div$. It is therefore reasonable that it should
contain specialized organs for just these operations. At any
rate a {\em central arithmetical} part of the device will probably
have to exist, and this constitutes {\em the first specific part:
CA}.
\medskip
\noindent
4.3 It is clear that a very high speed computing device should
ideally have vacuum tube elements. Vacuum tube aggregates like
counters and scalers have been used and found reliable at reaction
times (synaptic delays) as short as a microsecond ( $= 10^{-6}$
seconds).
\medskip
\noindent
5.1 Let us now consider certain functions of the first specific part:
the central arithmetical part CA.
The element in the sense of 4.3, the vacuum tube used as a current
valve or {\em gate}, is an all-or-none device, or at least it
approximates one: According to whether the grid bias is above or
below cut-off; it will pass current or not. It is true that it needs
definite potentials on all its electrodes in order to maintain either
state, but there are combinations of vacuum tubes which have perfect
equilibria: Several states in each of which the combination can exist
indefinitely, without any outside support, while appropriate outside
stimuli (electric pulses) will transfer it from one equilibrium into
another. These are the so called {\em trigger circuits}, the basic
one having two equilibria. The trigger circuits with more than
two equilibria are disproportionately more involved.
Thus, whether the tubes are used as gates or as triggers, the
all-or-none, two equilibrium arrangements are the simplest ones.
Since these tube arrangements are to handle numbers by means of their
digits, it is natural to use a system of arithmetic in which the
digits are also two valued. This suggests the use of the binary
system.
\medskip
\noindent
5.2 A consistent use of the binary system is also likely to simplify
the operations of multiplication and division considerably.
Specifically it does away with the decimal multiplication
table. In other words: Binary arithmetic has a simpler and
more one-piece logical structure than any other, particularly than
the decimal\footnote{base 10} one.}
\end{quote}
\medskip
\noindent
7. Let $a$ and $b$ denote binary variables with one digit each.
Using only the logical connectives $\wedge$ (and), $\vee$ (or) and $\sim$
(not), find a logical expression which gives the digit in the ones
place (the right-hand digit) of
$a+b$. Find a logical expression which gives the digit in the twos
place (the left-hand digit) of $a+b$. Explain your answer.
\medskip
\noindent
Extra Credit A: Find a pattern in the binary representation of the
square numbers 1, 4, 9, 16, 25, $\ldots$ . Leibniz claims to have found
such patterns.
\medskip
\noindent
Extra Credit B: If in question 1 of the main project,
standard weights can be placed on
both sides of the balance, what four standard weights should be used
in order to weigh all stones of integral weight between 1 and 40
inclusive?
\section*{Notes to the Instructor}
The project is ideal for a beginning-level discrete mathematics or
computer programming course. It could be assigned independently or in
conjunction with the project ``Turing Machines and Binary Addition,''
available from the web resource \cite{JLBLLPR}. After completion of
the project, the instructor may wish to lead the class in the
discovery of divisibility properties of integers that become apparent
after studying their expression in binary form. The pattern of zeroes
in the base two expansion of the perfect squares leads to the
conjecture that $8 \vert (n^2 - 1)$, $n$ an odd integer, where the
vertical bar denotes ``divides.'' In this way, the class is following
in Leibniz's footsteps when he claims that ``calculation by twos
$\ldots$ is most basic for science; it permits new discoveries,
$\ldots \,$, because when the numbers are reduced to the simplest
principles, like 0 and 1, a wonderful order appears everywhere''
\cite{JLLeibniz1703}.
\begin{thebibliography}{99}
\bibitem{JLAiton} Aiton, E. J., {\em Leibniz: A Biography}, Adam Hilger,
Boston, 1985.
\bibitem{JLBLLPR} Bezhanishvili, G., Leung, H., Lodder, J., Pengelley,
D., Ranjan, D., ``Teaching Discrete Mathematics via Primary Historical
Sources,''
{\tt{math-old.nmsu.edu/hist{\_}projects/}}
\bibitem{JLChing} Ching, J., Oxtoby, W. G., {\em Moral Enlightenment:
Leibniz and Wolff on China}, Steyler Verlag, Nettetal, 1992.
\bibitem{JLDavis65} Davis, M.,
{\em The Undecidable. Basic Papers on Undecidable Propositions,
Unsolvable Problems and Computable Functions}, Martin Davis (editor),
Raven Press, Hewlett, N.Y., 1965.
\bibitem{JLGerhardt1} Gerhardt, C. I., (editor) {\em Die Philosophischen
Schriften von Leibniz}, vol. VII, Olms, Hildesheim, 1965.
\bibitem{JLGerhardt2} Gerhardt, C. I., (editor) {\em G. W. Leibniz
Mathematische Schriften}, Vol. VII, Olms, Hildesheim, 1962.
\bibitem{JLGlaser} Glaser, A., {\em History of Binary and Other
Nondecimal Numeration}, Anton Glaser, Southampton, PA, 1971.
\bibitem{JLGoldstine} Goldstine, H. H., {\em The Computer from Pascal to von
Neumann}, Princeton University Press, Princeton, New Jersey, 1972.
\bibitem{JLHollingdale} Hollingdale, S., {\em Makers of Mathematics}, Penguin
Books, New York, 1994.
\bibitem{JLJames} James, I., {\em Remarkable Mathematicians: From Euler
to von Neumann}, Cambridge University Press, Cambridge, 2002.
\bibitem{JLJolley} Jolley, N., (editor) {\em The Cambridge Companion to
Leibniz}, Cambridge University Press, Cambridge, 1995.
\bibitem{JLKatz} Katz, V., {\em A History of Mathematics: An
Introduction}, Second Edition, Addison-Wesley, New York, 1998.
\bibitem{JLLeibniz1703} Leibniz, G. W., ``Explication de
l'arithm\'etique binaire, qui se sert des seuls caract\`eres 0 et 1,
avec des remarques sur son utilit\'e, et sur ce qu'elle donne le sens
des anciennes figures Chinoises de Fohy,'' {\em Memoires de
l'Acad\'emie Royale des Sciences}, {\bf{3}} (1703), 85--89.
\bibitem{JLRussell} Russell, B., {\em A Critical Exposition of the Philosophy
of Leibniz}, second ed., Allen and Unwin, London, 1937.
\bibitem{JLStern} Stern, N., {\em From ENIAC to UNIVAC: An Appraisal of
the Eckert-Mauchly Computers}, Digital Press, Bedford, Massachusetts,
1981.
\bibitem{JLSwetz} Swetz, F. J., ``Leibniz, the {\em Yijing}, and the
Religious Conversion of the Chinese,'' {\em Mathematics Magazine},
{\bf{76}}, No. 4 (2003), 276--291.
\bibitem{JLTuring36} Turing, A. M., ``On Computable Numbers with an Application
to the Entscheidungsproblem,'' {\em Proceedings of the London
Mathematical Society} {\bf{42}} (1936), 230--265.
A correction, {\bf{43}} (1937), 544--546.
This paper with a short foreword by Davis
was reprinted on pages 115--154 of \cite{JLDavis65}.
\bibitem{JLvonNeumann} von Neumann, J., ``First Draft of a Report on
the EDVAC,'' in {\em From ENIAC to UNIVAC: An Appraisal of
the Eckert-Mauchly Computers}, N. Stern, Digital Press, Bedford, Massachusetts,
1981, 177--246.
\bibitem{JLYoung} Young, R. M., {\em Excursions in Calculus: An Interplay
of the Continuous and the Discrete}, Mathematical Association of America,
Washington, D.C., 1992.
\end{thebibliography}
\end{document}