The Art of Computer Programming: Positional Number Systems
This chapter is from the book
This chapter is from the book
This chapter is from the book
Seeing there is nothing (right well beloued Students in the Mathematickes) that is so troublesome to Mathematicall practise, nor that doth more molest and hinder Calculators, then the Multiplications, Diuisions, square and cubical Extractions of great numbers, which besides the tedious expence of time, are for the most part subiect to many slippery errors. I began therefore to consider in my minde, by what certaine and ready Art I might remoue those hindrances.
— JOHN NEPAIR [NAPIER] (1616)
I do hate sums. There is no greater mistake than to call arithmetic an exact science. There are…hidden laws of Number which it requires a mind like mine to perceive. For instance, if you add a sum from the bottom up, and then again from the top down, the result is always different.
— M. P. LA TOUCHE (1878)
I cannot conceive that anybody will require multiplications at the rate of 40,000, or even 4,000 per hour; such a revolutionary change as the octonary scale should not be imposed upon mankind in general for the sake of a few individuals.
— F. H. WALES (1936)
Most numerical analysts have no interest in arithmetic.
— B. PARLETT (1979)
The chief purpose of this chapter is to make a careful study of the four basic processes of arithmetic: addition, subtraction, multiplication, and division. Many people regard arithmetic as a trivial thing that children learn and computers do, but we will see that arithmetic is a fascinating topic with many interesting facets. It is important to make a thorough study of efficient methods for calculating with numbers, since arithmetic underlies so many computer applications.
Arithmetic is, in fact, a lively subject that has played an important part in the history of the world, and it still is undergoing rapid development. In this chapter, we shall analyze algorithms for doing arithmetic operations on many types of quantities, such as “floating point” numbers, extremely large numbers, fractions (rational numbers), polynomials, and power series; and we will also discuss related topics such as radix conversion, factoring of numbers, and the evaluation of polynomials.
4.1. Positional Number Systems
The way we do arithmetic is intimately related to the way we represent the numbers we deal with, so it is appropriate to begin our study of the subject with a discussion of the principal means for representing numbers.
Positional notation using base b (or radix b) is defined by the rule
Equation 1
)
for example, 
. Our conventional decimal number system is, of course, the special case when b is ten, and when the a’s are chosen from the “decimal digits” 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; in this case the subscript b in (1) may be omitted.
The simplest generalizations of the decimal number system are obtained when we take b to be an integer greater than 1 and when we require the a’s to be integers in the range 0 ≤ ak < b. This gives us the standard binary (b = 2), ternary (b = 3), quaternary (b = 4), quinary (b = 5), . . . number systems. In general, we could take b to be any nonzero number, and we could choose the a’s from any specified set of numbers; this leads to some interesting situations, as we shall see.
The dot that appears between a0 and a–1 in (1) is called the radix point. (When b = 10, it is also called the decimal point, and when b = 2, it is sometimes called the binary point, etc.) Continental Europeans often use a comma instead of a dot to denote the radix point; the English formerly used a raised dot.
The a’s in (1) are called the digits of the representation. A digit ak for large k is often said to be “more significant” than the digits ak for small k; accordingly, the leftmost or “leading” digit is referred to as the most significant digit and the rightmost or “trailing” digit is referred to as the least significant digit. In the standard binary system the binary digits are often called bits; in the standard hexadecimal system (radix sixteen) the hexadecimal digits zero through fifteen are usually denoted by
)
The historical development of number representations is a fascinating story, since it parallels the development of civilization itself. We would be going far afield if we were to examine this history in minute detail, but it will be instructive to look at its main features here.
The earliest forms of number representations, still found in primitive cultures, are generally based on groups of fingers, piles of stones, etc., usually with special conventions about replacing a larger pile or group of, say, five or ten objects by one object of a special kind or in a special place. Such systems lead naturally to the earliest ways of representing numbers in written form, as in the systems of Babylonian, Egyptian, Greek, Chinese, and Roman numerals; but such notations are comparatively inconvenient for performing arithmetic operations except in the simplest cases.
During the twentieth century, historians of mathematics have made extensive studies of early cuneiform tablets found by archæologists in the Middle East. These studies show that the Babylonian people actually had two distinct systems of number representation: The numbers used in everyday business transactions were written in a notation based on grouping by tens, hundreds, etc.; this notation was inherited from earlier Mesopotamian civilizations, and large numbers were seldom required. When more difficult mathematical problems were considered, however, Babylonian mathematicians made extensive use of a sexagesimal (radix sixty) positional notation that was highly developed at least as early as 1750 B.C. This notation was unique in that it was actually a floating point form of representation with exponents omitted; the proper scale factor or power of sixty was to be supplied by the context, so that, for example, the numbers 2, 120, 7200, and 
were all written in an identical manner. The notation was especially convenient for multiplication and division, using auxiliary tables, since radix-point alignment had no effect on the answer. As examples of this Babylonian notation, consider the following excerpts from early tables: The square of 30 is 15 (which may also be read, “The square of 
is 
”); the reciprocal of 81 = (1 21)60 is (44 26 40)60; and the square of the latter is (32 55 18 31 6 40)60. The Babylonians had a symbol for zero, but because of their “floating point” philosophy, it was used only within numbers, not at the right end to denote a scale factor. For the interesting story of early Babylonian mathematics, see O. Neugebauer, The Exact Sciences in Antiquity (Princeton, N. J.: Princeton University Press, 1952), and B. L. van der Waerden, Science Awakening, translated by A. Dresden (Groningen: P. Noordhoff, 1954); see also D. E. Knuth, CACM 15 (1972), 671–677; 19 (1976), 108.
Fixed point positional notation was apparently first conceived by the Maya Indians in central America some 2000 years ago; their radix-20 system was highly developed, especially in connection with astronomical records and calendar dates. They began to use a written sign for zero about A.D. 200. But the Spanish conquerors destroyed nearly all of the Maya books on history and science, so we have comparatively little knowledge about the degree of sophistication that native Americans had reached in arithmetic. Special-purpose multiplication tables have been found, but no examples of division are known. [See J. Eric S. Thompson, Contrib. to Amer. Anthropology and History 7 (Carnegie Inst. of Washington, 1941), 37–67; J. Justeson, “Pratiche di calcolo nell’antica mesoamerica,” Storia della Scienza 2 (Rome: Istituto della Enciclopedia Italiana, 2001), 976–990.]
Several centuries before Christ, the Greek people employed an early form of the abacus to do their arithmetical calculations, using sand and/or pebbles on a board that had rows or columns corresponding in a natural way to our decimal system. It is perhaps surprising to us that the same positional notation was never adapted to written forms of numbers, since we are so accustomed to decimal reckoning with pencil and paper; but the greater ease of calculating by abacus (since handwriting was not a common skill, and since abacus users need not memorize addition and multiplication tables) probably made the Greeks feel it would be silly even to suggest that computing could be done better on “scratch paper.” At the same time Greek astronomers did make use of a sexagesimal positional notation for fractions, which they had learned from the Babylonians.
Our decimal notation, which differs from the more ancient forms primarily because of its fixed radix point, together with its symbol for zero to mark an empty position, was developed first in India within the Hindu culture. The exact date when this notation first appeared is quite uncertain; about A.D. 600 seems to be a good guess. Hindu science was highly developed at that time, particularly in astronomy. The earliest known Hindu manuscripts that show decimal notation have numbers written backwards (with the most significant digit at the right), but soon it became standard to put the most significant digit at the left.
The Hindu principles of decimal arithmetic were brought to Persia about A.D. 750, as several important works were translated into Arabic; a picturesque account of this development is given in a Hebrew document by Abraham Ibn Ezra, which has been translated into English in AMM 25 (1918), 99–108. Not long after this, al-Khwārizmī wrote his Arabic textbook on the subject. (As noted in Chapter 1, our word “algorithm” comes from al-Khwārizmī’s name.) His work was translated into Latin and was a strong influence on Leonardo Pisano (Fibonacci), whose book on arithmetic (A.D. 1202) played a major role in the spreading of Hindu-Arabic numerals into Europe. It is interesting to note that the left-to-right order of writing numbers was unchanged during these two transitions, although Arabic is written from right to left while Hindu and Latin scholars generally wrote from left to right. A detailed account of the subsequent propagation of decimal numeration and arithmetic into all parts of Europe during the period 1200–1600 has been given by David Eugene Smith in his History of Mathematics 1 (Boston: Ginn and Co., 1923), Chapters 6 and 8.
Decimal notation was applied at first only to integer numbers, not to fractions. Arabic astronomers, who required fractions in their star charts and other tables, continued to use the notation of Ptolemy (the famous Greek astronomer), a notation based on sexagesimal fractions. This system still survives today in our trigonometric units of degrees, minutes, and seconds, and also in our units of time, as a remnant of the original Babylonian sexagesimal notation. Early European mathematicians also used sexagesimal fractions when dealing with noninteger numbers; for example, Fibonacci gave the value
as an approximation to the root of the equation x3 + 2x2 + 10x = 20. (The correct answer is 1◦ 22′ 7″ 42″′ 33IV 4V 38VI 30VII 50VIII 15IX 43X. . . .)
The use of decimal notation also for tenths, hundredths, etc., in a similar way seems to be a comparatively minor change; but, of course, it is hard to break with tradition, and sexagesimal fractions have an advantage over decimal fractions because numbers such as 
can be expressed exactly, in a simple way.
Chinese mathematicians—who never used sexagesimals—were apparently the first people to work with the equivalent of decimal fractions, although their numeral system (lacking zero) was not originally a positional number system in the strict sense. Chinese units of weights and measures were decimal, so that Tsu Ch’ung-Chih (who died in A.D. 500 or 501) was able to express an approximation to π in the following form:
- 3 chang, 1ch‘in, 4ts‘un, 1 fen, 5 li, 9 hao, 2 miao, 7 hu.
Here chang, . . . , hu are units of length; 1 hu (the diameter of a silk thread) equals 1/10 miao, etc. The use of such decimal-like fractions was fairly widespread in China after about 1250.
An embryonic form of truly positional decimal fractions appeared in a 10th-century arithmetic text, written in Damascus by an obscure mathematician named al-Uqlīdisī (“the Euclidean”). He occasionally marked the place of a decimal point, for example in connection with a problem about compound interest, the computation of 135 times (1.1)n for 1 ≤ n ≤ 5. [See A. S. Saidan, The Arithmetic of al-Uqlīdisī (Dordrecht: D. Reidel, 1975), 110, 114, 343, 355, 481–485.] But he did not develop the idea very fully, and his trick was soon forgotten. Al-Samaw’al of Baghdad and Baku, writing in 1172, understood that 
but he had no convenient way to write such approximations down. Several centuries passed before decimal fractions were reinvented by a Persian mathematician, al-Kāshī, who died in 1429. Al-Kāshī was a highly skillful calculator, who gave the value of 2π as follows, correct to 16 decimal places:
)
This was by far the best approximation to π known until Ludolph van Ceulen laboriously calculated 35 decimal places during the period 1586–1610.
Decimal fractions began to appear sporadically in Europe; for example, a so-called “Turkish method” was used to compute 153.5 × 16.25 = 2494.375. Giovanni Bianchini developed them further, with applications to surveying, prior to 1450; but like al-Uqlīdisī, his work seems to have had little influence. Christof Rudolff and François Viète suggested the idea again in 1525 and 1579. Finally, an arithmetic text by Simon Stevin, who independently hit on the idea of decimal fractions in 1585, became popular. Stevin’s work, and the discovery of logarithms soon afterwards, made decimal fractions commonplace in Europe during the 17th century. [For further remarks and references, see D. E. Smith, History of Mathematics 2 (1925), 228–247; V. J. Katz, A History of Mathematics (1993), 225–228, 345–348; and G. Rosińska, Quart. J. Hist. Sci. Tech. 40 (1995), 17–32.]
The binary system of notation has its own interesting history. Many primitive tribes in existence today are known to use a binary or “pair” system of counting (making groups of two instead of five or ten), but they do not count in a true radix-2 system, since they do not treat powers of 2 in a special manner. See The Diffusion of Counting Practices by Abraham Seidenberg, Univ. of Calif. Publ. in Math. 3 (1960), 215–300, for interesting details about primitive number systems. Another “primitive” example of an essentially binary system is the conventional musical notation for expressing rhythms and durations of time.
Nondecimal number systems were discussed in Europe during the seventeenth century. For many years astronomers had occasionally used sexagesimal arithmetic both for the integer and the fractional parts of numbers, primarily when performing multiplication [see John Wallis, Treatise of Algebra (Oxford: 1685), 18–22, 30]. The fact that any integer greater than 1 could serve as radix was apparently first stated in print by Blaise Pascal in De Numeris Multiplicibus, which was written about 1658 [see Pascal’s Œuvres Complètes (Paris: Éditions du Seuil, 1963), 84–89]. Pascal wrote, “Denaria enim ex instituto hominum, non ex necessitate naturæ ut vulgus arbitratur, et sane satis inepte, posita est”; i.e., “The decimal system has been established, somewhat foolishly to be sure, according to man’s custom, not from a natural necessity as most people think.” He stated that the duodecimal (radix twelve) system would be a welcome change, and he gave a rule for testing a duodecimal number for divisibility by nine. Erhard Weigel tried to drum up enthusiasm for the quaternary (radix four) system in a series of publications beginning in 1673. A detailed discussion of radix-twelve arithmetic was given by Joshua Jordaine, Duodecimal Arithmetick (London: 1687).
Although decimal notation was almost exclusively used for arithmetic during that era, other systems of weights and measures were rarely if ever based on multiples of 10, and business transactions required a good deal of skill in adding quantities such as pounds, shillings, and pence. For centuries merchants had therefore learned to compute sums and differences of quantities expressed in peculiar units of currency, weights, and measures; thus they were doing arithmetic in nondecimal number systems. The common units of liquid measure in England, dating from the 13th century or earlier, are particularly noteworthy:
)
Quantities of liquid expressed in gallons, pottles, quarts, pints, etc. were essentially written in binary notation. Perhaps the true inventors of binary arithmetic were British wine merchants!
The first known appearance of pure binary notation was about 1605 in some unpublished manuscripts of Thomas Harriot (1560–1621). Harriot was a creative man who first became famous by coming to America as a representative of Sir Walter Raleigh. He invented (among other things) a notation like that now used for “less than” and “greater than” relations; but for some reason he chose not to publish many of his discoveries. Excerpts from his notes on binary arithmetic have been reproduced by John W. Shirley, Amer. J. Physics 19 (1951), 452–454; Harriot’s discovery of binary notation was first cited by Frank Morley in The Scientific Monthly 14 (1922), 60–66.
The first published treatment of the binary system appeared in the work of a prominent Cistercian bishop, Juan Caramuel de Lobkowitz, Mathesis Biceps 1 (Campaniæ: 1670), 45–48. Caramuel discussed the representation of numbers in radices 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, and 60 at some length, but gave no examples of arithmetic operations in nondecimal systems except in the sexagesimal case.
Ultimately, an article by G. W. Leibniz [Mémoires de l’Académie Royale des Sciences (Paris, 1703), 110–116], which illustrated binary addition, subtraction, multiplication, and division, really brought binary notation into the limelight, and his article is usually referred to as the birth of radix-2 arithmetic. Leibniz later referred to the binary system quite frequently. He did not recommend it for practical calculations, but he stressed its importance in number-theoretical investigations, since patterns in number sequences are often more apparent in binary notation than they are in decimal; he also saw a mystical significance in the fact that everything is expressible in terms of zero and one. Leibniz’s unpublished manuscripts show that he had been interested in binary notation as early as 1679, when he referred to it as a “bimal” system (analogous to “decimal”).
A careful study of Leibniz’s early work with binary numbers has been made by Hans J. Zacher, Die Hauptschriften zur Dyadik von G. W. Leibniz (Frankfurt am Main: Klostermann, 1973). Zacher points out that Leibniz was familiar with John Napier’s so-called “local arithmetic,” a way for calculating with stones that amounts to using a radix-2 abacus. [Napier had published the idea of local arithmetic as part three of his little book Rabdologiæ in 1617; it may be called the world’s first “binary computer,” and it is surely the world’s cheapest, although Napier felt that it was more amusing than practical. See Martin Gardner’s discussion in Knotted Doughnuts and Other Mathematical Entertainments (New York: Freeman, 1986), Chapter 8.]
It is interesting to note that the important concept of negative powers to the right of the radix point was not yet well understood at that time. Leibniz asked James Bernoulli to calculate π in the binary system, and Bernoulli “solved” the problem by taking a 35-digit approximation to π, multiplying it by 1035, and then expressing this integer in the binary system as his answer. On a smaller scale this would be like saying that π ≈ 3.14, and (314)10 = (100111010)2; hence π in binary is 100111010! [See Leibniz, Math. Schriften, edited by C. I. Gerhardt, 3 (Halle: 1855), 97; two of the 118 bits in the answer are incorrect, due to computational errors.] The motive for Bernoulli’s calculation was apparently to see whether any simple pattern could be observed in this representation of π.
Charles XII of Sweden, whose talent for mathematics perhaps exceeded that of all other kings in the history of the world, hit on the idea of radix-8 arithmetic about 1717. This was probably his own invention, although he had met Leibniz briefly in 1707. Charles felt that radix 8 or 64 would be more convenient for calculation than the decimal system, and he considered introducing octal arithmetic into Sweden; but he died in battle before decreeing such a change. [See The Works of Voltaire 21 (Paris: E. R. DuMont, 1901), 49; E. Swedenborg, Gentleman’s Magazine 24 (1754), 423–424.]
Octal notation was proposed also in colonial America before 1750, by the Rev. Hugh Jones, professor at the College of William and Mary [see Gentleman’s Magazine 15 (1745), 377–379; H. R. Phalen, AMM 56 (1949), 461–465].
More than a century later, a prominent Swedish-American civil engineer named John W. Nystrom decided to carry Charles XII’s plans a step further, by devising a complete system of numeration, weights, and measures based on radix-16 arithmetic. He wrote, “I am not afraid, or do not hesitate, to advocate a binary system of arithmetic and metrology. I know I have nature on my side; if I do not succeed to impress upon you its utility and great importance to mankind, it will reflect that much less credit upon our generation, upon our scientific men and philosophers.” Nystrom devised special means for pronouncing hexadecimal numbers; for example, (C0160)16 was to be read “vybong, bysanton.” His entire system was called the Tonal System, and it is described in J. Franklin Inst. 46 (1863), 263–275, 337–348, 402–407. A similar system, but using radix 8, was worked out by Alfred B. Taylor [Proc. Amer. Pharmaceutical Assoc. 8 (1859), 115–216; Proc. Amer. Philosophical Soc. 24 (1887), 296–366]. Increased use of the French (metric) system of weights and measures prompted extensive debate about the merits of decimal arithmetic during that era; indeed, octal arithmetic was even being proposed in France [J. D. Collenne, Le Système Octaval (Paris: 1845); Aimé Mariage, Numération par Huit (Paris: Le Nonnant, 1857)].
The binary system was well known as a curiosity ever since Leibniz’s time, and about 20 early references to it have been compiled by R. C. Archibald [AMM 25 (1918), 139–142]. It was applied chiefly to the calculation of powers, as explained in Section 4.6.3, and to the analysis of certain games and puzzles. Giuseppe Peano [Atti della R. Accademia delle Scienze di Torino 34 (1898), 47–55] used binary notation as the basis of a “logical” character set of 256 symbols. Joseph Bowden [Special Topics in Theoretical Arithmetic (Garden City: 1936), 49] gave his own system of nomenclature for hexadecimal numbers.
The book History of Binary and Other Nondecimal Numeration by Anton Glaser (Los Angeles: Tomash, 1981) contains an informative and nearly complete discussion of the development of binary notation, including English translations of many of the works cited above [see Historia Math. 10 (1983), 236–243].
Much of the recent history of number systems is connected with the development of calculating machines. Charles Babbage’s notebooks for 1838 show that he considered using nondecimal numbers in his Analytical Engine [see M. V. Wilkes, Historia Math. 4 (1977), 421]. Increased interest in mechanical devices for arithmetic, especially for multiplication, led several people in the 1930s to consider the binary system for this purpose. A particularly delightful account of such activity appears in the article “Binary Calculation” by E. William Phillips [Journal of the Institute of Actuaries 67 (1936), 187–221] together with a record of the discussion that followed a lecture he gave on the subject. Phillips began by saying, “The ultimate aim [of this paper] is to persuade the whole civilized world to abandon decimal numeration and to use octonal [that is, radix 8] numeration in its place.”
Modern readers of Phillips’s article will perhaps be surprised to discover that a radix-8 number system was properly referred to as “octonary” or “octonal,” according to all dictionaries of the English language at that time, just as the radix-10 number system is properly called either “denary” or “decimal”; the word “octal” did not appear in English language dictionaries until 1961, and it apparently originated as a term for the base of a certain class of vacuum tubes. The word “hexadecimal,” which has crept into our language even more recently, is a mixture of Greek and Latin stems; more proper terms would be “senidenary” or “sedecimal” or even “sexadecimal,” but the latter is perhaps too risqué for computer programmers.
The comment by Mr. Wales that is quoted at the beginning of this chapter has been taken from the discussion printed with Phillips’s paper. Another man who attended the same lecture objected to the octal system for business purposes: “5% becomes 
per 64, which sounds rather horrible.”
Phillips got the inspiration for his proposals from an electronic circuit that was capable of counting in binary [C. E. Wynn-Williams, Proc. Roy. Soc. London A136 (1932), 312–324]. Electromechanical and electronic circuitry for general arithmetic operations was developed during the late 1930s, notably by John V. Atanasoff and George R. Stibitz in the U.S.A., L. Couffignal and R. Valtat in France, Helmut Schreyer and Konrad Zuse in Germany. All of these inventors used the binary system, although Stibitz later developed excess-3 binary-coded-decimal notation. A fascinating account of these early developments, including reprints and translations of important contemporary documents, appears in Brian Randell’s book The Origins of Digital Computers (Berlin: Springer, 1973).
The first American high-speed computers, built in the early 1940s, used decimal arithmetic. But in 1946, an important memorandum by A. W. Burks, H. H. Goldstine, and J. von Neumann, in connection with the design of the first stored-program computers, gave detailed reasons for making a radical departure from tradition and using base-two notation [see John von Neumann, Collected Works 5, 41–65]. Since then binary computers have multiplied. After a dozen years of experience with binary machines, a discussion of the relative advantages and disadvantages of radix-2 notation was given by W. Buchholz in his paper “Fingers or Fists?” [CACM 2, 12 (December 1959), 3–11].
The MIX computer used in this book has been defined so that it can be either binary or decimal. It is interesting to note that nearly all MIX programs can be expressed without knowing whether binary or decimal notation is being used—even when we are doing calculations involving multiple-precision arithmetic. Thus we find that the choice of radix does not significantly influence computer programming. (Noteworthy exceptions to this statement, however, are the “Boolean” algorithms discussed in Section 7.1; see also Algorithm 4.5.2B.)
There are several different ways to represent negative numbers in a computer, and this sometimes influences the way arithmetic is done. In order to understand these notations, let us first consider MIX as if it were a decimal computer; then each word contains 10 digits and a sign, for example
Equation 2
This is called the signed magnitude representation. Such a representation agrees with common notational conventions, so it is preferred by many programmers. A potential disadvantage is that minus zero and plus zero can both be represented, while they usually should mean the same number; this possibility requires some care in practice, although it turns out to be useful at times.
Most mechanical calculators that do decimal arithmetic use another system called ten’s complement notation. If we subtract 1 from 00000 00000, we get 99999 99999 in this notation; in other words, no explicit sign is attached to the number, and calculation is done modulo 1010. The number −12345 67890 would appear as
Equation 3
in ten’s complement notation. It is conventional to regard any number whose leading digit is 5, 6, 7, 8, or 9 as a negative value in this notation, although with respect to addition and subtraction there is no harm in regarding (3) as the number +87654 32110 if it is convenient to do so. Notice that there is no problem of minus zero in such a system.
The major difference between signed magnitude and ten’s complement notations in practice is that shifting right does not divide the magnitude by ten; for example, the number –11 = . . . 99989, shifted right one, gives . . . 99998 = –2 (assuming that a shift to the right inserts “9” as the leading digit when the number shifted is negative). In general, x shifted right one digit in ten’s complement notation will give ⌊x/10⌋, whether x is positive or negative.
A possible disadvantage of the ten’s complement system is the fact that it is not symmetric about zero; the p-digit negative number 500 . . . 0 is not the negative of any p-digit positive number. Thus it is possible that changing x to –x will cause overflow. (See exercises 7 and 31 for a discussion of radix-complement notation with infinite precision.)
Another notation that has been used since the earliest days of high-speed computers is called nines’ complement representation. In this case the number −12345 67890 would appear as
Equation 4
Each digit of a negative number (–x) is equal to 9 minus the corresponding digit of x. It is not difficult to see that the nines’ complement notation for a negative number is always one less than the corresponding ten’s complement notation. Addition and subtraction are done modulo 1010 – 1, which means that a carry off the left end is to be added at the right end. (See the discussion of arithmetic modulo w − 1 in Section 3.2.1.1.) Again there is a potential problem with minus zero, since 99999 99999 and 00000 00000 denote the same value.
The ideas just explained for radix-10 arithmetic apply in a similar way to radix-2 arithmetic, where we have signed magnitude, two’s complement, and ones’ complement notations. Two’s complement arithmetic on n-bit numbers is arithmetic modulo 2n; ones’ complement arithmetic is modulo 2n − 1. The MIX computer, as used in the examples of this chapter, deals only with signed magnitude arithmetic; however, alternative procedures for complement notations are discussed in the accompanying text when it is important to do so.
Detail-oriented readers and copy editors should notice the position of the apostrophe in terms like “two’s complement” and “ones’ complement”: A two’s complement number is complemented with respect to a single power of 2, while a ones’ complement number is complemented with respect to a long sequence of 1s. Indeed, there is also a “twos’ complement notation,” which has radix 3 and complementation with respect to (2 . . . 22)3.
Descriptions of machine language often tell us that a computer’s circuitry is set up with the radix point at a particular place within each numeric word. Such statements should usually be disregarded. It is better to learn the rules concerning where the radix point will appear in the result of an instruction if we assume that it lies in a certain place beforehand. For example, in the case of MIX we could regard our operands either as integers with the radix point at the extreme right, or as fractions with the radix point at the extreme left, or as some mixture of these two extremes; the rules for the appearance of the radix point after addition, subtraction, multiplication, or division are straightforward.
It is easy to see that there is a simple relation between radix b and radix bk:
Equation 5
)
where
see exercise 8. Thus we have simple techniques for converting at sight between, say, binary and hexadecimal notation.
Many interesting variations on positional number systems are possible in addition to the standard b-ary systems discussed so far. For example, we might have numbers in base (–10), so that
)
Here the individual digits satisfy 0 ≤ ak ≤ 9 just as in the decimal system. The number 12345 67890 appears in the “negadecimal” system as
Equation 6
since the latter represents 10305070900 – 9070503010. It is interesting to note that the negative of this number, –12345 67890, would be written
Equation 7
and, in fact, every real number whether positive or negative can be represented without a sign in the –10 system.
Negative-base systems were first considered by Vittorio Grünwald [Giornale di Matematiche di Battaglini 23 (1885), 203–221, 367], who explained how to perform the four arithmetic operations in such systems; Grünwald also discussed root extraction, divisibility tests, and radix conversion. However, his work seems to have had no effect on other research, since it was published in a rather obscure journal, and it was soon forgotten. The next publication about negative-base systems was apparently by A. J. Kempner [AMM 43 (1936), 610–617], who discussed the properties of noninteger radices and remarked in a footnote that negative radices would be feasible too. After twenty more years the idea was rediscovered again, this time by Z. Pawlak and A. Wakulicz [Bulletin de l’Académie Polonaise des Sciences, Classe III, 5 (1957), 233–236; Série des sciences techniques 7 (1959), 713–721], and also by L. Wadel [IRE Transactions EC-6 (1957), 123]. Experimental computers called SKRZAT 1 and BINEG, which used –2 as the radix of arithmetic, were built in Poland in the late 1950s; see N. M. Blachman, CACM 4 (1961), 257; R. W. Marczyński, Ann. Hist. Computing 2 (1980), 37–48. For further references see IEEE Transactions EC-12 (1963), 274–277; Computer Design 6 (May 1967), 52–63. There is evidence that the idea of negative bases occurred independently to quite a few people. For example, D. E. Knuth had discussed negative-radix systems in 1955, together with a further generalization to complex-valued bases, in a short paper submitted to a “science talent search” contest for high-school seniors.
The base 2i gives rise to a system called the “quater-imaginary” number system (by analogy with “quaternary”), which has the unusual feature that every complex number can be represented with the digits 0, 1, 2, and 3 without a sign. [See D. E. Knuth, CACM 3 (1960), 245–247; 4 (1961), 355.] For example,
)
Here the number (a2n . . . a1a0.a–1 . . . a–2k)2i is equal to
)
so conversion to and from quater-imaginary notation reduces to conversion to and from negative quaternary representation of the real and imaginary parts. The interesting property of this system is that it allows multiplication and division of complex numbers to be done in a fairly unified manner without treating real and imaginary parts separately. For example, we can multiply two numbers in this system much as we do with any base, merely using a different carry rule: Whenever a digit exceeds 3 we subtract 4 and carry –1 two columns to the left; when a digit is negative, we add 4 to it and carry +1 two columns to the left. The following example shows this peculiar carry rule at work:
A similar system that uses just the digits 0 and 1 may be based on 
, but this requires an infinite nonrepeating expansion for the simple number “i” itself. Vittorio Grünwald proposed using the digits 0 and 
in odd-numbered positions, to avoid such a problem; but that actually spoils the whole system [see Commentari dell’Ateneo di Brescia (1886), 43–54].
Another “binary” complex number system may be obtained by using the base i − 1, as suggested by W. Penney [JACM 12 (1965), 247–248]:
)
In this system, only the digits 0 and 1 are needed. One way to demonstrate that every complex number has such a representation is to consider the interesting set S shown in Fig. 1; this set is, by definition, all points that can be written as ∑k≥1ak(i − 1)−k, for an infinite sequence a1, a2, a3, . . . of zeros and ones. It is also known as the “twindragon fractal” [see M. F. Barnsley, Fractals Everywhere, second edition (Academic Press, 1993), 306, 310]. Figure 1 shows that S can be decomposed into 256 pieces congruent to 
S. Notice that if the diagram of S is rotated counterclockwise by 135°, we obtain two adjacent sets congruent to () S, because (i − 1)S = S ∪ (S + 1). For details of a proof that S contains all complex numbers that are of sufficiently small magnitude, see exercise 18.
)
Fig. 1. The fractal set S called the “twindragon.”
Perhaps the prettiest number system of all is the balanced ternary notation, which consists of radix-3 representation using –1, 0, and +1 as “trits” (ternary digits) instead of 0, 1, and 2. If we let the symbol 
stand for –1, we have the following examples of balanced ternary numbers:
One way to find the representation of a number in the balanced ternary system is to start by representing it in ordinary ternary notation; for example,
(A very simple pencil-and-paper method for converting to ternary notation is given in exercise 4.4–12.) Now add the infinite number . . . 11111.11111 . . . in ternary notation; we obtain, in the example above, the infinite number
Finally, subtract . . . 11111.11111 . . . by decrementing each digit; we get
Equation 8
This process may clearly be made rigorous if we replace the artificial infinite number . . . 11111.11111 . . . by a number with suitably many ones.
The balanced ternary number system has many pleasant properties:
- The negative of a number is obtained by interchanging 1 and .
- The sign of a number is given by its most significant nonzero trit, and in general we can compare any two numbers by reading them from left to right and using lexicographic order, as in the decimal system.
- The operation of rounding to the nearest integer is identical to truncation; in other words, we simply delete everything to the right of the radix point.
Addition in the balanced ternary system is quite simple, using the table
)
(The three inputs to the addition are the digits of the numbers to be added and the carry digit.) Subtraction is negation followed by addition. Multiplication also reduces to negation and addition, as in the following example:
Representation of numbers in the balanced ternary system is implicitly present in a famous mathematical puzzle, commonly called “Bachet’s problem of weights”—although it was already stated by Fibonacci four centuries before Bachet wrote his book, and by 
abarī in Persia more than 100 years before Fibonacci. [See W. Ahrens, Mathematische Unterhaltungen und Spiele 1 (Leipzig: Teubner, 1910), Section 3.4; H. Hermelink, Janus 65 (1978), 105–117.] Positional number systems with negative digits were invented by J. Colson [Philos. Trans. 34 (1726), 161–173], then forgotten and rediscovered about 100 years later by Sir John Leslie [The Philosophy of Arithmetic (Edinburgh: 1817); see pages 33–34, 54, 64–65, 117, 150], and by A. Cauchy [Comptes Rendus Acad. Sci. 11 (Paris, 1840), 789–798]. Cauchy pointed out that negative digits make it unnecessary for a person to memorize the multiplication table past 5 × 5. A claim that such number systems were known in India long ago [J. Bharati, Vedic Mathematics (Delhi: Motilal Banarsidass, 1965)] has been refuted by K. S. Shukla [Mathematical Education 5, 3 (1989), 129–133]. The first true appearance of “pure” balanced ternary notation was in an article by Léon Lalanne [Comptes Rendus Acad. Sci. 11 (Paris, 1840), 903–905], who was a designer of mechanical devices for arithmetic. Thomas Fowler independently invented and constructed a balanced ternary calculator at about the same time [see Report British Assoc. Adv. Sci. 10 (1840), 55; 11 (1841), 39–40]. The balanced ternary number system was mentioned only rarely for the next 100 years, until the development of the first electronic computers at the Moore School of Electrical Engineering in 1945–1946; at that time it was given serious consideration as a possible replacement for the decimal system. The complexity of arithmetic circuitry for balanced ternary arithmetic is not much greater than it is for the binary system, and a given number requires only ln 2/ ln 3 ≈ 63% as many digit positions for its representation. Discussions of the balanced ternary system appear in AMM 57 (1950), 90–93, and in High-speed Computing Devices, Engineering Research Associates (McGraw–Hill, 1950), 287–289. The experimental Russian computer SETUN was based on balanced ternary notation [see CACM 3 (1960), 149–150], and perhaps the symmetric properties and simple arithmetic of this number system will prove to be quite important someday—when the “flip-flop” is replaced by a “flip-flap-flop.”
Positional notation generalizes in another important way to a mixed-radix system. Given a sequence of numbers 〈bn〉 (where n may be negative), we define
Equation 9
)
In the simplest mixed-radix systems, we work only with integers; we let b0, b1, b2, . . . be integers greater than one, and deal only with numbers that have no radix point, where an is required to lie in the range 0 ≤ an < bn.
One of the most important mixed-radix systems is the factorial number system, where bn = n + 2. Using this system, which was known in 13th-century India, we can represent every positive integer uniquely in the form
Equation 10
where 0 ≤ ck ≤ k for 1 ≤ k ≤ n, and cn ≠ 0. (See Algorithms 3.3.2P and 3.4.2P.)
Mixed-radix systems are familiar in everyday life, when we deal with units of measure. For example, the quantity “3 weeks, 2 days, 9 hours, 22 minutes, 57 seconds, and 492 milliseconds” is equal to
The quantity “10 pounds, 6 shillings, and thruppence ha’penny” was once equal to 
pence in British currency, before Great Britain changed to a purely decimal monetary system.
It is possible to add and subtract mixed-radix numbers by using a straightforward generalization of the usual addition and subtraction algorithms, provided of course that the same mixed-radix system is being used for both operands (see exercise 4.3.1–9). Similarly, we can easily multiply or divide a mixed-radix number by small integer constants, using simple extensions of the familiar pencil-and-paper methods.
Mixed-radix systems were first discussed in full generality by Georg Cantor [Zeitschrift für Math. und Physik 14 (1869), 121–128]. Exercises 26 and 29 give further information about them.
Several questions concerning irrational radices have been investigated by W. Parry, Acta Math. Acad. Sci. Hung. 11 (1960), 401–416.
Besides the systems described in this section, several other ways to represent numbers are mentioned elsewhere in this series of books: the combinatorial number system (exercise 1.2.6–56); the Fibonacci number system (exercises 1.2.8–34, 5.4.2–10); the phi number system (exercise 1.2.8–35); modular representations (Section 4.3.2); Gray code (Section 7.2.1); and Roman numerals (Section 9.1).