J2ee Web Hosting, Perl Scripting And Developing Blog

4.1 POSITIONAL NUMBER SYSTEMS 195 20. [HM%] (David W. Matula.) Consider a decimal number system that uses the digits D = {-l,O, 8,17,26,35,44,53,62,71} instead of (0, 1, ,9}. The result of exercise 19 implies (as in exercise 18) that all real numbers have an infinite decimal expansion using digits from D. In the usual decimal system, exercise 13 points out that some numbers have two representations. (a) Find a real number that has more than two D-decimal repre- sentations. (b) Show that no real number has infinitely many D-decimal representations. (c) Show that uncountably many numbers have two or more D-decimal representations. b 21. [MZ?] (C. E. Shannon.) Can every real number (positive, negative, or zero) be expressed in a balanced decimal system, i.e., in the form xkcn aklOk, for some integer n and some sequence a,, anPl, an-s, . , where each ai is one of the ten numbers {-4$,-3~,-2~,-1~,–2, I Z,1 11 2, 2&,3$, 4$}? (Note that zero is not one of the allowed digits, but we implicitly assume that a,+~, a,+~, are zero.) Find all representations of zero in this number system, and find all representations of unity. 22. [HM25] Let cy = -Crn>i 10Vm2. Given E > 0 and any real number x, prove that there is a decimal representation such that 0 < 1~ - xockcn ~10~1 < E, where each ak is allowed to be only one of the three values 0, 1, or o. (Note that no negative powers of 10 are used in this representation!) 23. [HM30] Let D be a set of b real numbers such that every positive real number has a representation xkcn. akbk with all ak 6 D. Exercise 20 shows that there may be many numbers without unique representations; but prove that the set 7 of all such numbers has measure zero. 24. [M35] Find infinitely many different sets D of ten nonnegative integers satisfying the following three conditions: (i) gcd(D) = 1; (ii) 0 E D; (iii) every positive real number can be represented in the form xkcn -~10 with all ak E D. 25. [A&5] (S. A. Cook.) Let b, u, and w be positive integers, where b > 2 and 0 < u < b . Show that the base b representation of u/v does not contain a run of m consecutive digits equal to b - 1, anywhere to the right of the radix point. (By convention, no runs of infinitely many (b -1) s are permitted in the standard base b representation.) b 26. [HAJ30] (N. S. Mendelsohn.) Let (&) b e a sequence of real numbers defined for all integers n, –co < n < 00, such that Pn < &+I; lim &=co; lim & = 0. n-02 n—o3 Let (c,) be an arbitrary sequence of positive integers that is defined for all integers n, -co < n < cu. Let us say that a number x has a generalized representation if there is an integer n and an infinite sequence of integers a,, anel, an-s, . such that x = Cksn akpk, where a, # 0, 0 < ak < ck, and ak < ck for infinitely many k. Show that every positive real number z has exactly one generalized representation if and only if &+i = c,, 7Lckpk for all n. (Consequently, the mixed-radix systems with integer bases have thisproperty; and mixed-radix systems with pi = (co + l)&, PZ = (ci + l)(co + l)&, . , p-1 = &/(c.-1 + l), . are the most general number systems of this type.)

194 ARITHMETIC 4.1 5. (001 Explain why a negative integer in nines complement notation has a repre- sentation in ten s complement notation that is always one greater, if the representations are regarded as positive. 6. [16] What are the largest and smallest pbit integers that can be represented in (a) signed-magnitude binary notation (including one bit for the sign), (b) two s complement notation, (c) ones complement notation? 7. [M.Z0] The text defines ten s complement notation only for integers represented in a single computer word. Is there a way to define a ten s complement notation for all real numbers, having infinite precision, analogous to the text s definition? Is there a similar way to define a nines complement notation for all real numbers? 8. [MIo] Prove Eq. (5). b 9. [15] Change the following octal numbers to hexadecimal notation, using the hexadecimal digits 0, 1, . . . , F: 12; 5655; .2550.276; 76545336; 3726755. 10. [M.%?] Generalize Eq. (5) to mixed-radix notation. 11. [z?] Design an algorithm that uses the -2 number system to compute the sum of (a,. . alao)- and (b, . . blbo)-l, obtaining the answer (c,+z . c~co)-~. 12. [~3] Specify algorithms that convert (a) the binary signed magnitude number f(arl . . . ao)z to its negabinary form (&+I . . . bo)-2; and (b) the negabinary number Pn+l . . . bo)-z to its signed magnitude form &(a,+1 . . . a0)2. b 13. [A&1] In the decimal system there are some numbers with two infinite decimal expansions; e.g., 2.3599999.. . = 2.3600000.. . Does the negadecimal (base -10) system have unique expansions, or are there real numbers with two different infinite expansions in this base also? 14. [14] Multiply (11321)2i by itself in the quater-imaginary system using the method illustrated in the text. 15. [A4.24] What are the sets s={~m~yk~ ak an allowable digit }, - analogous to Fig. 1, for the negative decimal and for the quater-imaginary number systems? 16. [A&.24] Design an algorithm to add 1 to (a,. . . ala~)~-l in the i-l number system. 17. [A&N] It may seem peculiar that i -1 has been suggested as a number-system base, instead of the similar but intuitively simpler number i + 1. Can every complex number a+ bi, where a and b are integers, be represented in a positional number system to base i f 1, using only the digits 0 and l? 18. [HiV3.2] Show that the set S of Fig. 1 is a closed set that contains a neighborhood of the origin. (Consequently, every complex number has a binary representation to base i -1.) b 19. [Z3] (David W. Matula.) Let D be a set of b integers, containing exactly one solution to the congruence 2 3 j (modulo b) for 0 5 j < b. Prove that all integers m (positive, negative, or zero) can be represented in the form m = (a,. . . aO)b, where all the a3 are in D, if and only if all integers in the range 1 5 m < u can be so represented, where 1 = -max{ a ( a E D}/(b -l), u = -min{ a 1 a E D}/(b -1). For example, D = {-l,O,. . , b -2} satisfies the conditions for all b 2 3. [Hint: Design an algorithm that constructs a suitable representation.]

4.1 POSITIONAL NUMBER SYSTEMS 193 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 seconds 7, 24, 60, 60; 10004g2 1 3, 2, , 22, 57; The quantity 10 pounds, 6 shillings, and thruppence ha penny was once equal to [loI SE> 1i! 41 pence in British currency, before Great Britain changed to a purely debirnil monetary system. It is possible to add and subtract mixed-radix numbers by using a straightfor- ward 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 fiir Math. und Physik 14 (1869), 121-1281. Exercises 26 and 29 give further information about them. Some questions concerning irrational radices have been investigated by W. Parry, Acta Mathematics, 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 binomial 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). EXERCISES 1. [IS] Express -10, -9, , 9, 10 in the number system whose base is -2. b 2. [,%$I Consider the following four number systems: (a) binary (signed magnitude); (b) negabinary (radix -2); (c) balanced ternary; and (d) radix b = &. Use each of these four number systems to express each of the following three numbers: (i) -49; (ii) -33 (show the repeating cycle); (iii) 7r (to a few significant figures). 3. [Zoo] Express -49 + i in the quater-imaginary system. 4. [IS] Assume that we have a MIX program in which location A contains a number for which the radix point lies between bytes 3 and 4, while location B contains a number whose radix point lies between bytes 2 and 3. (The leftmost byte is number 1). Where will the radix point be, in registers A and X, after the following instructions? 4 LDA A b) LDA A WJL BD SRAX 5 DIV B 1

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