TEE UM1EPSIY'OF MJICHIGAN IDUJSTRY PROGRAM OF TEE COLLEGE OF ENGIMRING AN INVESTIGATION OF THE ALGEBRAIC PROPERTIES OF TH EIE RESIDE JMBER SYSTEM Donald P. Rozenbe.rg A diss-extation sasbmitted in par:tial Tfulfillment of the requirements for the degree of Doctor of Philosophy in the University of Michigan 1961 June, 1961 IP-520

ACKNOWLEDGMENT The author wishes to express his appreciation to the members of his committee for their assistance, criticisms, and suggestions during the course of the work. The research upon which this dissertation is based was supported by the United States Air Force under contract AF33(6.6)-7340. ii

TABLE OF CONTENTS Page ACKNOWLEDGMENT............................................. ii CHAPTER I INTRODUCTION.......................... o............. 1 1.1 Introduction to the Problem................. 1 1.2 The Residue Number System..................... 3 II THE R-SPACE........................................... 8 2.1 Basic Properties of the R-Space................ 8 2.2 Linear Transformations and Matrix Multiplication in the R-Space.................. 14 III CARRY FUNCTIONS IN RESIDUE NUMBER SYSTEM AND RELATED NUMBER SYSTEMS.........................,. 22 3.1 The Carry Algorithm.......................... 22 3.2 The Borrow Algorithm and Complementation....... 26 3.3 Change of Basis............................... 30 3.4 Multiplication............................... 32 IV THE MIXED BASE NUMBER SYSTEM...................... 43 4.1 Mixed Base Number System..................... 43 4.2 Overflow....e..............o................. 47 4.3 Division in the Mixed Base System....... o o o o 50 4.4 Digit Fill-In...,..O........................... 52 V OTHER NUMBER SYSTEMS RELATED TO THE RESIDUE NUMBER SYSTEM..........o....... o................ o 54 5.1 Partitioning Properties..................... 54 5.2 Number Systems Allowing Sign Detection with Fewer Than n-Carries...................o 62 VI SUMMARY AND CONCLUSIONS.....,,,,o...o........oo...o 65 BIBLIOGRAPHY............................................o e o 67 iii

CHAPTER I INTRODUCTION 1,1 Introduction to the Problem The first large scale digital computer designed to incorporate the binary number system was the EDVAC developed at the Moore School of Electrical Engineering, University of Pennsylvaniao The addition time of the EDVAC was one millisecond. Since 1949 when the design was described, the trend in digital computer technology has been toward higher speed, in particular drastically reduced addition timeo One of the fastest digital computers under development is the IBM STRETCH which is to effect addition in 0.6 microseconds. This great arithmetic speed is obtained partly by using very fast components and partly by the novelties in the logical structure of the system. As yet new and unconventional number systems have not been employed to increase the speed of arithmetic operations in a large scale digital computer. When two numbers represented in conventional number systems are added in a digital computer, carry propagation normally consumes the major portion of the computation time. The residue number systeml2 based on the algebra of residue classes, allows addition to be performed without carry computation. Furthermore, multiplication is as fast as addition. Cheney3 has designed a digital correlator based on the residue number 1 H. Lo Garner^ "The Residue Number System." IRE Trans. Electronic Computers, Vol. EC-8, June 1959, pp.140-7. 2 Ao Svoboda, "Rational Number Systems of Residual Classes," Stroje Na Zpracovani Informaci, Sbornik V; 1957. 3 Po W. Cheney, "A Digital Correlator Based on the Residue Number System." Technical Document LMSD-702670 Lockheed Aircraft Corporation, 1960o -1

-2system and concluded that a correlator of similar accuracy based on the binary system would have been 10 times slower if the organization were parallel and 100 times slower if serial. The residue number system poses rather formidable problems which have prevented its adoption in the design of general purpose digital computers. These problems include (1) sign determination, (2) the prevention of additive and multiplicative overflow, (3) magnitude comparison, and (4) division. In this thesis the algebraic properties of the residue number system and related number systems are investigated and employed to provide insight into the above problems. The remainder of this chapter will be devoted to the presentation of the residue number system as the direct sum of rings of integers. The above mentioned problems will be discussed. Chapter II will contain the algebraic theory of the R-space, a pseudo-vector space of the residue representations. The R-space will provide the formulation of the residue number system and the associated number systems. Carry functions which provide a basis for the addition and multiplication of the residue and related number systems are discussed in Chapter III. The mixed base number system related to the residue number system is discussed in Chapter IV. It is shown that the mixed base number system possesses several crucial properties. These properties allow the solution of the problems of the residue number system. Chapter V shows that there is no number system related to the residue number system which shares the special properties of the mixed base system.

-3This dissertation will investigate the problem of the residue number system and give solutions to the problems of (1) sign detection, (2) magnitude comparison, (3) overflow, and (4) division. These results will be obtained by considering the residue number system to be a pseudovector space. 1.2 The Residue Number System As a preliminary step in the introduction of the residue number system the ring IM of integers modulo M will be discussedo4 The elements of the ring are the integers 0O 1, 2 o oo M-o Ring addition and ring multiplication of two elements of IM are performed by reducing the conventional sum and product modulo Mo That is, the sum or product is divided by M and the remainder is retained as the result. Thus, for example, the ring 16 consists of the integers 0, 1, 2, 35 4, 5. Dividing the ordinary sum of 4 and 5 by 6, one obtains 3 for the remainder. Therefore, in 16, 4 + 5 3, Similarly 2 + 4 - 0 2 ~ 2 = 4 and 4 o 2 = 2. The proof that IM is actually a ring follows from the fact that in the division of an integer by M, the remainder is unique The complete proof may be found in the literature 5 The order of IM is Mo No Ho McCoy, "Rings and Ideals." The Mathematical Association of America, Buffalo, New York, p 1o A Ring is a set of elements a, b, c,..r, a unique defined addition a + b, and a uniquely defined product ab.:satisfrying the following five properties: P1 a + (b+c) (a+b) + c; P2 a + b= b + a; P the equation a + x = b has a solution x in R; P4 a(bc) - (ab)c\ P5 a(b+c) ab + ac, (b+c)a = ba + cao 5 Ibido, po 64~

-4Consider the ring I of integers and the ring IM of integers modulo M. An arbitrary element m of I determines a unique element m of IM; namely, the remainder upon division by Mo If one denotes the correspondence of m to m by m -- m, it is clear that if ml- ml9 m2 -- m2, then mi + m2 — m1+ m2 = ml + m2 and mlm2 -mlm2 = mlm2 o Therefore, the correspondence between I and IM is a homomorphismo Fixed point digital computers do not operate upon the ring I of integers but rather on the ring IMo If one thinks of the radix point as being on the right, then the largest number which can be represented is M-1 That the homomorphism is a many-to-one mapping is painfully apparent when overflow occurs and the most significant digit(s) are losto Fortunately, one can detect such an overflow by sensing the carry from the most significant digit position. The ring IM possesses an additive inverse of every element. If m is an element of IM, M - m is the additive inverse. Thus we map the integers less than M/2 onto the elements of IM less than M/2 and the negatives greater than -M/2 onto the remaining elements of IM. Thus the sign is readily determined and thereby magnitude comparisons can be performed. Since one can perform overflow detection, sign determination, and magnitude comparisons, division is possible. Let S1 and S2 be two rings and consider the ordered pairs of symbols (sl, s2) where sl E S1 and s2 E S2o If one defines addition and multiplication to be (sl, s2) + (tl, t2) = (s + tl S2 + t2) and (Sel s2) (tl, t2) = (sltL s2t2)

