Web And Email Hosting, Jsp Web Hosting Blog

4.1 POSITIONAL NUMBER SYSTEMS 197 b 31. [M3.5] A generalization of two s complement arithmetic, called 2-adic numbers, was invented about 1900 by K. Hensel. (In fact he treated p-adic numbers, for any prime p.) A 2-adic number may be regarded as a binary number u = (. .u3u2u1u0.u-1.. .U-&, whose representation extends infinitely far to the left, but only finitely many places to the right, of the binary point. Addition, subtraction, and multiplication of 2-adic numbers are done according to the ordinary procedures of arithmetic, which can in principle be extended indefinitely to the left. For example, 7=(… 000000000000111)2 ) = (. . .110110110110111)2 -7=(… 111111111111001)2 -f = (. . .001001001001001)2 $ = ( .000000000000001.11)2 & = (. .110011001100110.1)2 J–7 = (. .100000010110101)~ or (. .011111101001011)~ Here 7 appears as the ordinary binary integer seven, while -7 is its two s comple- ment (extending infinitely to the left); it is easy to verify that the ordinary procedure for addition of binary numbers will give -7 + 7 = ( . 00000)s = 0, when the procedure is continued indefinitely. The values of 3 and -+ are the unique 2-adic numbers that, when formally multiplied by 7, give 1 and -1, respectively. The values of 3 and & are examples of 2-adic numbers that are not 2-adic integers, since they have nonzero bits to the right of the binary point. The two values of J-7, which are negatives of each other, are the only 2-adic numbers that, when formally squared, yield the value (. . .111111111111001)2. a) Prove that any 2-adic number u can be divided by any nonzero 2-adic number v to obtain a unique 2-adic number w satisfying u = VW. (Hence the set of 2-adic numbers forms a field ; cf. Section 4.6.1.) b) Prove that the 2-adic representation of the rational number -1/(2n + 1) may be obtained as follows, when n is a positive integer: First find the ordinary binary expansion of +1/(2n + l), which has the periodic form (O.cucucu.. .)z for some string o of O s and 1 s. Then -1/(2n + 1) is the 2-adic number (. . ocycy)~. c) Prove that the representation of a 2-adic number u is ultimately periodic (that is, ZLN+X = UN for all large N, for some x 2 1) if and only if u is rational (that is, u = m/n, for some integers m and n). d) Prove that, when n is an integer, fi is a 2-adic number if and only if it satisfies nmod22k+3 = 22k for some nonnegative integer k. (Thus, the possibilities are either n mod S = 1, or n mod 32 = 4, etc.) 32. [M40] (I. Z. Ruzsa.) Prove that there are infinitely many integers whose ternary representation uses only O s and l s and whose quinary representation uses only O s, l s, and 2 s. 33. [M40] (D. A. Klarner.) Let D be any set of integers, let b be any positive integer, and let k, be the number of distinct integers that can be written as n-digit numbers (a,-1 . . . alac)b to base b with digits a, in D. Prove that the sequence (k,) satisfies a linear recurrence relation, and explain how to compute the generating function C,, kd. Illustrate your algorithm in the case b = 3 and D = (-1, 0,3}.

196 ARITHMETIC 4.1 27. [M.Zl] Show that every nonzero integer has a unique reversing binary representa- tion 2-3 -2el + . + (-1)9, where es < el < .. < et. b 28. [M24] Show that every nonzero complex number of the form a + bi where a and b are integers has a unique revolving binary representation (1 + i) + i(l + i) -(1 + i) -i(1 + i) + . . + ?(l + i) , where es < el < ... < et. (Cf. exercise 27.) 29. [M35] (N. G. de Bruijn.) Let SO, S1, Ss, be sets of nonnegative integers; we will say that the collection {SO, ,571, Sz, . } has Property B if every nonnegative integer n can be written in the form n = so + Sl + s2 + . , s3 E s,, in exactly one way. (Property B implies that 0 E S, for all j, since n = 0 can only be represented as 0 + 0 + 0 + . . . .) Any mixed-radix number system with radices bo, bl, bz, . provides an example of a collection of sets satisfying Property B, if we let S, = (0, B3, , (b, -l)B,}, where B, = bobI . . b,-1; here the representation of n = so + Sl + s2 + '.. corresponds in an obvious manner to its mixed-radix repre- sentation (9). Furthermore, if the collection {SO, Si, Sz, . } has Property B, and if Ao, AI, A2, . . is any partition of the nonnegative integers (so that we have A0 U A1 U A2 U . = (0, 1,2,. . } and A, n A3 = 0 for i # j; some A3 s may be empty), then the collapsed collection {TO, ZJ, 7 2, . } also has Property B, where ? , is the set of all sums x2eA s, taken over all possible choices of si E S,. Prove that any collection {TO, T1, 7 2, , } that satisfies Property B may be obtained by collapsing some collection {SO, S1 , S2, . . } that corresponds to a mixed-radix number system. 30. [A4391 (N. G. de Bruijn.) The radix-(-2) number system shows us that every integer (positive, negative, or zero) has a unique representation of the form (-2)el + (--2)Q + . . + (--2)Q, el > e2 > f.. > et 2 0, t 2 0. The purpose of this exercise is to explore generalizations of this phenomenon. a) Let bc, bl, b2, . . be a sequence of integers such that every integer n has a unique representation of the form n = beI + be, + . . + b,, , el > e2 > … > et 2 0, t > 0. (Such a sequence (b,) is called a binary basis. ) Show that there is an index j such that b, is odd, but bk is even for all Ic # j. b) Prove that a binary basis (bn) can always be rearranged into the form do, 2di, 4dz, . . . = (2nd,), where each dk is odd. c) If each of do, di, ds, . in (b) is fl, prove that (b,) is a binary basis if and only if there are infinitely many +1 s and infinitely many -1 s. d) Prove that 7, -13. 2, 7 3 2 , -13. 23, . . , 7. 22k, -13. 22k+1, . is a binary basis, and find the representation of n = 1.

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