Web And Email Hosting, Jsp Web Hosting Blog

192 ARITHMETIC 4.1 Representation of numbers in the balanced ternary system is implicitly present in a famous mathematical puzzle, which is commonly called Bachet s problem of weights although it was already stated by Fibonacci four centuries before Bachet wrote his book. [See W. Ahrens, Mathematische Unterhdtungen und Spiele 1 (Leipzig: Teubner, 1910), Section 3.4.1 Positional number systems with negative digits have apparently been known for more than 1000 years in India; see J. Bharati, Medic Mathematics (Delhi: Motilal Banarsidass, 1965). They were independently rediscovered by J. Colson [Philos. Trans. 34 (1726), 161-1731, and by Sir John Leslie [The Philosophy of Arithmetic (Edinburgh, 1817); see pp. 33-34, 54, 64-65, 117, 1501; and also by A. Cauchy [Comptes Rendus 11 (Paris: 1840), 789-7981, who pointed out that negative digits make it unnecessary for a person to memorize the multiplication table past 5 X 5. The first true appearance of pure balanced ternary notation was in an article by Lkon Lalanne [Comptes Rendus 11 (Paris: 1840), 903-9051, who was a designer of mechanical devices for arithmetic. The system was mentioned only rarely for 100 years after Lalanne s paper, 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 along with the binary system 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 In 2/ In 3 =t: 63% as many digit positions for its representation. Discussions of the balanced ternary number 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-1501, and perhaps the symmetric properties and simple arithmetic of this number system will prove to be quite important some day-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 * . . , a3, a2, al, a0; a-1, a-2, . * * I . ..) b3, bz, bl, bo; b-l, b-2, . . . 1 (9) = .+.+u3bzblbo +uzblbo+ulbo +a0 +c~~/b-~ +c~~/b-~b-~ +…. In the simplest mixed-radix systems, we work only with integers; we let bo, bl, b . . . be integers greater than one, and deal only with numbers that have no r?dix point, where a, is required to lie in the range 0 < a, < b,. One of the most important mixed-radix systemsis the factorial number system, where b, = 7~ + 2. Using this system, we can represent every positive integer uniquely in the form c, n! + cm-1 (n - l)! + .*. + c2 2! + Cl, (10) where 0 2 ck < k for 1 5 k < n, and cn # 0. (See Algorithm 3.3.2P.)

4.1 POSITIONAL NUMBER SYSTEMS 191 Balanced ternary Decimal 10T 8 1 lTO.11 328 1 1 10.1 1 -325 1110 -33 0.1 1 1 1 1.. . 4 One way to find the representation of a number in the balanced ternary system is to start by representing it in ternary notation; for example, 208.3 = (21201.022002200220.. .)3. (A very simple pencil-and-paper method for converting to ternary notation is given in exercise 4.4-12.) Now add the infinite number . . .lllll.lllll.. . in ternary notation; we obtain, in the above example, the infinite number (. . .11111210012.210121012101.. .)s. Finally, subtract . ..11111.11111… by decrementing each digit; we get 208.3 = (lOllOl.lOiOlOiOlOiO.. . )s. (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: a) The negative of a number is obtained by interchanging 1 and i. b) 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. c) The operation of rounding to the nearest integer is identical to truncation (i.e., deleting everything to the right of the radix point). Addition in the balanced ternary system is quite simple, using the table iiiiiiiiioooooooooiiiiiill~ iiioooiiiiiioooiiiiiiooo~~ l ioiio~ioiioiioiioiiolTolTolio~ Toil 111 i 0 i 0 iii i 0 i 0 i 0 iii i 0 10 iii iii10 (The three inputs to the addition are the digits of the numbers to be added and the carry digits.) Subtraction is negation followed by addition; and multiplication also reduces to negation and addition, as in the following example: iioi [I71iioi 1171 ii01 ii010 iioi 0111101 P891

190 ARITHMETIC 4.1 I -l+i +i -l+i -1-i -i Fig. 1. The set S. (Illustration by P. M. Farmwald, R. W. Gosper, and R. E. Maas.) 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 Ck,l ak(i -1)-k, for an infinite sequence al, a2, us, . . . of zeros and ones. Figure-l shows that S can be decomposed into 256 pieces congruent to &S; note that if tjhe diagram of S is rotated counterclockwise by 135 , we obtain two adjacent sets congruent to (l/&?)S (since (i -1)s = S U (S + 1)). For details of a proof that S contains all complex numbers that are of sufficiently small magnitude, see exercise 18. Perhaps the prettiest number system of all is the balanced ternary notation, which consists of base-3 representation using -1, 0, and +l as trits (ternary digits) instead of 0, 1, and 2. If we use the symbol i to stand for -1, we have the following examples of balanced ternary numbers:

4.1 POSITIONAL NUMBER SYSTEMS 189 (1957), 1231. For further references see IEEE Transactions EC-12 (1963), 274- 276; 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-base 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, CACA4 3 (1960), 245-247.1 For example, (11210.31)s, = 1 . 16 + 1 . (-8i) + 2. (-4) + 1 . (2i) + 3 * (-fi) + 1(-a) = 7$ -73i. Here the number (uzn . . . alao.a-1 . . . u-zk)zi is equal to (a2n.. . u2u()*u-2.. . u-2&4 + 2i(u2n–1.. .U3Ul.U-1.. .u–2k+l)-& 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 +l two columns to the left. A study of the following example shows this peculiar carry rule at work: 12231 [9 - lOi] 12231 [9 - lOi] 12231 10320213 13022 13022 12231 021333121 [-19 -18Oi] A similar system that uses just the digits 0 and 1 may be based on &i, but this requires an infinite nonrepeating expansion for the simple number i itself. Vittorio Griinwald proposed using the digits 0 and l/d in odd-numbered positions, to avoid such a problem, but this actually spoils the whole system [cf. Commentari dell Ateneo di Brescia (1886), 43-541. Another binary complex number system may be obtained by using the base i -1, as suggested by W. Penney [JACM 12 (1965), 247-2481: ( . . . a4a3a2alao.a-l . . . )2-l = . ..- 4a4 + (2+2i)a3 -2ia2 + (i-l)aI + uo -$(i+l)a-I + + . +.

188 ARITHMETIC 4.1 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 in each result are straightforward. It is easy to see that there is a simple relation between radix b and radix bk: (. . . U~UQU~UO.U-1U-2.. . )* = (. . .A3A2A1&.A-1A-z.. . )* , (5) where A3 = (Uk,+k-1 . . . Ukj+lUkj)b; see exercise 8. Thus we have simple techniques for converting at sight between, say, binary and octal notation. Many interesting variations on positional number systems are possible be- sides the standard b-ary systems discussed so far. For example, we might have numbers in base (-lo), so that (. . . U3U2UlUo.UplU-2.. . j-l, = . . . + u3(-10)3 + u2(-10)2 + u&loy + a0 + . . . ..- = . 1000u3 + loo@ -10Ul + a0 -&U-l + &ju–2 -. . . . Here the individual digits satisfy 0 < ak 5 9 just as in the decimal system. The number 12345 67890 appears in the negadecimal system as (193755 73910)-10, (6) since the latter represents 10305070900 -9070503010. It is interesting to note that the negative of this number, -12345 67890, would be written (28466 48290)-10, (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 Griinwald [Giornale di matematiche di Battaglini 23 (1885), 203-221, 3671, who explained how to perform the four arithmetic operations in such systems; Griinwald also discussed root extraction, divisibility tests, and radix conversion. However, since his work was published in a rather obscure journal, it seems to have had no effect on other research, and it was soon forgotten. The next publication about negative- base systems was apparently by A. J. Kempner [AMM 43 (1936), 610-6171, who discussed the properties of non-integer 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 1 Academie Polonaise des Sciences, Classe III, 5 (1957), 233-236; %rie des sciences techniques 7 (1959), 713-7211, and also by L. Wade1 [IRE Transactions EC-6

4.1 POSITIONAL NUMBER SYSTEMS 187 99999 99999 in this notation; in other words, no explicit sign is attached to the number, and calculation is done modulo lOlo. The number -12345 67890 would appear as 8765432110 (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 f87654 32110 if it is convenient to do so. Note that there is no problem of minus zero in such a system. The major difference between signed magnitude and ten s complement nota- tions 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 t,o the right inserts 9 as the leading digit when the num- ber shifted is negative). In general, z shifted right one digit in ten s complement notation will give Lz/lO], whether z is positive or negative. A possible disadvantage of the ten s complement system is the fact that it is not symmetric about zero; the largest negative number representable in p digits is 500.. . 0, and it is not the negative of any p-digit positive number. Thus it is possible that changing LX to –z 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 87654 32109. (4 Each digit of a negative number (-Z) is equal to 9 minus the corresponding digit of 5. 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 lOlo -1, which means that a carry off the left end is to be added at the right end. (Cf. 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. 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. Most computer manuals tell us that the machine s circuitry assumes that the radix point is situated in a particular place within each computer word. This advice 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

186 ARITHMETIC 4.1 senidenary or sedecimal or even sexadecimal, but the latter is perhaps too risquk 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 3.i462 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. Sot. London Al36 (1932), 312-3241. Electromechanical and electronic circuitry for general arithmetic operations was developed during the late 193Os, 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 194Os, 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 the decision to make a radical departure from tradition and to use base-two notation [see John von Neumann, Collected Works 5, 41-651. Since then binary computers have multi- plied. 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 (December 1959), 3-111. 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 arith- metic. 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 methods for representing negative numbers in a computer, and this sometimes influences the way arithmetic is done. In order to understand these other notations, let us first consider MIX as if it were a decimal computer; then each word contains 10 digits and a sign, for example -12345 67890. (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

4.1 POSITIONAL NUMBER SYSTEMS 185 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; e.g., (B0160)1e, was to be read ?ybong, 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 Sot. 24 (1887), 296-3661. 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 Prance [J. D. Colenne, Le systkme octaval (Paris: 1845); Aim6 Mariage, Numeration 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 [A&&f 25 (1918), 139-1421. 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), 491 gave his own system of nomenclature for hexadecimal numbers. The book History of Binary and Other Nondecimal Numeration by Anton Glaser (privately printed, 1971) contains an informative and nearly complete discussion of the development of binary notation, including English translations of many of the works cited above. Much of the recent history of number systems is connected with the devel- opment of calculating machines. Charles Babbage s notebooks for 1838 show that he considered using nondecimal numbers in his Analytical Engine [cf. M. V. Wilkes, Historia Math. 4 (1977), 4211. 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-2211 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 [i.e., 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 Lhexadecimal, which has crept into our language even more recently, is a mixture of Greek and Latin stems; more proper terms would be

184 ARITHMETIC 4.1 Ultimately, an article by G. W. Leibniz [Memoires de 1 Academie Royale des Sciences (Paris: 1703), 110-1161, which illustrated binary addition, subtraction, multiplication, and division, really brought binary notation into the limelight, and this 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 inves- tigations, 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. Leibnia (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 an appendix to his little book Rhabdologia 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 Scientific American 228 (April 1973), 106-111.1 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 r in the binary system, and Bernoulli solved the problem by taking a 35-digit approximation to 7r, 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 r = 3.14, and (314)10 = (100111010)~; hence T in binary is 100111010! [See Leibniz, Math. Schriften, ed. by K. Gehrhardt, 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 7r. 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 introdu.cing 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.1 Octal notation was proposed also in colonial America before 1750, by the Rev. Hugh Jones, rector of a parish in Maryland [cf. Gentleman s Magazine 15 (1745), 377-379; H. R. Phalen, AMM 56 (1949), 461-4651. 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

4.1 POSITIONAL NUMBER SYSTEMS 183 1685), 18-22, 301. 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 QXuvres Compl&tes (Paris: hditions de Seuil, 1963), 84-891. Pascal wrote, Denaria enim ex institute hominum, non ex necessitate nature 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 would 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 many 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; and this was actually arithmetic in a nondecimal number system. The common units of liquid measure in England, dating from the 13th century or earlier, are particularly noteworthy: 2 gills = 1 chopin 2 demibushels = 1 bushel or firkin 2 chopins = 1 pint 2 firkins = 1 kilderkin 2 pints = 1 quart 2 kilderkins = 1 barrel 2 quarts = 1 pottle 2 pottles = 1 gallon 2 barrels = 1 hogshead 2 gallons = 1 peck 2 hogsheads = 1 pipe 2 pecks = 1 demibushel 2 pipes = 1 tun Quantities of liquid expressed in gallons, pottles, quarts, pints, etc. were essen- tially written in binary notation. Perhaps the true inventors of binary arithmetic were English 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. The first published discussion of the binary system was given in a comparatively little-known work by a Spanish bishop, Juan Caramuel Lobkowitz, Mathesis biceps 1 (Campan&, 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 for the trivial operation of adding unity).