this set of rdered pairs becomes the ring S termed the direct sum of S1 and S2 and denoted SL + S2 In the above definition the operations si + ti and siti are the ring operations of Si. An especially important theorem is the following: Theorem 1. If a ring S has positive characteristic n = n1 - n2 where nI and n2 are greater than 1 and relatively prime, then S is isomorphic (') to S + S2 where Si is a ring 6 of characteristic ni (i = 1, 2)6 This theorem states, for instance, that 16 is isomorphic to the direct sum I2 + I3 with the following mapping 0 - (0 0) 3 -— (1, 0) 1 -(1- 1) 4-(0o, 1) 2- (0 2) 5 - (1 2) Theorem 1 may be extended as follows: Theorem 2. If the ring,1 has positive characteristic M - mlm2.p * mn where the mi are integers greater than 1 and pairwise relatively prime, then IM [ + Im2 + +; 3 Proof: If n x 2, the result follows from Theorem 1 Assume the resuLt for n = K and consider Nji mm M2 444 mm 12 K K+l B. L. van der Waerden, op. cit. p. ll6. Theorem 1 is Theorem 28 in MC.oy

-6M may be written M = mlm2 *. m'K where m' = mKmK+l Thus we have IM Iml + Im2 + *** m K but by Theorem 1, m K mK mK+l Therefore, IM = Iml Inm2 + + ImK+l Thereby, the conclusion is proved. The direct sum of Theorem 2 defines the residue number system. Elements of IM are mapped unto n-tuples of the direct sum (elements of the residue number system) according to the following scheme x -> (x mod m, x mod m,.., mod m ).7 (1-1) If x<-> (x1, X2,..., xn) then x + y < > [(xl + Y1) mod ml,.., (xn + y.) mod mn] and x ~ y <-> [(x1 Y1) mod,..., (xn Yn) mod mn] It is clear from both the example following Theorem 1 and Expression (1-1) that the components of the residue representations have no positional significance. Therefore, there is no direct means of 7 x mod mi is defined to be the residue of xi modulo mi

-7comparing two elements to determine which is the image of the larger integer. Thus one cannot compare any element with the image of M/2 (or M+1 if M is odd) to learn sign. A result is that Euclidean 2 division is not possible in the residue number system. Consider the following examples of additions in the ring I2 with m = 2 m2 = 3, m 5 and m4 = 7 (a) 209 — (1,2,4,6) (b) 209 — (1,2,4,6) 1 — (1,1,1,1) 105 —- (1,0,0,0,) 210 -- (0,0,0,0) 104 —- (0,2,4,6) (c) 105- (1,0,0,0) (d) 23 -- (1,2,3,1) 120 - (0,0,0,1) 162 — (1,2,2,6) 015 —- (1,0,0,1) 185 — (0,1,0,0) In example (a), the sum produces an overflow and each component ring indicates an overflow. The sum in (b) overflows but only one component overflows. In (c), overflow occurs but the component subrings do not indicate overflow. No overflow accompanies the addition in (d); however, overflow is present in each component. These examples indicate that overflow in the component subrings is unrelated to overflow of IM. Similar statements may be made concerning multiplicative overflow.

CHAPTER II THE R-SPACE 2.1 Basic Properties of the R-Space Let any two residue representations be x = (xl1 X2,.e xn) y = (Yl Y2 *'~~ Yn ) then x + y _ [x1 + Yl (ml),.ooo Xn + Yn (mn)] where the mj are pairwise relatively prime. The component xi is said to be associated with the base modulus mi. The residue number system representations form an additive Abelian group which is denoted by Rn. For S, a ring with identity, we select the integers and define multiplication by a scalar to be x axaxl(ml),..., axn(mn)] With these definitions it is seen that a.) ax e Rn, b.) a(x + y) = ax + ay for a(x + y) {a[(x1 + Y1)(nl)] (ml)9 ooo a[(xn + Yn)(mn)] (mn)} = {[(axl)(ml) + (ayl)(ml)] (ml),.009 [(axn)(mn) + (ayn)(mn)] (mn)} = ax + ay, c.) (a+b)x = ax + bx -8

since (a + b)x a [(a + b)xl (ml),..., (a + b)xn (mn)] {['axl(ml) + bxl(ml)] (m1' ),... ['axn(m ) + bxn(mn)] (mn)} d.) (ab)x = a(bx) for (ab)x = [abxl(ml),.., abxn(in)] = a[bxl(ml),.., bxn(mn)l = a(bx), and e,) All elements of Rn are uniquely expressible as linear forms a, l +,.o + a e by means of n fixed basis elements with 0 < ai < mi where ej has one for its j-th component and zero for the other componentsThe five properties which must be satisfied far Rn to be a n-dimensional vector space are a, b, c, d above, and: e' ) All elements of Rn are uniquely expressible as linear forms alu1 +., + anun by means of n fixed "basis elements" ul,,., un and aie S.8 This property is not satisfied. and thus Rn is not a true vector space. The pseudo-vector space Rn will be called the R-space and all vector space terms which follow will have an interpretation in the R-space which is analogous to the vector space definitions. Consider the set of'ectors < aG1.... an> with each ai having n components. Form a square array of the components by placing the components of ai in the i-th row. If this array can be made triangular (specifically a lower traingular array) by reordering rows and columns, 8 B. L van d.er Waerd.en, "Modern Algebra." Frederick Ungar Publishing Company, New York, Vol. 1, p. 42.

-10the set < l, ~c., COn > is termed semi-triangular and the reordered set termed triangular. Theorem 3. If the set {alc,.. % } is triangular and the elements on the principal diagonal are relatively prime to the associated base moduliU, then any linear form alCl + a2C2 + ooo + anon where the ai are integers can be uniquely expressed as n i i ai where O0 ci s mi i —~l Proof:. knncn - kan mod mn where kij is the j-th component of a(i9 Thus cn a an mod mn since mn is relatively prime to knn, and 0 < cn < mn is uniquely determined. Assume the conclusion true for cj for j = m, m + 1, oo, n and also that these cj have been determined and consider the congruence km-l, m-1 Cm-1 + km, m-1 Cm + c ~m + kn m-1 Cn a km-1, m-1 am-l + km, m-l am + o + kn, m-1 an mod mm-lo By adding to both sides of the above congruence the additive inverse of (km,m-1 Cm + * + kn m-l Cn) mod mm-l this congruence takes on the form kml, m-1 Cm1 a A mod mm-l. Since (km-1, m-1, am.l) =. 1I cm_1 is uniquely determined mod k1-l and 0 < cm-l < mm_.10 9a m b mod m (a is congruent to be modulo m) if and only if m[a-b (m divides a-b or a a b + km). 10 The greatest common divisor (d) of a and b is written (a, b) ~ d.

-11Theorem 3 is of key importance for it allows us to abandon the ring S and to concentrate our attentions on linear forms of triangular sets of vectors; namely, i ci oi where < a1,. an > is triangular and 0 < ci < mi. Except where indicated the following discussion will be limited to sets of triangular vectors and linear combinations with restricted scalars. Definition: The vectors 1 ~.Y cn of a triangular array are linearly independent if and only if ClQl +... + cnn = where 0 < cj < mj implies cl = c2 =.. = cn = 0. Otherwise the vectors al,..., a0 are termed linearly dependent. Theorem 4. The triangular set of vectors < 1a Q~ 2, ~~ an > is linearly independent if and only if each element on the principal diagonal is relatively prime to the associated base modulus. Proof: Consider the equation Cl1a + + c.. + C = 0 (2-1) Equation (2-1) is equivalent to the following simultaneous linear congruences knncn ~ mod mn n kiii + Z kji cj 0 mod mi for i = n-l, ooo 1. j=i+l For knncn - 0 mod mn to yield the unique solution cn = 0 it is sufficient that (knn,.n-) = l. As-sume (XX, m,) = 1 and ci = 0 for i = 2,6+1, 2 + 2,..., n.. The L-th congruence becomes kXX c - 0 mod mX and cQ = 0 is the unique solution. This proves the sufficiency of the hypothesis.

-12Assume r to be the least index for which (kii9 mi) # 1. Let ci = O for i > r. The above congruences become krr Cr 0 mod mr (2-2) r kii ci + j ki C= 0 mod mi for i r-l, r-2,.., 1. j=~+l ji j Congruence (2-2) may be solved with cr 4 0. Since (kii, mi) = 1 for i = r-l, v-2,.e e 1, the remaining congruences assume the form kii ci m Ai mod mi The condition (kii, mi) = 1 for i < r guarantees the existence of a solution for each congruence. This completes the proof. Definition: Aset of vectors {czl, 02'..o an} is said to span Rn if and only if there exists a set of coefficients ci in the ranges 0 < Ci < mi satisfying the equation n z ci ai = r for all- rein. Theorem 5. For a triangular set — of vectors < xl,. o on > to span Rn it is necessary and sufficient that each element on the principal diagonal be relatively prime to the associated base modulus. Proof: The existence of solutions ci to the following congruences will be shown knn. n an mod mn (2-3) n and kiici + Z kji cj m ai mod mi for all ai in the range jis al+

-130 < ai < mio The necessary and sufficient condition for the existence of a solution to (2-3) is (knn, mn)ian. Since an (an integer) will range 0 < an < mn, it is necessary and sufficient for (knn, mn) = 1. Assume that solutions ci exist for i > X. These solutions are substituted into the ~-th congruence yielding an expression of the form kit cX + D = a mod mX or keg cX al + E mod mi Again (aX + E) mod mX will include all integers in the range 0 through mX - 1. Thus to guarantee solution it is necessary and sufficient that (kid, mi) = 1. The proof is complete. Corollary: The triangular set of vectors < 1a,.o., an > is a spanning set of Rn if and only if it is an independent set. Definition: A basis of an R-space is a linearly independent set of vectors which generate the R-space. Theorem 5 may be rephrased in more conventional terms as follows: Theorem 6. For a triangular set of vectors < a1,.oo a n > to be a basis of Rn it is necessary and sufficient that each element on the principal diagonal of the array be relatively prime to the associated modulus. Theorem 7. If l. O, n forms a basis for Rn then every vector ( e Rn has a unique expression = x1 + x2 0C2 +. + xn On, 0 <_ xi < mi. Proof: It will be shown that the congruences which must be satisfied for the above expression to hold will provide xj which are unique modulo mj. Let p = (b1, b2,..., bn).

-l4The first congruence is xn kn n bn mod mn. Since kn and mn are relatively prime, xn is uniquely specified modulo mn. Assume Xm+l Xm+2'... xn have been uniquely determined. Then to be considered is the congruence km,m Xm + km+l,m Xm+ + + kn,m Xn bm mod mmo Add to each side the additive inverse modulo mm of (km+lm x*+ + + kn,m Xn) to obtain k nm x - B mod mn Since (kmm, mm) = 1, xm is uniquely determined modulo mm. Theorem 7 states that every residue number has unique coordinates relative to a given basis. Thus every basis serves to define a number system related to the residue number system. The chapters which follow will be devoted to the arithmetic properties of this class of number systems. Algorithms which permit addition, complementation, and multiplication will be developed. The relation of these number systems to the problems of the residue number system will be investigated. It has been proven by Garner and Arnold that only triangular arrays of vectors will span Rn. 2.2 Linear Transformations and Matrix Multiplication in the R-Space Definition: A linear transformation G: Rn — Sm of an R-space Rn into an R-space Sm is a transformation which satisfies (5 + n) G G + n G (c ) G = c( G).

-15Theorem 8. If al,..., an is any basis of Rn and Y1,..., 7 are any vectors in Sm, then there is one and only one linear transformation G: Rn - Sm with OUG = 71 OnG = 7n ~ This transformation is defined by (xll +... + Xnin)G = x171 + x272 +... + Xnyn Proof: Let A = {a1,..., Qc} be a basis for Rn and B = {pl,,..., 5 be a basis for Sm, then UG = Y U2G = 72 OnG = 7n, where 7i = aill +... + almj m for i 1,..., n. If _ = (xl..., xn)A E Rn, then = Xla01 +... + nan from which results GG = xl7l + X272 +... + xn7n By substituting for 7i one obtains =G = x1 (all11 +... + alm)m) + X2 (a21l1 + *' + a2mEm) + Xn (anlBl +... + anmBm) and by rearranging terms,

-16G= (xa11 + x2a21 +... + Xnnl)1 + (xla12 + x2a22 +.. + Xnan2)P2 + (Xlalm + X2a2m +.' + xnanm)fm By Theorem 3 the image SG can be uniquely expressed m Z diPi where 0 < di < mi i =1 and, therefore, SG c Sm and the transformation G is a transformation Rn - Sm. Let = (Yl, *... Yn)A then = YlCl +.. + YnQn Thus IG = Y171 +... + YnYn ~ + q = (X1 + yl)CZl + (xn + Yn)On (5 + q)G= (x1 + yl)Yl +... + (Xn + yn)Yn = xl71 +.. + xnYn + Yll7 +.. + YnYn = GG + TG, and c = CX lC0 +... + CX n (c5)G = cxlY1 +.. + CXn7n = c(iG). Thus the transformation is linear. It is to be noted that it is not necessary that the set {71, *.., 7Y be a triangular set. Since every vector in Rn can be expressed uniquely as XlC1Q+ +... + nn for 0 < xi < mi, the transformation is single valued

-17and therefore, no other transformation from Rn into Sm yields OiG. The proof is complete. Let A ~ {<X1,'.., be a basis for Rn and B j {el,..., m} be a basis for Sm. We then have the equations UlG = all" +... + almfm O2G = a21i +... + a2mm nG = anll +... + anm^m The form of these equations suggests writing the rectangular matrix all a12... alm a21 *.. a2m anl.. am If Rn, Sn, and Tn are three n dimensional R-spaces, G is a transformation of Rn into Sn, and H is a linear transformation of n into Tn. then the product of the transformations is defined ci(GH): (G)H Theorem 9. If the product of two transformations is defined, then it is a linear transformation. Proof: Let G and H be linear transformations whose product exists, let c be a scalar, and let U1, ~2 be vectors in the domain of G. Then we have (cl. + c) (GH) = [ (ac + c )G]H - [(alG) + (a2G)]H

-18(ao1G)H + (a2G)H C= (GH) + o2(GH) and (cal)(GH) = [(cal)G]H = [c(a1G)]H = c [(CeG) ]H c[(alG)]H = c[al(GH)] Multiplication of linear transformations has been defined and will now be used as a guide to defining multiplication of matrices. To this end let Rn, Sn, and Tn be three R-spaces of dimension n with respective bases A - {01,.., ] B, B. {, Bn}, and C = {y1,., 7n} Relative to these bases G has the matrix a and H has the matrix3. Consider the matrix P = I||pijl of the product transformation J = GH relative to the bases for Rn and Sn. A development of the rows of P will be given in terms of aij and bij. ollG = allp +... + alnfn OQ2G = a211P +... + a2nPn OnG = anl +.. + annkn and P1H = bllY1 + *.. + blnYn 2H = b2171 +... + b2nYn DnH = bnlY1 + *.. + bnnYn ~

-19Thus (aC1G)H= all(PlH) + a12(2H)+ +.. aln(nH) all(bll11 + b1272 + *. + bln7n) + a12(b2171 + b2272 +... + b2nn) + a e a aln(bnlyl + bn2Y2 +... + bnnyn) Therefore n n n (COGH) = ( Z alkbkl, Z alkbk2,..., l alkbkn) k=l k=l k=l Similarly n n n (c2GH) = ( a2k a2kbk2... a2kbk2. k k=- k=1 k=l Thus n n n (OnGH) = ( Z ankbkl, Z ankbk2,., Z ankbkn). k=l k=l k=l The above equations are preliminary results in the determination of the rows of P. Each of the linear forms indicated above must be expressed as linear forms with restricted coefficients. The linear form with restricted coefficients corresponding to (CiGH) constitutes the i-th row of P. The justification for restricting the discussion to the multiplication of matrices which correspond to linear transformations from n dimensional R spaces into n dimensional R spaces is the projected application of such multiplication. The principal application will be in the change of basis operation (conversion from one number system into another). In this application the linear transformation is an automorphism from Rn onto Rn.

-20In the interest of completeness, the result for the most general case will be given. Let RV, SW, and TZ be three R-spaces with respective bases a = {1''''. v}} 0 = {P1' feel Pw}j, and C = {1i,.., 7z}. The linear transformations G and H are defined by w aiG = Z aiVyv (i = 1, 2,... v), v=l and z PiH = Z biY9I (i = 1, 2,.., w) Therefore, w w w z (CiGH) = ( aiv~v)H aiv(PvH)= aiv Z bvY7 v= =l V=l Jl=1 z w W W W = Z vZ aivbvyk =, ( Z aikbkl Z aikbk2,..., aikbkz) p=l v=l k=l k=l k=l The above linear form when expressed with restricted coefficients constitutes the i-th row of the product matrix. If A = Hlaijll, B |bij||, and C = I|cijll are n x n matrices relative to the natural basis, the product (AB)C is developed in the following manner: AB = E = I eijj| relative to the natural basis and the i-th row of E is obtained from the linear form n n ( aikbkl, Z aikbk2, k., aikbkkn) k=l k=l k=l

-21Since this linear form is to be reduced relative to the natural basis, the i-th row of E is n n n [( Z aikbkl)(ml), ( Z aikbk2m2 (m2),, ( - aikbkn)(mn)] k=l k=l k=l The product (AB)C = F = I| fij l is similarly developed and the i-th row of F is n n [( e eikckl)(m-l), *., ( ~ eikckn)(mn)] k=l k=l n n -= { [(r- airbbk)(mk)] ckl} (ml), *. k=1 r=l n n {Z [( Z airbrk)(mk)] ckn} (mn).(2-4) k=l r-l Consideration of the product BC gives rise to the following linear form with restricted coefficients. n n [( kl bikckl)(ml)l *' (kl bikckn)(mn) ] Also A(BC) = D = I dijl where the i-th row of D is n n n n [(l air Zk brkCkl)(ml),.., ( Z air k brkckn)(mn)]. (2-5) r=l k=l r=l k=l As shown by Equation (2-4) and (2-5), multiplication of matrices associated with the residue system is not associative,for the ranges of the components in (2-4) and (2-5) differ.

CHAPTER III CARRY FUNCTIONS IN RESIDUE NUMBER SYSTEM AND RELATED NUMBER SYSTEMS 3.1 The Carry Algorithm In the second chapter many of the results depended upon the existence of a linear form with restricted coefficients which was equivalent to a given linear expression. This chapter will discuss an algorithm (the Carry Algorithm) for finding the linear form with restricted coefficients when any linear combination of the basis vectors {ol,..., aj is given. The algorithm involves the notion of carries from some components of the representations into other components of the representation. If the linear form to be reduced is alal + a2a2 +..e + anan, one proceeds by expressing anQn as blOl + b2C2 +... + bnn where 0 < bi < mi and making the substitution to obtain (al + bl)1 +..* + bnan. The process is then repeated focusing attention on (bnl + an-l)n-l and continued until one has the desired result. Dividing aj by mj, one obtains aj = mjq + r, 0 < r < mi. Any multiple of mjaj will yield a vector in the subspace (xl, x2,..., xj_l, 0..., 0). Since the set of vectors {Ci} is a basis, the set {,'..., acj} is a basis of the mentioned subspace by Theorem 4. Thus the term mj will not affect the multiplier of aj in the reduced expression; that coefficient must be r. The product mjaj can be expressed as a linear combination of 1l through aj-1 and qmjaj is merely q times each term of that combination. The linear combination for (q m.)aj is added to the original linear combination and ajaj is replaced by -22

-23raj. Thus one applies the above procedure to first an, then to the new coefficient of an-l, and so on until the desired result if obtained. The Carry Algorithm may be stated as follows: 1. Express mjaj as a linear combination of a,1..., aj-l denoted bjlc+ + bj22 + + bjjlj for j = 2,3, Beginning with j = n and an an 2. Divide a! by mj and obtain a =q.m. + r. with 0 < r. < m.. J 3 J 3 3 3 3. Replace a'a with r a and j i j3 a! with (a + qib ) for i = 1, 2,..., j-1. i I I ji 4. Repeat steps 2 and 3 substituting j-1 for j. Stop after executing steps 2 and 3 with j = 1. Theorem 10. The linear form produced by the application of the Carry Algorithm expresses the same residue number as the original linear combination. Proof: The proof will be the demonstration that the coefficients of the resulting linear form satisfy the congruence indicated in the proof of Theorem 3. Consider cn = an mod mn with 0 _ cn < mn. By the uniqueness of division rn is the residue of an modulo mn and rn C= n. Assume that rj = cj for j = m +l,..., n. The congruence which then must be satisfied is km-l, m-1 r in-1 + km, ml'C% + - -t + kn, m-1 On k1^m-l m-l am-1 + kin, m-1 am + *.. + kn, m-l am-l mod mnl.

-24The quantity a' which enters the davision in step 2 of the Carry Algorithm is a' = aj q blj + + - + + bj+l, j thus an = an a' =a + q b n-1 n-1 -+bn, n-, an-2 = an-2 + nbn, n-2 + n-1 bn-l, n-2 am-l = am-l + nbn, m-1 +..' + qbm m-1 In expressing pj = bjlal + bj2a2 + ** + bjj lljl - one solved the congruences kjj- bjj_ -= mjkjl mod mj1i j-2j-2 jj-2 + k jl j-2 kjj2 mod mj km-l,m-1 b jml + km-2,m-1 bjm-2 +.ee + kji-,m1 bjn-1 mj kj,m-l mod mm-1 kllbjl + k21bj2 +' + kj_l,1 bjjl mj kjl mod mi Using the induction assumption, relation (3-1) can be written km-,m-lcm-l + km,m_lrm +. + kn,m-lrn km-l,m-laml + km,mlam + e. + kn,mlan mod mm-_ which can be manipulated to yield kmlm-lm-l + km,m-rm + *e + knl,mlrn1km-l,m-lam-l + m-am +''' + knm- (an - rn) mod mn (3-2)

-25Since an = an an - rn = qnmn, (3-2) becomes km-lm-lCm- + km,m-lrm + *.. + kn-l,m-lrn-l m-l m-l (am-l + qnbn,m-l) + kmm-l (am + nbnm) +.. + kn-l,m-1 (an-1 + qnbn,n-l) mod mm_1 (3-3) upon the substitution qn (km-l,m-lbn,m-l + kmm-lbnm + + kn,m-lbn,n-1) nmnkn,m-l(mod mm_-l) Once again we transpose (add the inverse) knl,m-lrn-1 and recognize that an1 + qnbnnl - rnl = a'n-l - rn-l = n-lmn-l Making the following substitution: qn-1 (km-l,m-lbn-l,m-1 + km,m-lbn-l,m + * + kn-l,m-lbn-l,n-2 qn-lmn-lkn-l,m-l mod mml we obtain km-l.m-lCm-l + km,m-lrm +.. + kn-2,m-lrn-2 k-lm-l (am-l + -nbn,m-l + qn-1 bn-l,m-l) + km,m- (am + qnbn,m + qnlbn-l,m) + ** + kn-2,m-l (an-2 + qnbn,n-2 + qn-lbn-l,n-2) mod mm_-l Again we identify the last quantity in parenthesis as atn2, transpose and substitute. By repeating these manipulations, one finally obtains km-l,m-lcm-l km-l,m-l (am-l + qnbn,m-l + + qmbm,m-l) mod mm_or Cm-1 - aTm-l mod mml which yields the desired result Cm1l = rm.l.

-26By showing that rm = Cm, we have shown that the linear form produced by the Carry Algorithm is identical to the linear form of the conclusion of Theorem 3. Therefore the proof is completed. Without the Carry Algorithm, one can perform operations such as addition, multiplication, and matrix multiplication by resorting to the defined operations of addition and scalar multiplication of residue numbers. The only alternative is to solve a set of simultaneous linear congruences every time one wishes to express a linear form with restricted coefficients. With the Carry Algorithm, it is necessary to solve only n sets of simultaneous linear congruences, and further those sets of congruences may be solved immediately upon the selection of the base moduli and the basis vectors. Thereafter, any linear form may be reduced to one with restricted coefficients by the application of steps 2, 3, and 4 of the Carry Algorithm. It is thus possible to select a set of basis vectors, perform step 1 of the reduction algorithm (i.e., determine the carry functions), and thereafter perform addition of two vectors by addition of the components followed by the application of the Carry Algorithm. Scalar multiplication is effected by multiplying each component of the vector by the scalar and then applying the Carry Algorithm. The Carry Algorithm will prove significant in the multiplication of representations for it will provide a means of combining partial products. 3.2 The Borrow Algorithm and Complementation The question arises: Given two representation X and Y of positive integers, how does one obtain the remainder X - Y? This question will now be considered in some detail.

-27Let X be represented by (x1, x2,..o, xn)O and Y by (Y1' Y2 **e, Yn)c' Initially one forms (x1 - y1, x2 - Y2,., X - Yn). This last expression denotes (x1 - Yl)gl + (x2 - Y2)a2 +.. + (xn - yn)n Consider the j-th component of an expression to be negative. Since mj bj = bjl1l + bj2Ca +... + bj,j_lj_-l, one may add to the above expression zero in the form dj [mjOj - (bjlOl + bj2C0 + bj,j-loj-l)] = 0O where dj is the smallest multiple of mj which is larger than the magnitude of the j-th component. This addition yields (x1 - Yl - dnbnl 2 Y2 - dnbn2,.., _1 - Yn-2 - dnbn,n-l, Xn - Yn + dnmn) for j = n, (X1 - Yl - dnbnl - dn-lbn-l,, x2 - Y2 - dnbn2 - dn-l bn-l,2 ***, Xn-n-l -dnbn,n-1 + dn-lm n-l Xn - Yn + dnmn) for j = n-l, and finally (x1 - Y1 dnbnl - dn-lbn-l,1 - e'* - d2b21 + dlmly X2 - Y2 - dnbn2 - dn-lbn-1,2 -... - d3b32 + d2m2,.., Xn-l - Yn-l - dnbn,n-l + n-lmn-l, Xn - Yn + dnmn) for J = 1. This final expression will be a linear form with restricted coefficients which is the representation of X - Y if X > Y. If X < Y the above procedure yields a representation of -(Y - X). Thus complementation quite naturally enters the picture. By dividing the range of integers which can be represented by residue numbers into those integers less than M/2 and those integers larger than M/2, one can designate the first group of vectors to be representations of positive integers and the second group, codings for the

-28complements of the elements of the first group. If M is even, M/2 is self complement. To find'the complement of a given representation Z, one generates the remainder (0 - Z) as indicated above. The procedure for performing subtraction and finding complements indicated above suggests the statement of a Borrow Algorithm as follows: 1. Express majj as a linear combination of aG,..., aj-l denoted bjlal + bj2a2 + l.. + bj,j-laj-_ for j = 2, 5,.., r Beginning with j = n and a'j = an. 2. Perform steps 3 and 4 if a'j < 0, otherwise skip to step 5. 3. Determine dj such that dj is the smallest multiple of mj which is larger than l|aj. 4. Add to the linear form the expression (-djbjl, - djbj2,..., - djbjjl + djmj, 0,..., 0). 5. Repeat steps 2, 3, and 4 substituting j-1 for j. Stop after executing steps 2, 3, and 4 for j = 1. Example: With the basis < (1,0,0,0), (1,2,0,0), (1,1,2,0), (1,1,1,1) > where the moduli are ml = 2, m2 = 3, m3 = 5 and m4 = 7, the carry functions are 352 = 51, 5a 3= O2, and 7a4 = a3. An example of subtraction using the Borrow Algorithm directly will be given as well as subtraction by using the complement of the substrahend.

-29Subtraction using the borrow algorithm: z 3 <7 7 ( 1, 2, 2, 1) - 190 - ( 0, 2, 4, 6) * — -104 ( 1, 0,-2,-5) + ( 0, 0,-1, 7) ( 1, 0,-3, 2) + ( 0,-1, 5, 0) ( 1,-1, 2, 2) + (-1, 3, 0, 0) ( 0, 2, 2, 2) - 86 Complement of (0,2,4,6): ( 0,-2,-4,-6) + ( O, 0,-1, 7) ( 0,-2,-5, 1) + ( 0,-1, 5, 0) ( o,-3, 0, 1) + (-1,-3, 0, 0) (-1, 0, 0, 1) +( 2, 0, 0, 0) ( 1, 0, 0, 1) Subtraction utilizing the complement: (1, 2, 2, 1) -- 190 + ( 1, 0, 0, 1) -I 104 ( 0, 2, 2, 2) -- - 86

-303.3 Change of Basis One quite important use of the carry algorithm and matrix multiplication is the change of basis operation. Quite often it is desirable to convert from one number system to another, i.e., express a vector in coordinates relative to a different set of basis vectors. One might wish to make the conversion because different number systems are more advantageous for particular operations than others. More will be said concerning this later. Let a vector X be represented by (xl, x2,..., xn) relative to the basis < 1, 02,..., An >. It is desired to find coordinates (Y1p Y2, *... Yn), relative to the basis < 51' 52'..., >. Each vector C1 of the old basis can be expressed as a linear combination of the vectors of the new basis in the form li = cill + 22 + qi22 + * + inPn * (3-4) However, since both bases are triangular, qik = 0 for k > i. The vector X with coordinates (xl, x2,..., xn) relative to the basis < C 2l, o.., Cn > is XlCl1 + x2a2 +... + xnn Substituting from above, one obtains for X XlqllB'+ x2 [q21~l + q 2222] + xn 22nl + x [qn + + qnnPn] which can be written (Xlqll + x2q21 + *' + Xnqnl)pl + (x2q22 +... + Xnqn2)f2 +... + xnnnn

-31The carry algorithm is then applied to linear form (3-5) and the result is X = Y11 Y 2+ Y22 + Ynn ~ The Yi are the coordinates of X relative to the basis < 12 P2''*'a' n >' If the zero coefficients are retained in Expression (3-4), Expression (3-5) becomes (x1q11 + 2 +. + l) + (x12+ + x221 + n + X nl l + 2 + 222 4 2 +,.. + (xlqln + X2q2n + *. + Xnqnn)n This expression is an interpretation of (xlqll + X2q21 + *.* + Xnqnl), (xl-12 + X2q22 +.. + Xnqn2), (xlqln + o* + Xnqnn) which is the matrix product [x1, x2,..* xn] f11 2... qn hq21 422 *' n 2 n = [Y1' Y2 *, Yn Lnl qn2 -' 4innj denoted X Q = Y The above procedure constitutes an effective procedure for executing change of basis. The vectors Pi of the new basis can be written as linear combinations of the old vectors, n Pi = Z Pijaj (3-6) j=1 Thus for a change of basis from < t1o'oo~ e n > to < l,. oo, ~ n >, the appropriate matrix product is Y * P = X where P = I PiJ |.

-32Substituting Equation (3-6) into Equation (3-4) one obtains n n n'i m il jrl Pljaj + qi2 l P2jj + * + qin Z1 Pnj0j n n n e qilPlja j + E qi2P2jaj + *. + E qlnPnjaj j=l j1= j=l n n l Z jel qikPkj'j k=l j=l One may interchange summations to obtain n n Oai.= s E qikPkjuj j=l k=l n n n Z q ikPPkjal + qikPk20 +. + Z qjikPknon (3-7) k=l k=l k=l Equation (3-7) written in n-tuple, form with restricted coefficients is the i-th row of the matrix product QP. Since the oi constitute a basis, the reduced form of Equation (3-7) must be ai = ai. As a consequence, it is seen that Q ~ P I. (3-8) By advancing a dual argument, one deduces P ~ Q = I. (3-9) Equations (3-8) and (3-9) can be used as a check on the determination of the P and Q matrices. These equations are necessary but not sufficient conditions for the accuracy of P and Q. 3.4 Multiplication To multiply two elements of a number system related to the residue number system, one forms partial products, one for each component of

-35the multiplier, and adds them together producing a linear combination of the basis vectors which is then reduced by means of the Carry Algorithm. The algorithm for determining the form of the partial products will be called the Multiplication Algorithm. The Multiplication Algorithm may be stated as follows: Consider the most general multiplicand (Y1l y2, 0oo yn) and multiplier (xl, x2,..., xn). 1. Write the multiplicand (Y1, Y2~ *, Yn) as the vector sum Yl'l + Y20C2 +.o. + YnQO ~ Beginning with j = n 2. Write the partial multiplier ( 0,..o, 0a xj, 0,.o, O ) as the vector xjaj. 3. Multiply, component by component, xjaj ~ Yiai i = 0,.oon 4. Express the vector xjaj * Yii as the linear combination Zi 1 +... + Ziai, i = 0,.o., n. 5. Sum the linear forms produced in Step 4 to determine the j-th partial sum. 6. Reduce j by one and repeat Steps 2 through 5. Terminate the procedure after doing the above steps with j = 1. Example: Consider the multiplication (Yi) Y2, *"e, Y4)M~ (x1, x22 e, X4)M in the mixed base number system where ml = 2, m2 = 3, m = 5, m4 = 7. Here the basis is < (1,0,0,0), (1,2,0,0), (1,1,2,0), (1,1,1,1) >

-34The following steps are numbered to correspond to the statement of the Multiplication Algorithm. 1. (Y1, 0,0,0) + (y22y2, 0,0) + (yy3,,y3,o)+ (y4,y4,y4,y4) 2. (x4,x4,x4,x4) 3. (ylx4,0,0,0) (y2X4,2y2,x4,0o) (y3x4,y3x4,2y3x4,0) (y4X4 yX4,y4X 4 y4X4) 4. (ylx4,0,0,0) = (ylx4,0,0,o)M (y2x4,2y2x4,,0O) = (O,y2x4,0,O)M (y3x4,y3x4,2y3x4,0) = (0,0,Y3x4,0)M (y4x4,y4x4,y4x4,y4x4) = (O,0,0,Y4x4)M 5. (yl'y2Y35,y4)M (O,,O,x4)M = (x4y,yl2,x4y3,xyx4y4)M 2. (x3,x3,2x3,O) 3. (ylx3,O,,0) = A (y2x3 2y2x350, O) = B (Y3x3,Y3X3,2(2Y3X3), ) = C (y4x3,y4x3,2y4x3,O) = D 4. A = (yix3,OOO)M B = (0,y2x3,0,o)M C = (o,o,2y3x3,O)M + (O,x3y3,0,O)M since (0,0,2x3y3,O)M+ (0,x3Y3s0,0)M = (2x3Y3,2x3Y x33Y3,0) + (x3y3,2x3y3,0,0) = (y3x3,yx3,2(2y3x3) 0) D = (O,0,XY4,0)M.

-355. (yy2,lYy3,y4)M (Ox3,O)M = (YlY2X3 + y3x3,2x3y3 + x3y4,o)M 2. (x2,2x2,0,0) 3. (x2y10,0,0) = A' (x2Y2,4x2y2,0,0) = B' (x2y3,2x2y3,0,0) = C (x2y4, x2y4, 00) = D 4. A' = (YlX2,0,0,O)M B' = 2(0,x2y2,0,O)M + (x2Y2,ooo)M for (x2Y2,4x2Y2,0,0)M = (x2y2,2x2y2,0,O) + (0,2x2y2,0,0) = (x2y2,2x2y2,,0) + (x2y2,2x2y2,0,0) + (2y20,0,0,0) C' = (0,x2y3,00)M D' = (0,x2y4,0,O)M 5. (Y,1Y2,Y3,y4)M * (o,x2,o,o)M = (x2Y1 + x2Y2,2x2y2 + x2Y2 + x2y4,0,)M 2. (xl,0,0,O) (x1y2,0,0,0) (xlJy,0,0,0) (x1y4,0,0,0) 5. (YlY2,Y3,Y4)M * (xl,0,0,0)M = (X1Y1 + xlY2 + X1Y3 + x1Y4,0,0,0)M The results of the Multiplication Algorithm in this example are the following for rules for the formation of partial products:

-36(y1y2Y3Y4)M' (xl,0,0,O)M= (xlY1 + xly2 + x1y3 + xly4,0,0,O)M (YlY2,Y3,Y4)M' (0,X2,0,0)M= (X2Yl + x2Y2,2X2Y2 + X2Y3 + x2y4,0,0)M (YlY2,Y3,Y4)M (OO,x5,0)M= (3Ylx3Y2 + X3Y3,2x33 + x3Y4,)M (y1,y2 Y3,Y4)M' (0,,0, x4)M= (x4y x4Y2,x4y3,x4y4)M, To multiply two mixed base elements (YlY2,Y3,Y4)M and (Xlx2,x3,X 4)M one procedes as follows: 1. Form the above partial products. 2. Reduce each partial product by employing the Carry Algorithmo 5. Sum the partial products again employing the Carry Algorithm. As an example, consider the product (1,2,3,4)M ~ (0,2,4,6)M The partial products are (1,2,3,4)M * (0,0,0,6)M = (6,12,18,24) = (1,,1,1,)M Mod M (1,2,3,4)M * (0,0,4,0)M = (4,28,40,0) = (1,1,o,o)M Mod M (1,2,3,4)M (0,2,0,O)M = (6,22,0,0) = (1,1,0,O)M Mod M Therefore, (1,2,3,4)M - (0,2,4,6)M (0,0,1,5)MMod M (0,2,4,6)M — 104 and (1,2,3,45* — 200 104. 200 = 20800 - 10 Mod M (0,0,1,3)M -v 10 Let us look again at the question of associativity of matrix multiplication. Consider the three matrices A = |laijl| B - ||bij.|, and C = ||cijll. Let the basis of the vector spaces be U, < a, 2,.., 9n >; V, < 1s, 2, Is n >; W. < Y1 Y2, *9.. ~ n >; and Z, < 81, 62,..., 6n >o TA is a transformation from U —V, TB: V —W, and TC: W-~Z.

-57The i-th row of the product A * B is n n n (k al b akbk2 0 aikbk ) aikbk2 k k=l k=l k reduced relative to the basis < 7j1 o~~, 7n > Designating the reduced form obtained (ell, ei2, ooo9 ein)9 we obtain n em k aikbkn ein k -n Define r n C aikbkn k=l in L mn n kL aikbkn-l + fingn,n- 1 ei,n-l k a..b........+...j mn-1 n a f aikbkl + fingnl + fi,n-lgn-l +*~ + fi,2g21 eil = -. ml d where mj 7j gjll71 + gj272 +.' + gjj-l7j-1l r a a - denotes the integr al part of the division a o I b 17 ~

-38The i-th row of the product (A. B)C is nn n (Z eikCkll, eikCk2,..., Z eikckn) k=l k=l k=1 reduced relative to the basis < Y1, 7Y2.., 7n > This gives rise to the reduced form (hil, hi2, * *. hin) where n Z eikckn hin - k=l hin = _ and n _ eikckn. n- = Ik=l mn [ Z eikck,n-l + inrn+n-1l,- ir _ -_ _ "n-l k=l eikckl + binrnl + cin-lrn-l,l + c.. + fi2r21 hil a I = ml where mj j = rjl51 + s*a + rj,j j-l l Similarly the i-th row of the product B ~ C is n n n (kEl bikCkly k bikck2 *'-~' k=l bikckn) reduced relative to the basis < 51,..., en >.

-39The reduced form is (Siln si2, **., Sin) where n Z bikckn s. k=l mn 7. bikCkn tin = k Si n-l -1 n T bikCk,n-l + tlnrnn-l k=l ti,n-l = k=ln-1 \kl bikCkl + tinrnl + ti n1l^-l +''' + t2r21 Sil = The i-th row of A(BC) is n n ( E aikSkl. aikSk2,.*, aikskn) kk=l k=l k=l reduced relative to the basis < *1.'*' 6n > The reduced form is (Vil, Vi2, *-., Vin) where n ( Z aikSkn k=l Vin =

-4oVin n n |Z aiksnkf - ^ k=l k=7l aikskn-1l + Uinrn,n-l 1 mn-l n Z= aikskn-1 + uinrnn-l ui n-l =.1.......... (mn-_1 n + Z aikSkl + Uinrn,l + ui n-l- + * + ui2r2 k=l Vil = i ml Selecting particular components for comparison n hin = eikckn) mod mn [( nSl aikbkn) mod mn * cn k=l n + ks' aikbkn-l + fingnn-l) mod mn-1 Cn-ln +. n + ( Z aikbkl + fingnl + fi,n-lgnl,1 + + fi2g21l) mod ml * cl, n] mod mn n n or hin = ( aikbkr mod mr)crn mod mn n-l n +, ( fijgj mod ma)' cQnmod mn.

-41Removing one term and changing indicies, one finds n hin = Z aikbkncnn mod mn k=l n-l n + [ Z ( aikbkr mod mr) crn] mod m r=l k=l n-l n + Z ( fijgjr mod mr) cn mod mn r=1 j=r n Z abkncnn mod mn k=l k knnn n-l n n + Z [ Z aikbkr +.Z fijgjr] mod mr Crn mod mn r=l k=l j=r Also n Vin = aikskn) mod mn (k=l n n [ail (k bikCkn mod mn) + ai2 (k b2kCkn mod mn) k=i k - n +... 2 ai (_Z bnkCkn mod mn) ] mod mn or n n Vin k= Z rl airbrkckn mod mn k=l r=l n n-l n = Z airbrnCnn mod mn + Z Z airbrkCkn mod mn Changining indic'ies for clarity, one obtains n n-1 n Vin = ZL aikbknCnn mod mn + Z Z aikbkrCrn mod mn. k=l r=l k=l

-42Since the first terms of hin and vin are the same, it is sufficient to look at n n [ airbrk + fijgik] mod mk (3-10) r=l j=k and n [ airbrk] mod mn ~ (3-11) r=l It is seen that the above expressions are not in general equal, for the range of Expression (3-10) is the positive integers less than mk whereas the range of (3-11) is the positive integers less than mno Since the mj are relatively prime, one is led to conclude that the i-th row of (AB)C is not equal in general to the corresponding row of A(BC). This was shown independent of the selection of the basis for the various image spaces involved. Therefore, no selection of basis will guarantee associativity of matrix multiplication.

CHAPTER IV THE MIXED BASE NUMBER SYSTEM 4.1 The Mixed Base Number System When one allows complementation as a means of subtraction, the representations are partitioned into two classes, those representations termed positive and those termed negative (or complements of positives). For sign determination and magnitude comparison, it is necessary to identify the classification of each and every representation. As is well understood, the elements of the residue number system contain insufficient information for making such an identification. The structure of the mixed base system makes the identification immediate. In addition, the mixed base system allows one to handle the problems of additive and multiplicative overflow, and division. We shall see that the mixed base system extracts payment in the form of carries for these advantages. The basis vectors for the mixed base system are generated in the following manner: 1. Order the prime ml, m2,..., mn 2. Set QO equal to the vector consisting of all ls. Beginning with j = n 3. Obtain aj-l = mjaj 4. Repeat step 3 with j replaced by j-1. Stop after performing 3 with j = 1. Theorem 11. The vectors {Cl,...,0 produced by the above scheme constitute a basis. -45

-44In order to prove the theorem Lemma 1 will be proven. Lemma 1: If (a, b) = 1, then (a mod b, b) 1 Proofo a = bg + r, 0 < r < b and by definition r is the residue of a mod b a a r mod b or a m (a mod b) mod b Since x = y mod z v (x,z) m (yz), (a mod b, b) - (a,b)o The conclusion follows. Proof of Theorem 11: an is a representation of the integer 1. The vecn tor Ce is the residue representation of A = i= +1 m. Each mi for i < 2 is relatively prime to Ay. Thus it is seen that ki. i 0 for i > X and (ki, mi) 1 for i < X. By Theorem 4 the set < al 2 o ~'. an > is a basis of Rn. Theorem 12. An element (xl x2> oo., xn) of the mixed base number system is a representation of an integer X in the range C - < X < (C+1) M if and only if x-l Co Proof: The element X = (xl x2, oo. xn) is a coding of the integer M M M x1 + - + x -— + x3 + o + xn modulo Mo (4-1) ml'mlm2 mlm2m3 Consider the quantity M M M X1 - M x2 m + x2 + x + - X (4-2) ml mlm2 mm2m3 The largest value Expression (4-2) can assume is attained when xi m m - 1 0

-45Upon substitution one obtains M M (ml -1) M- + (2 m)2 3 mm2m3 This is then rewritten as (m - ) + mn (mn - ) + mnmnl(mn2 - + + (m2 ) + - mlm2 ml remembering the scheme for generating the base vectors. All but the following terms add out: -1 + + M- 1. m1 ml This means that Expression (4-2) is equivalent to Expression (4-1). Consider next the quantity: (m2 - 1 (m3 ) mlmm + + -) rlm2 mim~m3 which is equal to (mn - 1) + mn (mn21 -) +mnmn (mn -1)... + (2 ) M mlm2 The above expression reduces to 1 + M. ml From this the conclusion is clear. To determine the sign of a mixed base number it is necessary to have a partitioning of elements representing consecutive integers into',two classes. The first coordinate gives such a partitioning if m1 is even, 12 i.e., xl < mj/2, — 0 < X < M/2. 12 The relevance of the mixed base number system to the problems of sign detection, magnitude comparison, and additive overflow has been cited by Garner and Svoboda.

-46When applying the Garry Algorithm to the reduction of the expression alOl + a2a2 +... + anan (ai is a base vector of the mixed base system) one must increase by one a. for every multiple of mj+l contained in a +1 (The notation here is consistent with that contained in the discussion of the Carry Algorithm). This indicates that a carry may be propagated from the n-th coordinate to the first. Therefore, when adding two elements of the mixed base system, one unit of time is required to produce the unreduced sum and up to n-1 units of time may be required to propagate carries. Borrowing is accomplished by reducing a' by 1 and increasing a+ by mj+1. Again up to n-1 units of time may be required to perform subtraction or complementation. Multiplication of two elements of the mixed base system was discussed and an example given in Chapter III. Theorem 13. When two mixed base numbers are added, the carries are binary and a position which produces a carry cannot also propagate a carry. Proof: The largest j-th component of the unreduced sum occurs when the j-th components of the addend and the augend are maximum, i.e., equal to mj - 1. The maximum sum will be mj - 2. Let j=n. The maximum unreduced n-th component will be 2mn - 2; therefore, the carry can only be zero or one. Consider j = n-l. The component 2mnl - 2 will produce a carry. If a carry was generated by the n-th position mn_l- 2 + 1 = mn_l - 1 < mn.lJ therefore, no carry is both propagated and generated.

-47Assume the results true for j=m. In this case 2mm_ - 2 will generate a carry of one, and 2mm_1 - 2 + 1 will also give rise to a carry of one. 4.2 Overflow A problem of the residue number system which can be solved with the mixed base system is overflow. In a mixed base number system where m1 = 2, the integers less than M/2 are represented in the system. Therefore, overflow is defined to be the condition where the true arithmetic result is an integer larger than or equal to M/2. First additive overflow will be discussed and then various conditions for the absence of multiplicative overflow will be demonstrated. (Due to sign detection and overflow conditions it will be convenient to assume ml = 2 for the remainder of this chapter. In this chapter all n-tuples will be elements of the mixed base number system.) Theorem 14. If the sum of two positive elements of the mixed base system is (Z,... z ) additive overflow occurs if and only if n Zl = 1. Proof: (Zl, z2,...* Zn) represents the integer M M Z1 2 + z 2m2 + "' + Zn mod M (4-) and overflow occurs when M M M Zl + z2 2m2 + n 2 This will clearly be the case if zl = 1.

-48The largest value that z2 2- +... + zn can attain has been shown to be - 1. The largest sum possible is 1 = M - 2 < Mo Thus Expression (4-3) becomes z1M + 2 +. + zn and the other 2 2m2 conclusion follows. To insure that multiplicative overflow will not occur, conditions will be given which will insure that no multiplicative overflow will occur as the partial products are formed. It is also necessary that overflow does not occur when the partial products are summed. This also will be treated. Consider (Yl, Y2.0o, Yn) * (xl, O,.0o, 0), Since M (xl, 0,..., 0)- --- -x, overflow will occur unless Y1 = Y2 oo =n 0 Consider next (Yl, Y2,., Yn)' (0, x2, 0,. o, 0) and note that (O, x2, 0,-.. O) —-x - Therefore, the condition which is necessary and sufficient for the absence of multiplicative overflow in this partial product is: Y1 =Y2 -= Yn-1 = 0 and x2' Yn < m2 Since (0,0,x3,0,..,0) represents x2m2m3 and (y1y2,. n) represents Y = Yn + Yn-lmn + Yn-2mnmn-1 + ooo + Y1 m- a necessary and sufficient condition to prevent overflow is M M < 44) x3 2m2m3 2 or x3 Y < m2m3.

-49Thus it is seen that condition (4-4) becomes 3(Yn + Yn-lmn) < m2m (45) and Y = Y = = Yn-2 = ~ Since Yn < mn we may substitute for Expression (4-5) x3mn(yn-_ + 1) < m2m3 to obtain a sufficient condition. Consider now the general partial product (Y1' Y2''' Yn)' (0..., O, xj, O,..., 0). In this case (0,..., 0, xj, 0,..., 0) represents xj M. To guarantee 2m2..mj that no overflow will occur we must satisfy the inequality xjy < m2... m: or Xj(Yn + n-1 + Yn-(j-2)mn *' mn-(j-3) + Yn-j+l mnmn-1' mn-j-2 + * + yl ) < m2m3mj. (4-6) The condition becomes Yn-j+l = Yn-j = * Y1 = 0 and xj(Yn Y n + + Yn-n + + n-(j-2)mn mn-(j-3)) < m2m3mj' (4-7) This constitutes a necessary and sufficient condition that this partial product does not produce an overflow. Again there are simpler inequalities the validity of which will imply the validity of (4-7). These

-50inequalities are xj [(n- + 1) mn + + Yn-(j-2)mn. mn-_(j_)] < m2m... mj, Xj [(Yn-2 + 1) mnmn- +. + yn-(j2)mn...mn_(j_3)] < m2m3.) mj, Xj [(Yn-(j-2) + 1) mn...mn (j3)] < m2m3.*mj The sufficiency of the above inequalities stems from Theorem 15. Theorem 15. If xi < mi I then x1 + x2ml + x3mlm2 + l.. + Xk* - lmm2 mk2 < mlm2... mk-l Proof: The maximum value that x1 + x2m1 + x3mlm2 +... + xkmlmlm2..~ mk-2 can attain is (mi - 1) + (m2 - 1) m1 + (m3- 1) mlm2 +... + (mk-l - 1) mlm2e.mk-2 = mlm2... mk-2 mkl - 1 < mlm2... mk-1 l Even when none of the partial products of a multiplication involve multiplicative overflow, overflow may result when the partial products are summed. Such overflow will be avoided only if the first coefficient of the unreduced sum is zero and no carry is propagated into that position. 4.3 Division in the Mixed Base System Utilizing the overflow rules given in this chapter, one may now state rules for performing division in the mixed base system. The conditions

-51for the absence of multiplicative overflow and rules for forming partial products provide a means for estimating trial divisors. The subtraction rules then allow one to determine the new dividend. The method will be demonstrated before the formal rules are stated. Example: Divide 95 by 14 using the mixed base system where ml = 2, m2 = 3, m3 = 5, and m4 = 7. 95 -" (0,2,3,4) 14 C- (0,0,2,0) Step 1: Determine first divisor a_ 0,0,2,0 0,2,5,4 It is seen that it is necessary for a = 0 to avoid overflow. Step 2: Determine second divisor 0, 0,0,2,0,2,3,4 A-gain to avoid overflow 3 = 0. Step 3: Determine third divisor 0,O,7 0,0,2,0 j 0,2,5,4 From overflow considerations it is seen that 7 = 1 is satisfactory. 0,0,1 0,0,2,0 y 0,2,5,4 0,2,4,0 It is seen that y =1 is too large; therefore, = 0. Step 4: Determine fourth divisor 0,0,2, 0 0,2,,4 010,2,0 0,2,5,4

-52From reference to overflow rules and multiplication the estimate is = 6. 0,0,0,6 0,0,2,0 0,2,53,4 0,2,2,0 0,0,1,4 The division is completed giving 95 = 6 * 14 + 11 The procedure for determining the trial divisor is as follows: 1. Consult the conditions for the absence of multiplicative overflow to determine the possible range of trial divisors. 2. Use the rules for forming partial products to determine a trial divisor which will yield the required zero(s) in the most significant place(s) and a non-zero component in the most significant non-zero position (k-th) of the divident. (The k-th component must be less than or equal to the k-th component of the divident.) 3. Subtract the partial product from the divident and if necessary revise the quotient so that the least possible non-negative result is achieved. 4.4 Digit Fill-In An addition problem which can be solved by using the mixed base system is the problem of digit fill in. If one is given the coordinates of a vector representing the integer relative to the basis A = {flC2,.2,' n} and base moduli ml,m2,..,mn, the problem is to express the integer s in terms of coordinates relative to be basis {l2'P''' * n' n+' * *' n+m} = B and base moduli m1,m2,. *,m n,mn+l, * o.mn+m. The mi are pairwise relatively prime.

-53Since one can represent s as a vector relative to the base n moduli ml,m2,...,mn, s is less than T m. Therefore, if s is i =1 expressed in the mixed base system relative to the moduli mn+lmn+2, *..,mn+,mmlm2,...,mn, the coordinates with weights greater than or equal to n mi must be zeros. The weights of the last n components of the mixed system will be, in reverse order, lmn,mnmnl,..,mnmnl... m2. These weights are the same as the weights of the components in the mixed base system relative to the primes m,m2,.o,mn. Therefore, digit fill-in is accomplished as follows: 1. Perform the change of basis operation from the basis A to the mixed base system. 2. Prefix the m zeros to produce the correct representation in the extended mixed base system. 3. Perform the change of basis operation, this time from the extended mixed base system to the basis B.

CHAPTER V OTHER NUMBER SYSTEMS RELATED TO THE RESIDUE NUMBER SYSTEM 5.1 Partitioning Properties In Chapter IV it was noted that the mixed base number system representations corresponding to consecutive integers are partitioned by the first coordinate. It was this property which lead to the solution of the outstanding problems of the residue number system. A question arises whether number systems exist which possess the desirable partitioning while having simpler rules of arithmetic manipulation. It will be shown that the only related number system to achieve a partitioning of elements representing consecutive integers is the mixed base system. Lemma 2: For any integer k within the range 1 < k < p, there exists an integer R such that p < k k < 2p where e < p and p > 2 Proof: It is evident that k,cannot lie in the range 1 < k < -Pp-l for p > 2, p-2 > O 2p-2 > p 2(p-1) > p; therefore, - < 2 p-l -54

-55Thus there exists an ipnteger - such that P < k < P with p > ~ and one concludes p < -k < -- p < 2p, Q.E.D. X-1 Theorem 16. If the base moduli are ordered ml, m2,.0o, mn, only the mixed base number system gives a partitioning of the elements (c+l)M into those elements which represent integers in the range less than (c+l)M ml but greater than or equal to c M, where c is the first coordinate of the element. Proof: We will consider all number systems which give the desired partitioning and conclude that they are all identical to the. mixed base system. Consider the number system based on the vectors < P1 P2,...,'> It is assumed that this number system achieves the desired partitioning. Here P1 corresponds to B1; P2 to B2; etc. An element of this number system A = (Y1, Y2, *'', yn) represents the integer YlB1 + Y2B2 +. + YnB mod M. For the set < P1,..' pn > to be a basis it must be triangular; therefore, one may state Bn = kn Bn1 = kn-lmn n Bj J i=j+l n B1 = k1 nt ml

-56where J 0 < kj < T mi. Consider yl = c and yi =0 for i 1. The expression YlB1 + Y2B2 +.. + YnBn mod M becomes c k1l m mod M. cM 1 M Y2 2 n n mM Clearly, m < ck - < (c+l) - for c < m1 requires k1 = 1. m- - ml ml One condition which must be satisfied is Yl =, Y <. This ml requirement becomes 2B2 + yB3 +. + YnBn = z mod M (5-1) M where z < m for all Y2, Y3', o Yn Consider first the case Y2 ~0 Y3 = O*' = Yn = 0. We have M Y2B2 = Y2k2 m If there is an integer ~ in the range 0 < ~ < m2 such that M < Mk M < M (5-2) ml mlm2 condition (5-1) is violated.- Expression (5-2) may be written m2 < 2k2 < mlm2. (5-3) By Lemma 2, it is seen that for k2 > 1, we can find an integer in the range 0 < 2 < m such that m2 < 2k2 < 2m2. Since ml > 2, inequality (5-3) is satisfied. Therefore, k2 = 1.

-57Assume that we have shown ki = 1 for i = 1, 2,.o., m. Let yi =mi - 1 for i = 1, 2,.., m,Ym+1 0, and Ym+2 = Ym+3 =.00 = yn = 0. Consider M M mlM M (m2-lM + - 1) mlm2m + ml..m Ym+lkm+l mlm2. mm or (m2 l)m3...mn+(m3 - l)m4..mn+... +(nmm - 1)mm +l. mn+ym+lkm+lmm+2.. mn which yields (m2m3...mn) - (mm+l.oomn) + Ym+lkm+lmm+2..mne But M _ But m = m2m3... e mn Thus the sum s is M = m- mm+l.. mn + Ym+lkm+lmm+2 * mn If M < s < M (5-4) ml - condition (5-1) will be compromised. Expression (5-4) becomes Mm+l *.. mn < Ym+lkm+lmm+2.~ mn < (ml - 1) M + m+l m which upon substitution for M yields mm+l *. mn < Ym+lkm+lmm+2... mn < [m2.o. mm(ml - 1) + 1] mm+l..o mn

-58Removing the common factor in the above expression one obtains mm+1 < Ym+lkm+l < [m2... mm(ml - 1) + 1] mm+1 (5-5) If m+l < km+1 < (ml-1)m2.. mm+l, (5-5) is satisfied by Y +1 = 1. If km+1 < mm+1 and km+1 > 1, Lemma 2 guarantees that there exists a Ym+l such that + < m+ Y+lkl < 2mm+ 1 but since 2 < [m2... mm(ml - 1) + ] 1 It is necessary that km+ = 1 or that (ml - 1) m2... mm+l < km+i < mlm2..o mm+l To see that km+i cannot be in the range (ml - 1) m2... mm+l < km+ < mlm2.^.o mm+, consider Ym+ = 1 and yi = 0 for i m + 1. Then s = Blm+ km+lmm+2 *.. mn and M < (m1 - l)m2 2. mn < mm2 m2 m M mli Again we have satisfied condition (5-4); it is necessary that km+, = 1. Therefore, the only number system which effects the partition described is that system having ki = 1 for i = 1,. o, n. This system is the mixed base number system.

-59Theorem 17. If the base moduli are ordered ml, m2,..., mn, there is only one number system with the property that the first coordinate partitions elements which represent consecutive integers into ml classes. That number system is the mixed base number system. Proof: Theorem 16 shows that there exists but one number system which partitions the elements into those elements which represent integers in the range less than (c + l)m — but greater than or equal to c m- ml where c is the first coordinate of the element. By definition this number system is the mixed base number system. It remains to show that no number system exists which effects the same partitioning for y1 f c. Assume such a number system exists with basis 1, 23,...,'. An element of the number system represents the integer Y1 B + Y2B2 + *. + YnBn mod M (5-6) Again we may state BA = kn J J i=j+l n B = k T m. i=2 1 where O < kj < ~ mi. The range imposed on k1 is O < k1 < m. i=1

-6oThus we have B = = kl M/ml and Expression (5-6) becomes ylk m mod M when Y1 j O, Y2 =* ~ = Yn = 1 It will now be shown that there exists an integer c in the range 0 < c < m1 such that c M < ylk M mod M < (c+l) M(5-7) cannot be satisfied for 0 < kl < ml, 0 < y1 < ml, and y1 f c Take c = 0. Expression (5-7) becomes 0 < ylkl M mod M < M. (5-8) ml ml Condition (5-8) will be satisfied only if Ylkl - 0 mod ml. (5-9) Since Yl A 0, (5-9) requires that k1 = O. This is the desired contradiction which completes the proof. Collary 1: If the base moduli are ordered ml = 2, m2, m3,.o., mn there is one and only one number system with the property that the first coordinate partitions the elements into two classes, the representations of the M integers less than M, and the representations of integers greater than M or equal to -.

-61Proof: This corollary follows from Theorem 17 with ml = 2. One now asks whether a number system with base moduli ml, m2,..., mn exists which partitions elements which represent consecutive integers into mj classes with the first coordinate where J 1? The number of elements having the same j-th coordinate in any system having mj as a base prime is n M= T mi m. i=1 J i^j Likewise, the number of elements associated with a particular value of the first coordinate is n M/ml = iT mi i=2 The number of elements in the two cases differ and the greatest common multiple is one. Therefore, the answer to the question posed in the preceding paragraph is negative. A similar argument shows that no number system with base moduli mi, m2,..., mn where (ml, m) = (m2, m) =.. = (n, m) = 1 exists which partitions with the first coordinate elements which represent consecutive integers into two classes, one class the elements of which represent integers less than M/m and the other class representing integers greater than or equal to M/m. The argument follows: Since M is relatively prime to m, m M, but m M - when 0 < < m. Let M = - = dm. If m <ml,ml M - B. If m > ml ml M - B for cm1 <a < (c+l)m1.

-62Suppose kml =, then m - m =m m2.o. mn - mlk but (m, ml) 1; therefore, m M - ~ which is a contradiction. The only related number system which produces a partitioning is the mixed base number system and; therefore, the proof is completed. From the theorems and arguments advanced thus far in this chapter, one concludes that the mixed base number system is the only number system which partitions the elements representing consecutive integers. In particular only the mixed base system with ml even partitions the elements representing consecutive integers into two groups-(1) elements corresponding to positive integers and (2) elements representing complements. Thus if one wishes to use a number system to determine the sign of the residue element, he will find it necessary to use the. mixed base system. 5.2 Number Systems Allowing Sign Detection with Fewer Than n-Carries It has been suggested that the use of number systems which are neither strictly residue nor strictly mixed base might ease the carry situation in sign determination. Such systems are those in which a certain number of carries are eliminated from the operation of expressing a vector in the mixed base system. As developed in the chapter concerning the Carry Algorithm, a vector X with coordinates (xl, x2,.0., xn) relative to the basis < 1 P2, 2',. n > is expressed with coordinates (Y, Y2,..., Yn ) relative to the mixed base basis < al, c2,.., n > by determining the Q = ||qijll matrix and following with the matrix multiplication X Q = Y. The elements of the Q matrix are governed by the equation Bi = -ill + e'' + -inQn for i = 1, 2,.oo, n. (5-10)

-63The Y so obtained will not in general be a linear form with restricted coefficients. Carrys must then be propagated from each position to the next more significant position. The general conversion will require up to n-l carries. To reduce the maximum possible number of carries which can occur by say m-l carries, it will be necessary and sufficient to guarantee Yk < mk for k = n-m,.., n. (5-11) This is in turn equivalent to the condition 4ik = ik for ik = n-m,..., n (5-12) Condition (5-12) may be expressed as n-m-l kk = ck + CikOi for k = n-m,.., n (5-13) If | laijl is the array of the mixed base basis vectors, consider the m x m sub-array in the lower right corner. Equation (5-13) states that this sub-array must be preserved in | bij |j, the array of the p vectors. The only other requirement is that I|bijll be triangular. Other considerations which affect the selection of the remaining elements in the B array stem from a desire to simplify the carry structure in the 3 system. Since aij = bij for i, j = n-m,.o., n the carry structure in the last m positions is fixed. Carries from the k-th components to the j-th components where k = n-m,..o, n j = 1, 2,..e, n-m-1

-64can be prevented by the following constraint b = 0 for i = n-m,.., n j = 1, 2,..., n-m-l. Further carries can be eliminated by making the upper right partition of the f array the identity matrix. Since aij = bij for i, j = n-m,..., n carries from the ~-th component to the (e-l)-st component will occur for X = n-m+l,,.o, n. Therefore, at least m-l carries will occur in the B system. The total number of carries in the P system for a subtraction followed by sign detection is at least as great as for subtraction in the residue number system and conversion to the mixed base system. Such number systems do not appear practical, for nothing is gained in addition and sign detection. In fact, from the Multiplication Algorithm cf Chapter III, it is clear that much speed is sacrificed in multiplication.

CHAPTER VI SUMMARY AND CONCLUSIONS The general question of the algebraic properties of the residue number system was treated. By considering the set of elements of the residue number system as a pseudo-vector space (the R-space) it was possible to define and describe the properties of a whole class of number systems related to the residue number system. Meaningful definitions of linear independence, linear transformations, and matrix multiplication were formulated. However, such vector space concepts as rank and row echelon form have no analogous interpretations in the R-space. It was proven that any triangular array of vectors will define a number system related to the residue number system if the elements on the principal diagonal are relatively prime to the associated base modulus. The Carry Algorithm and a variation, the Borrow Algorithm were given which allow arithmetic operations in number systems related to the residue number system. The mixed base number system has been known to afford solutions to the problems of sign determination, magnitude comparison, and additive overflow. Solutions to the problems of multiplicative overflow digit fillin, and division were shown. The R-space analysis led quite naturally to the known solutions as well as the new solutions of the problems of the residue number system. Solutions are possible because the mixed base number system partitions elements representing consecutive integers with the first coordinate. Thus when employing the mixed base number system the magnitude of the first coordinate gives the sign. The partitioning places -65

-66weights on the coordinates and allows magnitude comparison. Since overflow may be regarded as a variation of magnitude comparison, overflow problems may be solved. With these problems solved division by the Euclidean Algorithm is possible. The mixed base number system was proven to be the only number system related to the residue number system which incorporates the desired partitioning. Further, number systems were investigated which would require fewer carries for sign detection than the residue number system and possess fewer arithmetic carries than the mixed base system. It was shown that no net savings would be possible. The number systems related to the residue number system may be classified according to the maximum length of carry chains involved in addition. If this is done it is noted that the residue number system with carry chains of zero length possesses the simplest carry structure while the mixed base system with a possible n-l carries is the most complex. The desirable properties and the problems of the residue number system arise from its carryless structure. Similarly the solution to the residue number system problems exist because the mixed base system involves carry chains of maximum length. Thus one concludes that of all the number systems related to the residue number system only the residue and mixed base systems are of primary interest. The solutions to the problems of the residue number system depended upon the partitioning properties of the mixed base number system. In a certain sense these solutions are unique; therefore, it is not anticipated that the residue number system will achieve wide application in general purpose digital computers:.

BIBLIOGRAPHY Birkhoff, G. and MacLane, S. A Survey of Modern Algebra. New York~ The Macmillan Company, 1941. Cheney, P. Wo A Digital Correlator Based on the Residue Number Systemo Technical Document LMSD-702670, Lockheed Aircraft Corporation, Palo Alto, CalifO, 1960. Garner, Ho L. "The Residue Number System." IRE Trans. PGEC, Vol. EC-8, June 1959, po 140-7. Hardy, G. H. and Wright, E. Mo An Introduction to the Theory of Numbers. London, England: Oxford University Press, 1956. McCoy, N. H. Rings and Ideals. Buffalo, New York: The Mathematical Association of America, 1948. Svoboda, Ao Rational Number Systems of Residual Classeso Stroje Na Zpracovani Informaci, Sbornik, V, 1957. van der Waerden7 Bo Lo Modern Algebra. New York: Frederick Ugar Publishing Company, Vol. I and II 1950.