192 ARITHMETIC 4.1 Representation of (Free web hosts) numbers in the
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.)