ASD TECHNICAL REPORT 61-483
RESIDUE NUMBER SYSTEMS FOR COMPUTERS
H. L. earner
R. F. Arnold
B. C. Benson
C. G. Brockus
R. J. Gonzalez
D. P. Rozenberg
The University of Michigan
Octo-ber 1961
Electronic Technology Laboratory
Contract No. AF 33(616)-7340
Project No. 7062, Task No. 706205
AERONAUTICAL SYSTEMS DIVISION
AIR FORCE SYSTEMS COMMAND
UNITED STATES AIR FORCE
WRIGHT-PATTERSON AIR FORCE BASE, OHIO

Ci
(

FOREWORD
This report represents the results of research performed by the group at
The University of Michigan under the direction of Professor H. Lo Garner.
Concurrently, research on the same subject was being conducted at Harvard
University under the direction of Professor Howard Aiken, and at the Lockheed
Missile System Division under the direction of Dr. Richard Tanaka.
There was a considerable exchange of information among the above groups
during the course of the research effort. The efforts attained exhibit little
overlap, rather they are complementary.
A portion of this report was extracted from the doctoral dissertation of
D. P. Rozenberg. His work was supported by this contract, and led to the Ph.D.
ASD TR 61-483 iii

ABSTRACT
The purpose of the research performed under this contract was to investigate the feasibility of residue number systems in their applications to
digital computers.
The problems of such an application are the ones of magnitude determination,
sign determination, overflow, scaling, and division. These problems are not independent, but are found to be quite interrelated.
A theoretical treatment of residue number systems is given which lays the
foundation for a unified study of the complete problem. Treatments of an organizational nature are given which deal with multiplication, division, and
scaling. The matter of correlating the theoretical and organizational studies
to physical realizations involving networks is treated also.
The question of whether the residue number system can be successfully
applied to general purpose computers is still an open one. Their application
to special purpose machines is considered both feasible and practical.
ASD TR 61-483 v

TABLE OF CONTENTS
Page
LIST OF TABLES xi
LIST OF FIGURES xiii
LIST OF SYMBOLS xv
CHAPTER
I. INTRODUCTION 1
1.1 Introduction to the Problem 1
1.2 The Residue Number System 4
1.3 Theorems on the Basic Properties of Residue Number
System 7
II. THE R SPACE 13
2.1 Basic Properties of the R Space 13
2.2 Linear Transformation and Matrix Multiplication in
the R Space 24
III. CARRY FUNCTIONS IN RESIDUE NUMBER SYSTEM AND RELATED NUMBER
SYSTEMS 33
3.1 The Carry Algorithm 33
3.2 The Borrow Algorithm and Complementation 37
303 Change of Basis 40
3.4 Multiplication 43
IV. THE MIXED BASE _NUMBER SYSTEM 53
4,1 The Mixed Base Number System 53
4.2 Overflow 57
4.3 Division in the Mixed Base System 60
4.4 Digit Fill-in 62
V. OTHER NUMBER SYSTEMS RELATED TO THE RESIDUE NUJMBER SYSTEMS 63
5.1 Partitioning Properties 63
5.2 Number Systems Allowing Sign Detection with Fewer
than n-Carries 70
5.3 Generalization of Sign Detection for the Residue Number System 72
ASD TR 61-438 vii

TABLE OF CONTElNTS (lor i.r' ed)
Page
V:I oDIGIT I EODIS.iN.E PEA.? 77
6o, Codes E.ased up&on tL he Group St-ructure of the
Eikt ipl.ic at ine Subogroup 77
6o2 Codes Based on Mudltipica'tion' as a Linear Transfo rmat ion 8
VII o DIVISION 87
7.1 Introduc tin 87
7 2 An. Approxi-mate Divisor. Meth;od 88
70 A Newton-Raphson Method 93
7o 4 Initial Approx:irmations 94
VIIIo TEE MULTIPELICA7I VTI COVERFLO.W PROBLEM 99
8.o1 tro.dut.....on 99
8.2 Application of ihe oSquare-Root Criterioen 102
8,3 Considerations of the Dout.e-ength System 104
8,4 mil tiplication 1.05
8, -5 Numher Format- and' Magr nitude C.omnparison 1.1
806 r7The Fo-ur Cases of Addition I 2
a. ",-( o: ~ion,3 1O2
8o7 Division 114
8o8 Carry Co^rpietion Sensirng 1.18
8 9 Postponed Scaling a-nd Special Parpose Machines 120
8, 0i A. Matrix -_n!ve rsio n ornp;L " r 122
8 1.1. A Method -recision C o par.ison 127
IX, I. LEVENAT' ). SIG N F DEEREMlAN!. IvETHODS 131
9 I- r l; roduc ti on 131
902 Residue 4to Mixed Bases Con.version Using Current
Sterin Circuitry 1.33
903 uLmoiber of El:.ementrs i.n a Conversion Network 141
9,4 Selection of oduli, for Maximumm Economy 148
90o5 The. App.lication of Binary Coding to Conversion Procedures Usin::g Stored Tabies 149
9,6 General Stri.ucure of the Network 151
9,7 Determination of the lumber of Elements of the Network 152
9,8 The Necessary Number of Binary Bits 160
9~9 Systematic Procedure for the Development of the Network and for the Determination of the Number of
Element s 162
ASD TR 61-458 viii

TABLE OF CONTENTS (Concluded)
Page
APPENDIX
Io THEOREMS ON THE GENERATION OF SEQUENCES OF RELATIVELY PRIME
NUMBERS 165
IIo A MIXED BASE AND MODULAR COMPARISON 169
IIIo SIGN DETERMINATION BY A IWO-DIGIT REDUCTION PROCESS 177
IVo COMMENTS ON PARITY CHECKING IN IHE RNS 187
REFERENCES 191
ASD TR 61-438 ix

LIST OF TABLES
Table Page
1. Encoding of the Multiplicative Subgroup 79
2. Factorization Procedure 80
3. The Code M = 17, n = 8 84
4. Table of the Function F(mi) 143
5. Procedure for the Calculation of the Total
Number of Elements 143
6. Number of Elements in the Conversion Network
for Different Sets of Moduli 145
7. Number of Elements for Networks of the Type (1+M) 157
8. Maximum Carry and Carry Propagation Length 158
ASD TR 61-438 xi

LIST OF FIGURES
Figure Page
1l An adder for the M = 17, n = 8 code. 84
2. Multiplication in the floating point RNS. 109
3. Step 3 of the magnitude comparison. 112
4. Addition in the floating point RNS. 113
5. Division in the floating point RNSo 115
6. Carry completion. 119
7. Block diagram of a computer. 124
8. Blcok diagram for scaling operation. 128
9. Switching network for residue to mixed
basis conversion network (1st part). 136
10. Switching network for residue to mixed
basis conversion network (2nd part). 137
11. Simplified schematic of the complete residue
to mixed basis conversion network. 139
12. Block diagram of the conversion network from the
residue system to mixed basis. 140
13. Variation of the number of elements in the
conversion network. 146
14. Switching network for sign determination for
a residue system with 3 moduli. 153
15. Block diagram of sign determination network for
a system with 4 moduli. 154
16. Carry matrix for three addends and corresponding
network. 156
17. Carry matrix for four addends and corresponding
network. 156
ASD TR 61-438 xiii

LIST OF FIGURES (Concluded)
Figure Page
18. General structure of the carry determining network
for the first column of K binary bits. 157
19. Carry determining network for the (2 to 3) case. 159
20. Carry determining network for the (3 to 4) case. 159
21. Determination of the number of elements in the
carry network. 163
ASD TR 61-438 xiv

LIST OF SYMBOLS
[x] The integer part of x (*)
(Ix The fractional part of x (*)
(ab) = c The greatest common divisor of a and b is c (*)
Ix m The residue of x with respect to m
a b; (a/b) a divides b; (a does not divide b)
a - b mod m a is congruent to b modulo m
a - b a is isomorphic to b
a " b a is on the order of b (is approximately equal to b)
x* x7 The modular complement of x
G: R - Sm G is a linear transformation from Rn into Sm
a -> a' a corresponds to a'
Two levels of switching elements
Switching element
{-^ I- Delay element
-( - Binary Encoder
Modulo five operation
(*)The brackets are also used at times to indicate association. The square
bracket is used also to indicate a matrix. The particular meaning should
be clear from context.
ASD TR 61-483 xv

CHAPTER I
ITTRODUCTI ON
1.1 INTRODUCTION TO THE PSROBLEM
The aspects of the residue class of the number system which makes this
class of number systems suitable for high-speed computation has been long known
to mathematicians. The first consideration of the residue class of numbers for
a computer system is due to Valach. This initial work was soon followed by a
2 3
paper by Svoboda, and later a paper by Valsch and Svoboda. Svoboda must be
given credit for the most fundamental and comprehensive study of the application of residue class to practical computing machines. In his paper, "Rational
Number Systems of Residue Classes," he considers both fractional and integer
number systems' The residue number system is most naturally interpreted as an
integer system, though the fractional interpretation allows greater flexibility
with respect to the problem of scaling. The paper by Garner considers only
the integer interpretation of the residue nmber system and suggests a unified
approach to the problem of sign detection. The first part of this research report is a continuation of the study of the vector-space approach to the sign
detection problem.
Carry propagation accounts for the major portion of execution timre in a
conventional arithmetic system. The residue number system, based on the algebra
Manuscript released by the University of Michigan, October 1961, for publication
as an ASD Technical Report.
ASD TR 61-483 1

of residue classes, permits addition and multiplication to be performed without the existence of carries. The main advantage to be gained from the residue number system follows from the fact that it should be possible to execute
multiplication as rapidly as addition. The usefulness of the residue number
system for general purpose computation is still an open question. However,
there exist many favorable applications of a special nature. Cheney5 has designed a digital correlator based on the residue number system and has estimated that a correlator of similar accuracy, based on the binary system, would
have been 10 to 100 times slower, depending on whether the organization were
parallel or serial. The residue number system has several characteristics
which have prevented the adoption of this system for general purpose computation. The problems of sign detection, the detection and handling of additive
and multiplicative overflow, and division are of extreme practical importance.
In this report the algebraic and numeric properties of the residue number system are investigated in order to determine algorithmic solutions for the above
problems. Considerable attention has been given to the nature of possible algorithmic solutions. This is, in many cases, more important than the actual
algorithms.
In the remainder of this chapter, the residue number system is shown to
be a ring. Various well-known ring theorems are interpreted in terms of the
residue number system to provide fundamental information concerning the problems of sign detection, the representation of negative numbers, and division.
Other theorems provided in this section relate to the construction of residue
number systems.
ASD TR 61-483 2

In Chapter II, the basic algebraic structure required for the investigation
of the residue number system and other number systems is developed. In Chapter
III the carry structure of the class of non-r edundant lnumber systems is determined. It is shorm that the residue nrumber system is a member of the class of
carry-type ntumber systems' focr Thich the carries are congruent to zero modulo
base of the number system. In Chapter IV, the characteristics of the mixedbase number system are determinedO In Chapter V, particular attention is given
to the problem of sign detecticno It is shown that the only non-redundant number system with simple sign detection characteristics is the mixed-base number
systemr Trhis fact is used to establish a general definition for the sign detection process. In Chapter VI the problem of multiplication for a residue
number system is studied. iT particular, two different multiplication schemes
are presented. The first is based on the decomposition cf the ring structure.
This obtains a simple multiplication algorithm at the expense of complicating
the addition algorithm. The second approach uses redundancy to speed the multiplication process and. is termed A-codingo Both of the techniques offer advantage over conventional residue coding when the moduli are large.
In Chapter VII, division for a residue number system is considered. Two
division schemes are presented. One is based on a Newton-Raphson iterative
procedure, while the other depends on approximation to the integral part of
the quotient. In Chapter VIII specific attention is given to the problem of
multiplicative overflow. Various schemes are considered and a special purpose
application of the residue number system is given. In Chapter IX the problem
of sign detection is considered in terms of physical realizationo
ASD TR 61-483 3

1.2 THE RESIDUE NUMBER SYSTEM
As a preliminary step in the introduction of the residue -:umber system9
the ring iM of integers modulo M will be discussed.6 The elements of the ring
are the integers 0, 1i 2, 0. M-l. Ring addition and ring multiplication of
two elements of IM are performed by reducing the conventional sum and product
modulo M. That is, the sum or product is divided by M and the remainder is
retained as the result~ Thus, for example, the ring I6 cQnsists of the integers 0, 1, 2, 3, 4, 5o Dividing the ordinary sum of 4 and. 5 by 6, one obtains
3 for the remainder. Therefore, in Te, 4+5 = 3. Similarly 2+4 = 0, 2-2: h,
and 4.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. The order of IM is M.
Consider 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 M. If one denotes the correspondence of m to m by
m -~, m, it is clear that if mi - n, m 2 mf- m2, then m+m2 ~ mi+m2 - m +ma2
and mm m2>ml1m2 = m1ms2 Therefore, the correspondence between I and IM is a
homomorphism.
Fixed point digital computers do not operate upon the ring, I, of integers
but rather on the ring I-. If one thinks of the radix point as being on the
right, then the largest number which can be represented is M-lo That the homomorphism is a many-to-one mapping is painfully apparent when overflow occurs
arnd. the most significant digit(s) are lost. Fortunately, one can detect such
an overflow by sensing the carry from the most significant digit position. The
ASD TR 61-483 4

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/29 and the negatives greater than -M/2 onto the
remaining elements of IMo Thus the sign is readily determined and thereby magnitude comparisons can be performedo Since one can perform overflow detection,
sign determination, and magnitude comparisons, division is possible.
Let SI and S2 be two rings and consider the ordered pairs of symbols
(s5n,2) where sieSL and s2eS2. If one defines addition and multiplication to
be (sls2) + (tlt2) = (s1 + tl,s2 + t2)
and (sls2)(t,t2) = (sltl,s2t2)
this set of ordered pairs becomes the ring S termed the direct sum of S1 and S2
and denoted S1 6 S2. In the above definition the operations si+ti and siti are
the ring operations of Si.
An especially important theorem is the following:
6
Theorem I. If a ring S has positive characteristic n = nl n2 where nl
and n2 are greater than 1 and relatively prime, then S is isomorphic (-) to
S1 0 S2 where Si is a ring of characteristic ni(i = 1,2).
This theorem states, for instance, that 16 is isomorphic to the direct
sum I2 e I3 with the following mapping:
C -- (0,O0) 3 ~-> (lo0)
1 <-> (1,1) 4 -> (O,1)
2 <-i (0,2) 5 -> (1,2)
Theorem I may be extended as follows:
Theorem II. If the ring IM has positive characteristic M = mlm2...mn
ASD TR 61-483 5

where the mi are integers greater than 1 and pairwise prime, then
IM -rt ImD2 i~ I. ( m
Proof: If n = 2, the result follows from Theorem I. Assume the result for
n = k and consider M = mlm2...mkmk+l. M may be rewritten M = m1m2...mk, where
m = mkmk+l. Thus we have
IM iml I m2 mk
but by Theorem I,
mI mk Imk+l
Therefore,
IM = Iml M2 I —. 3 Imk+l.Thereby, the conclusion is proved.
Theorem II completely defines the residue number system. Elements of IM
are mapped into n-tuples of the direct sum (elements of the residue number
system) according to the following scheme:
x 4> (x mod ml,x mod mi2,...,x mod mn). (1-1)
If
x (-> (xl,x2,... Xn),
then
x + y -> (xi + y1mod m...,xn + ynmod mn)
and
x ~ y - l (xlylmod ml,...,Xnynmod mn).
It is clear from both the example following Theorem I and Expression (1-1)
that the components of the residue representations have no positional significance.
ASD TR 61-483 6

Con sider the fo1lrlow ex ampies of aflitions in the ring I210 with m1 - 2
ms = r39. a 5 ^ rl 7m ~
\a) 209 -+ (i,2,,69 (b) 209 -4 (1,924,6)
21 — 7 (C, I) 10t (020,4,6)
(c) 210^ <~ (1,0,0,0) 2 c-> (1,2j,69 )
120 - ( 09o )1 ) 162 7- (1,22,26)
015 — 2 ( 1,0,0,) 185 ee (0,1l0,0)
In example (a), the sum prod.ces an overflow and each component ring indicates
an overfloTo The s-um in (b) overflows but only one component overflows. In
(c), overflow occurs but the component subrings do not indicate overflow No
overflowT accompanies the addiition in (d), howeTve r overflow is present in each
component. These exaimples indicate that overflow in the component subrings is
unrelated to overflow,of.o Similar statements may be made concerning multiplicative overflowo
1o3 THEOREGMS ON THIE BAi3tC PROPEiRTS ES OF RESi LTJE UMER SYSTEMS
The'eorem T1. T.he- peTriod o(f a residue class,number system is equal to the
least common mulltiple (cm) of the aseso
Proof. Given bases mi ooogmno Assume mi jmj, ijthe then the digits associated
with modulus mirnj have a period equal to mj. Thus, min has no effect on the
period and may be dropped from further consideration. The process may be continued for remaining bases until for all pairs milmj, ifj. The period is
n
given by the product M =k i mn.. The product is the lcm of the original bases
since, by the f'undamental theorem of arithmetic, the product of the bases is
ASD TR 61-483 7

P P1i P Pi P2 p P2P.f..lPm
the lcm of P, denote by <P>, is
<p> = p max p max.p P max,
Obviously, <P> = M.
Corollary: The maximum length period is obtained when the bases are relatively
prime by pairs. i.e., (mimj) = 1.
Theorem IV. The replacement of all residue digits, ri, associated with
base mi by the modulo mi productl ri mm where c a 0 and a < mi, yields a number system with period M', where
M
(C,mii)
Proof:
1. N - aimod mi
2. oc - = aimod mi'N Ca i [ mi
3 (,mi) = (ami) mod (cmi )
mi M
4. M' = ml.. on = 1
(Ogmi) (Oami)
Theorem V.
The successor of X an element of a residue number system R may be defined as
X' X+ X R
X c R
e R
The period of R is given by
M
M' = (M, )
ASD TR 61-483 8

Proof
For the standard residue number system
X' = X+ 1
Multiplication by 5 yields
XI = X+5
Hence, the change of successor is equivalent to multiplication of each element
of the residue code by the residue representation for 5. This situation is
covered by Theorem IV. It is necessary to verify that
(M,&) = (ml Qal).o. (mnvOQn)
where 5 is represented in residue code by al,..,an. But this is obvious since
(M,5) = (m1,5)... (mn,5) - (mei,) o (mnon)
(ala2,b) = (alb)(a2,b) _ (al,a2) = 1
Theorem VI. Isomorphic mapping between the ring of integers IM and the
residue number system consisting of Im,..Imn exists for any successor value
n
5,(5M) = 1 if the operation is addition. If the operation is multiplication,
the isomorphic mapping exists only if 5 = 1o
Proof:
sa + b = (a + b)
but
(5a) x (5b) i 5(ab)
except when 52= - mod M, 5 -= 1 since (5,M) = 1.
Corollary: Isomorphic mapping is obtainable between IM and Im,...,I if
each multiplication is followed by a corrective multiplication by S.
The results of Theorem VI, and the corollary indicate that the integer
interpretation is the natural interpretation for the residue number system.
ASD TR 61-483 9

Any other interpretation will require multiplicative correction to preserve
the interpretation.
Theorem VII. Consider the residue digits ri and r. associated with bases
mi and mj; then the operation ri-rj m partitions the set of mimj residue
digits into j subsets. Each subset has i elements. The subsets are ordered
modulo mi.
Proof:
1. N - rimod mi
N - rjmod mj
2. N = ri+miti
N = rj+mjtj
3. ri-rj = mjtj-miti
4. ri-rj = mjtjmod mi
(ri-rj)/mj - tjmod mi
Note: If N < m.mj then t. < m and I(r.-r)/m = t
3 31i j j3mk
Example: ml = 2,m3 = 7
rl r2 -rl-r21l Ir2rll m2 41 r2-rl m21m
0 0 0 0 0
1 1 0 0 0
0 2 0 2 1
1 3 0 2 1
0 4 0 4 2
1 5 0 4 2
0 6 0 6 3
1 0 1 6 3
o 1 1 1 4
1 2 1 1 4
0 3 1 3 5
1 4 1 3 5
0 5 1 6
1 6 1 5 6
ASD TR 61-483 10

Theorem VIII. Consider the ring R. For every a and. b elements of R
a*b* = ab
a*b = (ab)*
where a* is the additive inverse of a definad as a*+a = 0. Every element of a
ring has a unique additive inverse. This is usually given as one of the postulates of a ring. This postulate and Theorem VIII taken together indicate two
possible correspondences between the elements of the ring, the inverse elements
of the ring and the positive and negative signs. The usual convention specifies that an element interpreted as an additive inverse of a represents -a.
Thus the additive inverse provides a code for distinguishing positive and negative numbers. The code is valid for'both addition and multiplication but is
useful only when the ring is partitioned into elements always interpreted as
magnitudes and elements always interpreted a.s inverses, and a simple means
exists for determining the correct partition for a given element.
Theorem IX. For every a and b; b / 0, elements of a ring there exist
x and y such that
a = bx + y
However x and y are not unique.
Theorem X. For every a and b; b b 0 there exist a unique x and y such
that
a = bx+ y
if y < b. y < b may be interpreted in terms of the successor concept. Let
y = a Znd b Then y < b if lrj Ilm m is the cardinality of the ring.
Theorem IX and Theorem X provide some insight into the nature of the division algorithms associated with any finite number system. The residue number
ASD TR 61-483 11

system is included in the class of finite number systems. Observe that
a - y mod b
and if y < b then
alb = y
Furthe rmore
a-balb
A T-b 1alb = a = x
ASD TR 61-483 12

CHAPTER II
THE R SPACE
There are many aspects of the residue number system which suggest the
appropriateness and usefulness of the vector space model. This approach is
pursued in this chapter. It will be shown that strictly speaking the residue
number system is not a vector space. However, a development including much of
the conventional vector space concept is a useful tool for the investigation
of the residue and related number systems. The appropriate axiomatic system
has been called the R space. The basic properties of the R space are developed
in the chapter and are applied in the next three chapters to the basic problems
of the residue number system. We have found no property of the residue number
system which cannot be validated using either the R space approach or the number theoretic approach. However, depending on the nature of the problem, usually
one approach is more suggestive
2.1 BASIC PROPERTIES OF THE R SPACE
Let any two residue representations be
x = (XigX2,...nxn)
Y = (Y1,Y2,i ~,Yn)
then x+y = [xl+yl(ml),...,xn+y(mn)] where the mj are pairwise relatively prime.
The component xi is said to be associated with the base modulus mi. The residue
numnber system representations from an additive Abelian group which is denoted
by R. From S, a ring with identity, we select the integers and define multiASD TR 61-483 13

plication by a scalar to be
ax = [axi(ml),...,axn(mn)]
With these definitions it is seen that
a. axcRn,
b. a(x+y) = ax + ay
for
a(x+y) = (a[(xl+yl)(m) ](ml),..,a [(Xn+Y n)(m) ](mn))
= ([(axL)(ml) + (ayl)(ml)](ml),...,
[(axn)(mn) + (ayn)(mn)](mn)]
= ax + ay
c. (a+b)x = ax + bx
since (a+b)x = [(a+b)xl(ml),...,(a+b)xn(mn)]
= [(aXl)(ml) + bl(ml)](ml),...,
[(axn)(mn) + bxn(mn)](mn))
d. (ab)x = a(bx)
for
(ab)x = [(abxl)(ml),...,(abxn)(mn)]
= a[bxl(ml),..,bxn(mn)]
= a(bx), and
e. All elements of Rn are uniquely expressible as linear forms
aleL +... + anen by means of a fixed basis elements with
O 0 ai < mi where ej has one for its jth component and zero
for the other components.
The five properties which must be satisfied for Rn to be a n-dimensional vector
ASD TR 61-483 14

space a, b, c9 d above, and
e v All elements of Rn are uniquely expressible as linear forms
alul + o.o + asun by~ means of a f ixed "basis eiemen ts"
ui o Un and ai S.
This property is not satisfied9. and thus RP is not a, true vecto. spa.e. Tie:
pseudo-vector space R-1 will be callecl the R-space and all vector spa-ce terms
which follow will have an interpretation in. the R-space whnich is analogous to
the vector space definitionso
Consider the set of vectors <ai~. o,> wi-th each ai having n components.
Form a squlare array of the components by placing the com-ponrent's of a. in the
ith rowo If this array can be made triangular (specifically a lo'ner triang-ular
array) by reordering rows and coui-mans the set <Cai o O:> is termed, sem -
triangular and the reordered set termed triangular.
Theorem XIa If the set {l, ^o OOa ) is triangular and the elementr s on the
principal diagonal are relatively prime to the associated base moduli., then
any linear form aL a + a22, - -. + a-,C w.here the ai are integers can be
uniquely expressed as
n
L ciai where 0 < ci < mio
i =l
Proof~ kncn Knn anmod mn
where kij is the jth component of ai *
Thus cn - an mod mll since mn is relatively prime to k,, and 0 c, < mn is
uniquely determined.
*a - b mod m (a is congruent to b modulo m) if and only if mj a-b (m divides
a-b or a - b + kmn).
ASD TR 61-463 15

Assume the conclusion true for cj for j = m, m + l,...,n and also that
these cj have been determined and consider the congruence
km-l,m-lCm-l + km,m-lCm +. - + kn, m-ln
kmil,m-laml + kmmlam +... + kn,m-lanmd m_1By adding to both sides of the above congruence the additive inverse of
(kmm-lCm +. + kn m_lCn)mod mm_l, this congruence takes on the form
kml,mlCm_l = A mod mm-l_ Since (km-_l,m-lmml) = 1, Cm-1 is uniquely determined mod mm-l and
0 < Cml < mm-l
Theorem XI is of key importance for it allows us to abandon the ring S
and to concentrate our attention on linear forms of triangular sets of vectors;
n
namely, Z ciQi where < i, ~'.,~^n> is triangular and 0 ci < mi. Except
i=l
where indicated, the following discussion will be limited to sets of triangular
vectors and linear combinations with restricted scalars.
Definition: The vectors c,...,cn of a triangular array are linearly independent if and only if
c la +... + Cnn = 0 where 0 < cj < mj
implies cl = c2 =... = cn = O. Otherwise the vectors l,...,n are termed
linearly dependent.
Theorem XII. The triangular set of vectors < a1oy2,...o, n > is linearly
independent if and only if each element on the principal diagonal is relatively
prime to the associated base modulus.
*The greatest common divisor (d) of a and b is written (a,b) = d.
ASD TR 61-483 16

Proof Consider the ecuation
cO1 + cCo + c. o f2-i)
Equation (2-2) is eouivale-nt+ to e follwing smultaieous linear cotngrue -,ckc c+ k._ c = 0 rmo d m
for
iL = __, i + t hi
o rkn _. _ O S. l ~
For knrCi C 0 mo. mr to,;-ield r-.te u:rique sclu, ltc c-, 0, it is sufficient that
(knnpmn) - Assume (k:,rm) I and. c = 0 for i 2; + 1, + 2,.,. The
th congrue<nce tbecomes?kc - 0 m0od nm arnd. c = 0 is'te unique solutio. This
prov-es the suffiiciency,of thee h.ypowti esiso
Assume r to be the least nd.ex for which (. rl) lo Let c- C for
i > r. The above congruence.s become
k:cr ~ - 0 0n m.d (2-2)
r
kiici + L kji 0 mod. mi for i r-lr-2.oo l
Ji i+l
Congruence (2-2) -aay'be sol-ve, Vwith c^ 0C Since (k i) = or i =r-1
r-2..o.,I, the remaining congruerces assunmt me e form,
The ondition (i ) < ganee the existence of a solution
The condit-ion (kilsrn ) - cr i' <r gJL.ara..!te. e existenlce o f a s,-Iultion
for each congruenceo This completes the proofo
Definition: A set of vectors {az ~o0o._o.} 2ris said to span PR if and. only
if there exists a set of coefficients ci in the range 0 ci < mi satisfying
the equation
ASD TR 61-ot83 1 7

n
Z ciai = ri
i=l
where ri is any residue number.
Theorem XIII. For a triangular set of vectors < CGl,..,a > 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
knnCn anmod mn (2-3)
n
and kiici + j1 kjicj - aimod mi for all ai in the range 0 ai < mi. The
necessary and sufficient condition for the existence of a solution to (2-3) is
(knn,mn) lan 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 > Q. These
solutions are substituted into the ~th congruence yielding an expression of
the form
k1gcA + D ammod mi
or
k~c~ -- a, + E mod mi
Again (a2 + E) mod mE will include all integers in the range 0 through mi-l.
Thus to guarantee solution it is necessary and sufficient that (k~,m)) = 1.
The proof is complete.
Corollary: The triangular set of vectors <l,... > 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
ASD TR 61-483 18

which generate the R-spaceo
Theorem XIII may be rephrased in more conventional terms as follows:
Theorem XIV. For a triangular set of vectors <al,...,> to be a basis
of R it is necessary and sufficient that each element on the principal diagonal
of the array be relatively prime to the associated modulus.
Theorem XV: If l,....,a forms a basis for Rn, then every vector eRn
has a unique expression
C = Xlal + X22 + + Xnn, 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
= (blb2,.,bn).
The first congruence is xnknn -n bnmod mn. Since knn and mn are relatively prime, xn is uniquely specified modulo mn. Assume Xm+lxm+2),.. xn
have been uniquely determined. Then to be considered is the congruence
kmmXm + km+l,mXm+l +... + kn,mXn bmmod mm.
Add to each side the additive inverse modulo mm of
(km+l,mxm+l +.. + kn,mxn)
to obtain
km,mXm - B mod mn.
Since (kmn,mm) = l,xm is uniquely determined modulo mm.
Theorem XV 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. It is now shown that triangularity is a
necessary as well as a sufficient condition for a nonredundant number system.
ASD TR 61-483 19

Theorem XVI. If the set of residue numbers, <Kc)2,...n>, spans Rn
n
(i.e., rcR n (aia) aixi = r) then the set is triangular.
i i
Proof: If
(ala2,..,a n) E 0 alc1 + a2Co +... + anCn
(bjb2,. o,bn) < bill + b202 +... + bnOn
From the properties of Rr it follows that
aiji + biai = (ai + bi)0i
then
(aicj + a2%c +... + anc) + (blCX +... + bn%) =
(al + bl)aO1 + (a2 + b2)c% +... + (an + bn)cn =
A
dall + d2c2 +... + dna+n = S
Consider the form di = miqi + ri in which miqi is an integer; then
n
miqi Z eijOj
and
n n n
S = riai + ZE qjejiai
i-l " iJJi=l j=l
n i n )
-=! (r + q.e a
i=l\i j=lge ij
The above expression yields the residue number which is cqngruent to the
sum S modulo M; It is not, however, the required expression for the sum. The
desired sum has restricted coefficients, O0< ai < mi. So consider the above
expression to be
1 1 1 1 U
S = d.^ l + dd2oQ + -.. + 2. d n
2
This sum is manipulated to yield S, and the process is continued until
k+l k
S = S. It will be shown that the existence of this sum is equivalent to
ASD TR 61-483 20

triangularity.
The next step of the proof will be to show that no carry cycles can exist.
Assume that carry cycles of length k, when k n, exist. That is
ek,k-l 0
ek-l,k2 # 0
ii,k 7 0
and
ejk = 0 for j > k
Consider the element (xi,x2...,xkO,0,0,0), where xi < mi-l. Since Rn
is an additive Abelian group, the additive inverse of the above element exists.
Assume it to be
(Yl,Y2,2-,Yn)
Further it is known that the sum
(X1,X2,...,Xk,...,0,0,0) + (Yly2,. -,Yn) = (0,0,...,0)
No carries can enter this initially from outside the group of k under consideration.
Case I. k = 1: here, eii f 0; eji = 0, j > k.
A. xi + i must produce a carry into the first position, thus the first
component of the sum is non-zero.
B. If the sum, reduced modulo m, plus the carry is mi, there must be a
carry in the first position and the result is non-zero.
Case II. The general case.
A. It will be necessary to have
a. Yk = xk to get a zero in the kth position. This will produce a
ASD TR 61-483 21

carry to (k-l)th position.
b. If jth position produces a carry, the (j-l)st will also produce
a carry, for the (j-l)st unreduced sum is non-zero and will have
to be made congruent to zero by the addition of an appropriate
yj -l
It can be seen that there will be at least one full cycle of carries.
B. Assume we have had I full cycles of carries.
a. The sum of carries plus the previously reduced sum is in the
kth position. This is non-zero. If this sum is < mk the desired
contradiction has been obtained. That is, the existence of the
additive inverse has been contradicted. A carry must propagate
from k to k-l, otherwise the inverse does not exist.
b. Again it may be argued that, if the jth position produces a carry,
the (j-l)st position must also produce a carry.
Therefore, there are I + 1 carry cycles and the carry process does not converge; the proper sum is not obtained. This is the desired contradiction which
proves that it is not possible for carry cycles to exist.
From the fact that carry cycles of length 1 cannot exist it can be seen
that the principal diagonal of the carry matrix consists of zero elements only.
Since there can be no carry cycles of length 2,eij 0 =~ eji = 0.
The next step in the proof of the theorem is to show that the number system must have a carry matrix which is a lower triangular array with zero elements on the principal diagonal.
1. Initial Step. There must be at least one column which is composed
ASD TR 61-483 22

entirely of zeroso If this were not the case, there would be carries into
every position; and thus carry cycles
2. General Stepo A.ss-le there is one column with at most k-l non-zero
elements for k = 1,2,.o o, o There is a columrn with at most ~-1 non-zero
elements.
The array may be rearra:nged by placing the column, with k non-zero elements in the old array, into the kth column of the new array for k = 1, ~+1,..,n. The rows are interchanged in a similar manner, giving
0
x C
I 0',. x x 0
~an~ let e
Consider a non-zero elerment ei,1 above the principnl diagonal in the
(Q-l)st column. Since eij / 0 implies eji = 0; row i may be interchanged with
row Q-1, and columr. i with col'urmn 1- w-hile retaining e-i, ~1 = 0 and
ei e-i = 0. Thus all non-szero elements are placed below the principal diagonal.
To complete the proof it is onl'y necessary to note that since the base
moduli are pairwise relatively prime, multiplying a vector by the ith baSe
ASD TR 61-483 23

modulus can create a zero only in the ith position. Thus a carry matrix
with all non-zero elements below the principal diagonal implies that the set
< l, * 2.ooOn > is triangular.
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 Rspace Sm is a transformation which satisfies
( + n)G = CG + G
(cj)G = c(aG)
Theorem XVII. If Oll,..,cn is any basis of R and.,i.. are any vectors in Sm, then there is one and only one linear transformation G:RnSm with
aoG = 71
cnG = n
This transformation is defined by
(x1la +... + xnG = x X272 ++ + Xnyn
Proof: Let A = (a,.. ~ be a basis for Rn
and B = (1 m,.,im) be a basis for Sm.
then
liG y- 7
onG = 72
UOnG - Yn.
whe re
yi = ails +... almm
ASD TR 61-483 24

for
i = l,..o,n.
If
[ = (Xi,oo.xn)AsR
then
= xjaz + o. + XnQn,
from which results
oG = xl(aiG) + x2(%0G) +. + xn(anG).
By substituting for (aiG), one obtains
x= x(a113 + - + almsm)
+ x2(a2131 +... + a2mPm)
+ xn(anii + * + anm.m)y
and by rearranging terms,
CG = (xlaii + x2a21 +... + Xnanl)3
+ (xla12 + x2a22 +..+ + xnan2)2
+ (xialm + x2a2m +..o + Xnanm)mBy Theorem XI the image ~G can be uniquely expressed
m. di P
where
0 < di < mi
and, therefore, GeSm and the transformation G is a linear transformation
Rn+sm.
ASD TR 61-483 25

Let
= (Y1,. * yn)A
then
= Ylal +... + YnanThus
~G = yl(alG) +.. + Yn(anG)
= y +Yl +... YnYn
+ n = (X1 + yl)C1l +.o. + (xn + Yn)Cn
(5 + n)G = (x + yl)aG +... + (xn + yn)OnG
=(xl + yl) 71 +... + (Xn + Yn)7n
= XlYl +... + x7n + YlY1 +. + YnYn
and c( = cxll +...+ cx*nn
(c )G = (cxl)clG +... + (cXn)(CYnG)
= cx7Yi +. + Xn7n
= c(G).
Thus the transformation is linear. It is to be noted that it is not necessary
that the set (71,...,Yn] be a triangular set.
Since every vector in Rn can be expressed uniquely as xlal +.. + xnn
for 0 xi < mi, the transformation is single valued and, therefore, no other
transformation from R into S yields BiG. The proof is complete.
Let A = (c.,...,cn) be a basis for Rn and B = ([,... - m} be a basis for
Sm. We then have the equations
CSlG = all-1 +..e + a26
ASD TR 61-583 26

O2G = a21zl +.*. + a2mPm
OnG = ani +i +.o + anmrn
The form of these equations suggests writing the square matrix
alla12 *2 aim
a2i1 a~2m
a =
ani ao mi
If Rn, Sn, and Tn are three n-dirmensional R-spaces, G is a transformation
n n
of R into S, and H is a linear transformation of Sn into T. The product of
the transfornations is defined
a((GHf) = (-G)
Theorem XVIII. 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 0,, cU be vectors in the domain of G. Then we have
(c, + 2 )(GH) = [(x, + cx)G]H
= [(c1G) + (ac(G)JH
- (o1G)H + (o2G)H
and
(cOCX)(GH) = [(caO)G]H
[C (c i \; )] I
-:: (:K-ii) ].H
ASD TR 61-483 27

Muultiplication of linear transformations has been dBefined 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 - u i,. )
B = (3i ^~~1n)
and
C
C = {71^.o7)}.
Relative to these bases G has the matrix a and H has the matrix 3.
Consider the matrix P = |iPij I| 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
clG all:L +. o + aln3n
OcG = a21Ii + o + a2nn
nG = a= nl + + ann nr
and
5mH = bY17, +..+ bln7n
H = b21171 +... + b2Y n
PnH = bn1l + o o + bnn7n
Thus (caG)H = all-(1H) + al2(S)2H) +... + a(in(H)
= all(b171 + bl72i +. o + b n7n)
+ al2(b21T7 + b2272 + -.. + ban7n)
+ a n(b7, +b bm7 +.. + bnn^ n).
ASD TR 61-483 28

Therefore
n n
(%7GHT) = alkbkl, aikb.,, L akbk i.
k/^1 k=l k=1
Similarly
/n n
(CY2GH) a b a b a b
(CocE) -- C a2kbik 1 a2k k2'' 2kbkni)
k~ ~k=-l k=1 /
Thus
/n n n
(UnGH) a a
(cinG:) = Zn abklZ=bl;ankbk2p. n Jbkfk
k=l- /l k
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 coefficientso The linear form with restricted coefficients
corresponding to (oiGH) constitutes the ith 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 Rrn
In the interest of completeness, the result for the most general case will
be given. Let RX, SW, and Tz be three R-spaces with respective bases
A =_ (0 - o,.ox}
E - O B i~ * 3 W }
and
C - 7,* o- z)
The linear transformations G and H are defined by
w
i^G = E aiv (i = 1,2,..,x),
v=i
ASD TR 61-483 29

and
z
ikH= Ebiuyu(i =,2,...,w).
u=l
Therefore,
/w w w z
(CiGH) = Z.airv)H = Zaiv(SvH) Zaiv Zbvuu
v =l v/= v=l l
z w w w w
Z aivbvuu = aikbkl aikbk2.. 7 aikbkz
u=l v=l k=l k=l k=l
The above linear form when expressed with restricted coefficients constitutes
the ith row of the product matrix.
If A = |laijII, B = llbijll, and C = llcij U are n x n matrices relative to the
natural basis, the product (AB)C is developed in the following manner:
AB = E = Ileij 1 relative to the natural basis and the ith row of E is obtained from the linear form
/n n n
(7 aikbkl, Zk aikZbk,* klaikbkn\k=l k=l k=l
Since this linear form is to be reduced relative to the natural basis, the ith
row of E is
aikbk )(ml) (aikbk2 (m2). * aikbkn(mn)I
The product (AB)C = F = Ilfijil is similarly developed and the ith row of F is
n n N
L. eaikck (ml1)..., Zeikckn (mn
=-1 1 /
- J K zairbb (mkicki'>(m1)...
<[k~l [rairbrk) (mk) Ck& (mn) ( 2-4h)
Consideration of the product BC gives rise to the following linear form with
ASD TR 61-483 30

restricted coefficients.
n
k(lbikcki (ml), ~ ~, bikCkn) (m
\k=l / \^k=l /
Also
A(BC) = D = Ildij{l
where the ith row of D is
n n n n
ai rkk (,, air b rkCk (m) airkkn 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.
ASD TR 61-483 31

CHAPTER III
CABRY FJUNCTIONS TN RESIDUE NUMBER SYSTEM AND RELATED NUMBER SYSTEMS
3.1 THE CARRY ALGORITHI
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 (con...C On is given. The algorithm involves the notion of carries from some components of the representations into
other components of the representationo
If the linear form to be reduced is all + a2l2 +.o + ancn, one proceeds
by expressing anta as bllt + b20. + o b + bni where 0< bi < mi and making
the substitution to obtain (a+bl)<l +.. + bnOn. The process is then repeated focusing attention on (bn l+an )l )l_1 and continued until one has the
desired result.
Dividing aj by m., one obtains a. = mjq + r, 0 r < mj. Any multiple
of mjCj will yield a vector in the subspace (xl,X2,oo., xjl,.o,). Since'he set of vectors (ai) is a basis, the set ([l,...,cj) is a basis of the mentioned subspace by Theorem XII. Thus the term mjq will not affect the multiplier of Oj in the reduced expression; that coefficient must be r. The product
mjaj can be expressed as a linear combination of al through aj_l and qrr,.ja
is merely q times each term of that combination. The linear combination for
(qmj)caj is added to the original linear combination and ajcOj is replaced by
ASD TR 61-483 33

rCj. Thus one applies the above procedure to first an, then to the new coefficient of cn!1, and so on until the desired result if obtained.
The Carry Algorithmn may be stated as follows:
1. Express mjaj as a linear combination of l,. *e,%aj-l denoted b.j a +
bj2 2 +... + b.. j-aj for j = 2,3,.o,n. Beginning with j = n
and a' = an.
2 Divide aj by mj and obtain
aJ = qjmj + rj with 0 rj < mj.
3. Replace a j with r ja and
a! with (a!+qibji) for i = 1,2,...,j-l.
1 1 13
4. Repeat steps 2 and 3 substituting j-l for j. Stop after executing
steps 2 and 3 with j = 1.
Theorem XIX. 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 congruences indicated in the proof of' Theorem
XI.
Consider cn - an mod mn with 0 < cn < mn. By the uniqueness of division
rn is the residue of an modulo mn and rn = cn.
Assume that rj = cj for j = m,m+l,...,n. The congruence which then must
be satisfied is
km-l,m-lCml + km,m-lCm +... + kn,m-lcn
-= kmlm.laml + km,m.lam +. + kn,m-l a mod mml (31)
The quantity aj which enters the division in step 2 of the Carry Algorithm is
ASD TR 61-483 34

a. = a. +qnb + b + +.+ +..+q 1
j j n nj qnl- n-lj "J+l j+ l, j
thus
an = an
a 1 = an1 + qnbnnan-2 = n-2 + qnn,n-2 + qn-lb n-ln-l, n-2
I-l am-i 1 + nml + + mbmm-l
In expressing
pjaj = bJ1EK + b j22 +.o + bjjl-j-l,
one solved the congruences
kj_-ljlbjjl - mjkj j_lmd mj_
kj-2,jbj, 2 + kj_1j-2btjj -1 mjkj _j2mod mj-2
km-l,m-lbj,m1 + km-2,m-lbj,m-2 +' + kj-l,m-lb,n-1
mjkj,m_lmod mml
kllbjl + k21bj2 +... + kjl-,l j 1 mjkjmod i.
Using the induction assumption, relation (3-1) can be written
km-l,m-lcm-l + kmm-lrm + kn,m-ln
= km_-lm-lm-l + km,m_lam + e.. + kn,m_lanmod m_-l
which can be manipulated to yield
km-lm-lm-l + kmm_lrm +. + knl,mlrn_l
(3-2)
km-lm-lam-l + km,m-lam +... + kn,ml(an - rn) mod mm-lo
Since an = an,an - rn = qnmn, (3-2) becomes
ASD TR 61-483 35

km-l,mr-lCm-l + km-lm,.rr + k^ n-l,m-lrn-l
- lm-ll-(aml + qnbn,m-l) + k,m-l(am + qrbnm)
+..o + krl,i^-l(an-1 + qnb in-l)mod mm_ (3)
upon the substitution
qn(kml,mlbnm-l + m,mlbnm +.. + kn-l,m-l n,bn-1)
qnmknknm- (mod mmr1)~
Once again we transpose (add the inverse) kn-lmlrn-l and recognize that
an-l + nbnnl - rn1 = an_ - rn-l = qn-lmn-l
Making the following substitution~
qn- l(ml,m-lb n- lm-1 + &m,m-lbn-l,m +.. + kn-l,m-lbn-l,n-2
- qn-lmnlknl -l lmod mm-1.l
we obtain
km_-lmCml + kmm-lrm +.. + kn-2,mlrn_2
km 1 ml(am_1 + qnbnm + q1n bn lm-l)
= lnm-l(m-l ) ^n,m-l Yn-ln-l,m-l)
+ k rim-(am + qb + nln, m + n-ln-,m) + *.
+ kn-2,m-l(an-2 + nn,n- + n-lbn-l,n-2)mod mm-l.
Again we identify the last quantity in parenthesis as a_2, transpose and substitute. By repeating these manipulations, one finally obtains
kmlm-lCm-l km-l,m-l(m-l + L nbnm-1 + n'm-l )+ mbm,m-l)m~d mm-l
or
Cml = amlmOd m
which yields the desired result cm 1 = rm-1.
By 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
ASD TR 61-483 36

XI. 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 representations X and Y of positive integers, how does one obtain the remainder X - Y? This question will now be considered in some detail.
Let X be represented by (xi,X2,o^..,xn)0 and Y by (yl,Y2,..,yn)ao Initially one forms (xl-y1,x2-y2,. o.,Xn-Yn) This last expression denotes
ASD TR 61-483 37

(xl-yli)a, + (x2-Y2)a2 +.. +- (xn-yI)%l. Corsider the jth component of an expression to be negative. Since
mjj = bj1a + bja2a +.. + bj, j- l
one may add to the above ex-pressio zero in the form
dj [mj {j - (bj aO + b.,a + bj, jjl)] = 0
where dj is the smallest multiple of mj which is larger than the magnitude of
the jth component~ This addition yields
(Xi - y1 - dnbnl, x2 -2 - dnbr Xn- -l Y- 2 - dnbn nXn - Yn + dnmn)
for j = n,
(x - Y dnb - dnl- lbnl,l 2 - Y2 - nb - dlbnl,,'d'Xni - Yn-1 - dnbnl dn lrlxrl - Yn+ dnr1)
for j = n-l, and finally
(X - Y - db- ddlb _n- -. - d2b21 + dr1m,
X2 - Y2 - dnbn - dlbn-l,2 - - d3b32 + d2m2,''Xn-l1 Yn-l - dnbn,d l + dn-lmn-lnXn - Yn + dnran) 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)o 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 complements of the elements of the
ASD TR 61-483 38

first group. f M is enx^, M/2 is self complement.
To find the complement of a given representation Z, one generates the
remainder (O-Z) as indicated above.
The procedure for periorming subtraction and finding complements indicated
above suggests the statement of a Borrow Algorithm as follows:
1. Express mjaj as a linear combination of c29.o., j_ denoted
bji l + bj-22 + o* + bj j _lj -1 for j = 2,3,..,n. Beginning with
j = n and a! = al.
2. Perform steps 3 and 4 if a. < 0, otherwise skip to step 5.
3. Determine d. such that dj is the smallest multiple of mj which is
larger than a Io
Add to the liear rm the epression
4. Add to the linear form the expression
(-djbj, - djb j2..,. db j~ iT - + admj,0,. 0)
5. Repeat steps 2, 3, and 4 substituting -1 for j. Stop after executing
steps 2, 3, and 4 for j - 1L
Example: With the basis < (1 00,0), (,2,0,0), (1,1,2,0), (1,1,1,1) > where
the moduli are m1 = 2, rr_ = 3, m3 = 5 and rra -', the carry functions are
3o2 = %si, 503 = a2, and 7`4 = a3. An example of subtraction using the Borrow
Algorithm directly will be given as well as subtraction by using the complement of the subtrahend.
Subtraction using the borrow algorithm1, 2, 2, 1) -> 190
( 0, 2, 4, 6) > -104
( 1, 0,-2,-)
+ (., 0-i, 7)
1, 0,-3, 2)
+ ( 0,-, 5, 0)
( 11-i. 2, 2)
+ (-1, 5, 0,^ 0 )
( 0, 2, 2, 2)) - 86
ASD TR 61-483 39

Complement of (0,2,4,6):
(,-24,-6)
+ ( 0, o,-1, 7)
+ ( 01, 5, O)
( 0,-3, 0, 1)
+ (-1,-3, O, 0)
(-1, 0, 0, 1)
+ ( 2, 0, 0, 0)
( 10, 0, 1)
Subtraction utilizing the complement:
( 1, 2, 2, 1) — > 190
+ ( 1, 0o, 0 1) 4-> -le
( 0, 2, 2, 2) 0- 86
3.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
< al,20...,oG >. It is desired to find coordinates (Yy2, -,Y n), ) relative
to the basis < i, 2,.,on >. Each vector C1 of the old basis can be expressed
as a linear combination of the vectors of the new basis in the form
czi - qail + q1232 +.. + +qin n- (-4)
However, since both bases are triangular, qik = 0 for k > i. The vector X with
ASD TR 61-483 40

coordinates (xl,x2,...,x ) relative to the basis
< Cl.. e',a' > is xi + X2 + x2C + x. + Xnn
Substituting from above, one obtains for X
xlqll1~ + x2[q21Pi + q2232] +'~- + xn iir.l + - + qnn3n]
which can be written
(xlq i xq2 + Xq2i + + Xnqni)3i
+ (X2q22 + o + Xnqn2)P2 + o. + Xnqnnn. (3-)
The carry algorithm is then applied to linear form (3-5) and the result is
X = YlT1 + Y252 +... + YnLnThe Yi are the coordinates of X relative to the basis < 1,2Sn, —.,nn >If the zero coefficients are retained in expression (3-4), expression
(3-5) becomes
(Xlqll + X2q2l + * + Xnqnl) 1 + (Xlq12 + X2q22 + —. + xnqn)P2
+... + (xlqin + x2q2n +.. + Xnqnn)n.This expression is an interpretation of
(Xlqll + x2q2l +. + Xnqni),(xlql2 + x2q22 +.. + Xnqn2),
*-. + (xiqln + -. + Xnqnn)
which is the matrix product
[XIx2.. ~xnJ] q-.iiq.2 ~. q inl
q( 1q22a q2n = [Y1,Y2, ~ Yn
qniqn2... qnndenoted X'Q = Y.
The above procedure constitutes an effective procedure for executing
ASD TR 61-483 41

change of basis.
The vectors oi of the new basis can be written as linear combinations of
the old vectors,
n
= PijKj (3-6)
j=l
Thus for a change of basis from < L., oo > to < Ol,..,0 >, the appropriate
matrix product is Y^P = X where P = 1Pij ll
Substituting equation (3-6) into equation (3-4) one obtains
n n n
i = iljlPij + qi2 2P2jj + p j + qinZlPnjaj
-=1 l j=jL J==
n n n
qip I. + = + + E q inPnjj
j=l j= l j =
n n
k=l j
One may interchange summations to obtain
n n
T 7,IikPkSqj
ji =- k=lkPk qJ
n n n
= kB'qikPkjcl + ^qikPk2e2 + ^i+ qikPknOn (3-7)
Equation (3-7) written in n-tuple form with restricted coefficients is the ith
row of the matrix product QP. Since the ai constitute a basis, the reduced form
of equation (3-7) must be 1i = 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.
ASD TR 61-483 42

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 the 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 (y1,y2,. o-yn) and multiplier
(XlX2... o,Xn)
lo Write the multiplicand (yiy2,.o.,yn) as the vector sum yll + y2s2 +... + YnanBeginning with j = n
2. Write the partial multiplier (0,...,,xj,0, o.,0) as the vector xjcaj.
3. Multiply, component by component, xj0j ~ Yiai) i = 0,...,n.
4. Express the vector xjoj ~ yiai as the linear combination Ziel +...
+ Zia,, i = 0,..o,n.
5. Sum the linear forms produced in Step 4 to determine the jth partial
sum~
6. Reduce j by one and repeat Steps 2 through 5. Terminate the procedure
after doing the above steps with j = lo
Example: Consider the multiplication
(Y1,Y2. -.,y4)M ~ (xlx2,.., ^X4)M
in the mixed base number system where mi = 2, m2 = 3~ m3 = 5, m4 = 7. Here
ASD TR 61-483 43

the basis is < (1,0,0,0), (1,2,0,0), (1,1,2,0), (1,1,1,1) >.
The following steps are numbered to correspond to the statement of the
Multiplication Algorithm.
1. (Yl,0,0,O) + (Y2.2y2,0,0) + (Y3,y3,2y3,0) + (Y4,Y4,Y4,Y4)
20 (X4 x4,x4,4 )
3^ (Ylx40,O,0O)
(y2x4,2y2,x, O, 0)
(y3X4.y3X4,2y x4,0)
(74X4.7Y4x4.,Y4X4 Y 4x4 )
4. (Ylx4,0,0,0) = (y.x4,0,0,0)M
(y2x4,2y2x4, 0,0) = (O,y2x40,,o)M
(y3x4,y3x4,2y3X4,0) = (0,0,y3x4,0)M
(y4x4,y4x4,4,y4.x4,y44 ) = (O,O,,y4x4)M
5. (Y1,Y2,Y3,Y4)M' (00,0,OX4)M = (x4.Y1.x4y2, 4 Y3. X4Y 4)M
2. (X3, x3,2X3 0)
3- (ylX3s0,0,0) = A
(y2x3,2y2x3,0,0) = B
(Y3x3Y3x3 2 (2y3X 3), 0) C
(y4x3,y4x3,2y4x3,0) = D
4. A = (ylx3,.,O,O)M
B = (O,y2x3,0,O)M
C = (0,0,2y3x3,o)M + (O,x3sy30,,)M
since (0,0,2x3y3, )M + (O xsys30,0)M
= (2X3y3.2x3y3,4x3y3,0) + (X37y32x3y3,0,0)
ASD TR 61-483 44

= (y33,y3x,2 (2y3x3), O)
D = (O,o,x3y4,o)M5. (Y1,Y2,Y3,Y4)M (OO,x3s0)M
= (y1x3,y2x3 + Y3 + 3X34y + y40)M
2. (x2,2x2,0,0)
3. (x2yl,O,O,O) = A'
(x2y2,4x2y2, O O) = BE
(X2Y3,2x2y3,O,O) = C'
(x2x4,2x2y4,O,0) = D'
4. A' = (y7x2,0,0O,)M
B' = 2(0,x2y2,0,O)M + (x2y2,0,0,0)M
for (x2y2,4x2y2, 00 )M
(x2y2,2x229,OO) + (0,2x2Y2,0,0)
(x2y2,2x2y2,O,0) + ( x2y2,2x2y2,O,O )
+ (x2y20,0O.0)
C' = (O,x2Y3s,0,)M
D' = (O,x2y4,0,0)M
5. (Y1,Y2,Y3,Y4)M' (~,x2,o~'o)
= (x2yl + x2y2,2x2y2 + x2y2 + x2y4,, 0)M
2. (xl,O,O,O)
3. (xlyl,O,o,O)
(XlY20, O,O,)
(xiy3, 0,0o)
(xiy4,0,0,0)
ASD TR 61-483 45

5. (Y123,Y3,Y4)M' (xl,0OO)M = (xlyl 2 + + xly4,0,,0,)M
The results of the Multiplication Algorithm in this example are the following for rules for the formation of partial products:
(Y1,Y2,Y3,Y4)M' (x,0,,0)M = (xy X2 + + x x + xly4,0, 0,0)M
*(Y +2Y32 xy- * y20xti3)xy = (+ x2YY + x24,0,3 0)M
(Y Y2,Y3Y4 )M - (OO,3xa,)M - (X3syl3xsy2 + xsy3,2x3ys + X3Y4,0)M
(Y1,y2,Ys,7y4)M' (0,0~0x4 )M - (x4yi,x4y2,x4y3,x4y4)M
To multiply two mixed base elements (yl2y2,YsY4)M and (xlx29x3sx4)M one proceeds as follows:
1. Form the above partial products.
2. Reduce each partial product by employing the Carry Algorithm.
3. 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 ~ (0o00,6)M = (6,12,18,24) = (1,1,1,3)M mod M
(i,2,3,4)M ~ (0,0,4,0)M = (4,28,40,0) = (l,l,0,0)M mod M
(1,2,3^4)M (0,2,0,0)M = (6,22,0,0) = (1,1,,0,)M mod M.
Therefore,
(1,2,3,4)M (0o,2,46)M (0,0,1,3)M mod M
(0,2,4,6)M (- 104
and
(1,2,3,4)M -> 200
104 ~ 200 = 20800 = 10 mod M
(0,0,1,5))M (> 10
ASD TR 61-483 46

Let us look again atl the question of associativity of matrix multiplicationo Consider the three matrices A = Ilaij l, B = jbi jl., and C = lci. jlo Let
the basis of the vector spaces by U, < c i2,,. Co,n >; V, < P31,2 *o, r >;
W. 7>,72.',yn >7 and Z. < 5152.o.5n > TA is a transformation from
U + V, TB: V - W9 and TcO W + Z.
The ith row of the product A B is
(k=1 k=1 k=l
kkn n n
reduced relative to the basis < y1'y7n >. Designating the reduced form obtained (ei1e i2,...e in), we obtain
Define n -
Z aikbkn
k=l
in = mn
D naikbkn-l + ingrn-
=mnl
~n
laikbkn-l + fingn,n-1
mn-l
fi,n-1 = m_l
lZ aikbki + fg + fin-lg -1 + fi,2g2,
ei, - mwhe re
*i =.Y + gj2Y +.o. + g.j_1T
"mj - gjll j2 j J-1 j -1
ASD TR 61-483 47

The ith row of the product (A-B)C is
1/ "1)n n
( eikCk,, ei ck2 Z ~ e ikCkn
~_-1=I k=l k=l
reduced relative to the basis < y 7,. s, nr >. This gives rise to the reduced from
(hi1 hii~.. i hin)
where
hin = ~;
kl, eikCkn
hin
Sin =- r
n
h Zekckn:L + ~irrnJnl
hi,n-1 =
^iLkei nl c Rin'r, " Ri,n-lrn-l,l + o + fi2r2i 1
lm mm j
whe re
mi. I rj l + +rSimilarly the ith row of the product B$.C is
and n n
Zebikk n- i + kin nn- kckn
k=l k-l k=l
Bi n-1 - mn-1
Eeikcki + Binrnj, + Oinnlrn-lll +. i. + 121ir
reduced relative to the basis K s..e >. The reduced form is
ASD TR 61-483 48

( sin - I mwere
- bikCkn
kbi
tin =
n n
i k7i ikckn-l + tinrn n-l
Si,n-l =. mi
Tkbikck n-l + tznrn n-l
ti,n-l mL n
rn
klbikCkn + tinr nl + tin-lrn-ll +'' ~ + ti2r21 L
Oil
The ith row of A(BC) is
n n
n
lk=laikkl, klani kSk2i,n n, k+ ikSk21
whe re
Za ikskn
Vin= n n n
rn
k=l iksk n-l + Uinrn, nVi,n-l = n
ASD TR 61-483 49

n
hiaikskn- + Uinrn,n-l
uin-1 =
r/ 1
_______"___________ ____________________________________t
Selecting particular comrponents fcr comparison
/fn
hin m dk )
+ La, b +mod. c'9e i nkn+ l mod mir ll - n-l,n
N *1
aikbk....i -ingn- n-.-1' i+l
+ f 1ia2g921 mod ml ci rnm mod mn
or
hin " a/b, ro da m mod mn
+ ni ZL f. l g mio-d m~ m c mod nm
+Removing one term and changing ndie one finds
nr I1 n
n-+! M
r ~ ^ijg jr^ mod 1Y Crnmod. rn
ASD TR 61-483 50

k- aikbkncnnOd mnn
k=l
n-1 n n
+ l LE aikbkr + fijgjr 1mod mr' Crnmod mn.
r=l k=l j=r
Also
n/.
Vin =,aikSkn, od mn
~L i
Sil z bikCknmod mn + ai2 k b2kcknmod M
/ n
+... 2 ain ( bnkCkmod mod mn
or
n n-1 n
Vin = Zairbrncnnmod mn + Z a Zlairbrkcknmod mnv r=l k=l r=l
Changing indices for clarity, one obtains
n n-1 n
Vin = Z aikbknnnmod mIn + Z Z aikbkrCrnmod mn
k=l r=l k=l
Since the first terms of hin and Vin are the same, it is sufficient to
look at
n n 1
airbrk + figk mod mk (3-10)
r=~ J ~J i
and
n
airbrk mod mn. (3-11)
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 mn. Since the mj are relatively
prime, one is led to conclude that the ith row of (AB)C is not equal in general to the corresponding row of A(BC). This was shown independent of the
ASD TR 61-483 51

selection of the basis for the various image spaces involved. Therefore, no
selection of basis will guarantee associativity of matrix multiplication.
ASD TR 61-483 52

CHAPTER IV
TilE MIXED BASE JTUMBER SYSTEM
4.1 GENERAL CHARACTERISTICS
In order to remove ambigui-ty the elements of a finite number system are
partitioned into two classes, those representations defined as positive and
those defined as negativeo Normlal convention assigns a magnitude interpretation to positive elements and a complement interpretation to the negative elements. For sign determination and magnitude comparison, it is necessary to
identify the classification of each and every element. The structure of the
residue number system makes immediate classification difficult. The structure
of the mixed base system facilitates immediate classification. In addition,
the mixed base system allows one to handle the problems of additive and multiplicative overflow, and divisiono 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
manne r:
1. Order the primes mz,m2,.., mno
2. Set na equal to the vector consisting of all l's. Beginning
with j = n.
3. Obtain.j_- = mjCj
4. Repeat step 3 with j replaced by j-l. Stop after performing 3
with j = 1.
ASD TR 61-483 53

Theorem XX. The vectors (OC,..,Cn) produced by the above scheme constitute a basis.
in order *to pro-Te the theorem, Le-:ma 1 will be proven.
Lemria 1i If (ab) = 1, then (a mccl bb) = 1.
Proof: a bg + r, 0 r < b and.. by definition r is the residue of a mod b
a m r mod b
or
a (a mod b) mod b.
Since x = y mod z > (x,z) - (yz), (a mod b,b) + (a,b). The conclusion follows.
Proof of Theorem XX: Qn is a representation of the integer 1. The vector
n
ai is the residue representation of A = 7 mi. Each mi for i < is relatively prime to Ai. Thus it is seen that
ki = 0 for i >
and (k2imi) = 1 for i >~. By Theorem XII the set < al,a2,..,a. > is a
basis of Rn.
Theorem XXI. An elemert (xlx2. o., Xn) of the mixed base number system
is a representation of an integer X in the range C X ( ) if and
only if xi = C.
Proof: The element X (XsxX2, o,x n) is a coding of the integer
xi-+:x -+ + Xs M +. oo + x modulo M. (-1
mi M1m2 m1lm2r3 n
Consider the quantity
M M M
xl + x2 mm2 + x mim +m + X.n (4-2)
ASD TR 61-483 54

The largest value expression (4-2) can assume is attained when
X = ml - o
Upon substitution one obtains
(ml 1 + (m - 1) + (m3 - i) M + + m 1)
Ml IrI1m2 mim2m3
This is then rewritten as
M +
(mn - 1) + mn(mnl - 1) + _l) + m 1 1) + o. + m- -2(m2 - 1) + m
remembering the scheme for generating the base vectors. All but the following
terms add out:
-1 + M+ M + M - 1.
mi ml
This means that expression (4-2) is equivalent to expression (4-1) Consider
next the quantity:
(m2 - 1) M + ( I + (m - 1)
ilmn2 mimmn 3
which is equal to
M
(mn - 1) + mn(mnl - 1) + rmnm-1(mn-2 - 1) + + (m2 - 1)m
The above expression reduces to
M
-1 + -.
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 mi is even, i.e.,
ASD TR 61-483 55

xi < m1/2 0 < X < M/2.
When applying the Carry Algorit-hm., to the reduction of the expression
a1e, + a2+g + + an0n
(Cei is a base vector of the mixed base system) one must increase by one aj for
every multiple of mj+1 contained in a +. (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 nth 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-l units of time may be required to propagate carries Borrowing is accomplished by reducing a' by 1
and increasing a' by m i Again up to n-l units of time may be required to
perform subtraction or complementationo
Multiplication of two elements of the mixed base system was discussed and
an example given in Chapter III.
Theorem XXII. 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 jth component of the unreduced sum occurs when the jth components of the addend and the augend are maximum, i.e., equal to mj-l. The
maximum sum will be m -2.
J
Let j = n. The maximum unreduced nth component will be 2mn-2; therefore,
the carry can only be zero or one. Consider j = n-i. The component 2mn-1-2
will produce a carry. If a carry was generated by the nth position mnl-2 +
lmn_l; therefore, no carry is both propagated and generated.
Assume the results true for j = m. In this case 2m l-2 will generate a
ASD TR 61-483 56

carry of one, and 2m _-2 + 1 will also give rise to a carry of oneo
4.2 OVERFLOW
A problem of the residue number system, which can be solved with the mixed
base system is cverflowo in a mixed base number system where ml = 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 XXllI. If the sum of two positive elements of the mixed base system is (zl,..,zn) additive overflow occurs if and only if zi = 1.
Proof: (zlz2,....zn) represents the integer
M M
Z2 + + zo + o + Zmd M (4-3)
Z17 + Z2 m3
and overflow occurs when
Z1J + Z2 + * + zn
2 2m2 2
This will clearly be the case if zl = lo
The largest value that 22- +. + z can attain has been shown to be
2m2 n
2 - 1. The largest sum possible is 2 - 1 = M-2 < M. Thus expression (4-3)
becomes Zl + z.. + Zn and the other conclusion follows.
2 2m2
To insure that multiplicative overflow will not occur, conditions will be
ASD TR 61-483 57

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 will also be treated.
Consider (y1,Y2..o,Yn)' (xi,O,...,O). Since (x1,O,...,O) M xl, overflow will occur unless y y= -..o =Yn = 0.
Consider next (Y1,Y27,.,'Yn)' (Ox2,O,..,O) and note that (O,x2,O,..,O)
M
x2m2. Therefore, the condition which is necessary and sufficient for the
absence of multiplicative overflow in this partial product is:
Y1 = Y = 2Y1 = 0 arnd x2 ~ Yn < m2.
M
Since (OO,x3,O,o...,O) represents X3 M and (YzY2,-.-Yn) represents
Y = Yn + Yn lmn + y m m1 +..+ yM -, a necessary and sufficient condition
Y = Yn + Ynlmn + Yn_2mnmn- ml
to prevent overflow is
X3 Y< (4-4)
2mm3
or
X3 Y < m2m3
Thus it is seen that condition (4-4) becomes
X3(yn + Yn lmn) < m2m3 (4-5)
and
Y1 = Y2 =. Yn-2 = 0
Since Yn < mr we may substitute for expression (4-5)
x3mn(ynl1 + 1) < m2m3
to obtain a sufficient condition.
Consider now the general partial product (Y1,Y2,..,Y n)'
(0,...,O,xj,O,..,O). In this case (0,..o,O,xjO,...,O) represents xj m.
ASD TR 61-483 2m..
ASD TR 61-483 ^8

To guarantee that no overflow will occur we must satisfy the inequality
xjY < m2...mj or
x( Yn + Yn -lmn + * + Yn-(j -2)1.' mn-(j )
(4-6)
+ Yn-j+lmnmn-l mn-j-2 + ~ ~ + Yi ) < m2m3m3
The condition becomes
Yn-j+l = Yn-j= yj = 0
and
Xj(Yn + Yn-lmn + + Yn-(j-2)mn —mn-(j-3)) < m2m3mj (4-7)
This constitutes a necessary and sufficient condition that this partial product does not produce an overflowo Again there are simpler inequalities the
validity of which will imply the validity of (4-7). These inequalities are
Xj[(Yn-l + l)mn +.. + Yn-(j-cO)mn..mn-(j-3)] < m2m3''m-r
Xj[(yn-2 + l)rnmnl + - + Yn-(j-2)mn.mn-i(j-3)] < m2m3.. mj
Xj[(Yn-(j-2) + l)mn...mn_(j3)] < Mm32..mj.
The sufficiency of the above inequalities stems from Theorem XXIV.
Theorem XXIV. If xi < mi, then
xl+ + x32m 1 +.mlm2 + x, + _lmlm. omk_2 < mlm2.- omkl.,-lJ" - yLk-2
Proof: The maximum value that
xl + x2m1+ x3m2... + X3 _lmlm2.*.mk2
ASD TR 61-483 59

can attain is
(ml - 1) + (m - )m + ( m2 - l)mlm + )m..l + (mk-1 - l)mlm2...mk_2
= mlm.. mk-2m - 1 < mrlm2..m- k
k-I1
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 for
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,
ms = 5, and m4 = 7o
95 4 (0,2,3,4)
14 -> (0,0,2,0)
Step 1: Determine first divisor,0,0,2,0 j,2,,4
It is seen that it is necessary for a = 0 to avoid overflow.
Step 2: Determine second divisor
0,3
0,0,2,0 0,2,3,4
ASD TR 61-483 60

Again to avoid overflow = O0
Step 3: Determine third divisor
0 0 2:~9'n y4,0,y0
00,92,0 0,2,34
From overflow considerations it is seen that y = 1 is satisfactory.
0, 0,1
0 0,2,0 0,3 2
0,2,4,0
it is seen that y = 1 is too large; therefore, 7 = 0.
Step 4o Determine fourth divisor
0,0,0)
0,0,2,0 0,2935 4
From reference to overflow rules and multiplication the estimate is ~ = 6.
0,0,0,6
0,0,2,0 /0,2532 4
0,22,2,0
0,0,1,4
The division is completed giving 95 = 6 ~ 14 L l.
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 comrponent in the most significant non-zero position (kth) of the dividend. (The kth component must be less than or equal to the kth component of the
dividend. )
3. Subtract the partial product from the dividend and if necessary
ASD TR 61-483 61

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 = (alo i^,.^,oin) and base
moduli mlIm2-. o.mrnl the problem is to express the integer s in terms of
coordinates relative to the basis {lj2,.). on,3 n+l,', n+m] = B and base
moduli m,m2,.,m n'mn+l.o.,m. The m. are pairwise relatively prime.
n+m
Since one can represent s as a vector relative to the base moduli
n
ml,m2,...,mr, s is less than 7=1 mi. Therefore, if s is expressed in the
mixed base system relative to the moduli m n+l mn+2,..,mn+m,ml,m2,. rmn,
the coordinates with weights greater than or equal to 4 mi must be zeros.
i=l'
The weights of the last n components of the mixed system will be in reverse
order, lmn,mnmn_l,n..,mnnlo.. m2. These weights are the same as the weights
of the components in the mixed base system relative to the primes ml,m2,...mn
Therefore, digit fill-in is accomplished as follows:
i. 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.
ASD TR 61-483 62

C HAPIR V
OTHER NKRV'ER;~.T^.._S RELATED TO THE RESiDUE NUMBER SYSTEM.1 PARTiTITONTING PROPERTI-ES
In Chapter IV i't vwas noted that the mixed. base number system. representations corresponding to conseecutive integers are partitioned by the first coordinate. It is this property which permits a rapid solution to the sign detection problem.o A questi;r. arises whether other number systems exist which
possess the desirable parzaltitioning while having simpler rules of arithmetic
manipulation. to will be shown that the only non-redundant number system to
achieve a partiti oning of elemerents representing consecutive integers is the
mixed base systemr
Lemma 2~ For any integer k within the range 1 < k < p, there exists an integer & such that
p < k < 2p wThere & < p and p > 2.
Proof: It is evident that k cannot lie in the range.' k< p9
for
p > 2, p-2 > 0
2p-< > p
2(p-1) > p;
therefore,
P <2.
p-l
ASD TR 61 -483 63

Thus there exists an integer I such that
P P
< k < P-e with p > I
and one concludes p I.k < p. 2p.
Theorem XXV. If the base moduli are ordered mlm2,..o mn only the mixed
base number system gives a partitioning of the elements into those elements
which represent integers'in the range less than (C+l)M but greater than or
equal to c M _ where c is the first coordinate of the element.
ml
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 < 1,P32...,Pn >. It is
assumed that this number system achieves the desired partitioning. Here 31
corresponds to B1;P2 to B2 etc, An element of this number system Y = (Yi,Y2,...,yn) represents the integer.
yIBi + Y2B2 +.X. + ynBnmod M.
For the set < 31.-. Sn > to be a basis it must be triangular; therefore, one
may state
Bn kn
Bn-l = knlmn
n
Bj = kj i- mi. n
B,= kl i=2 mi
whe re
J
o < kj <X mi
ASD TR 61-483 64

Consider yl = c and yi = 0 for i / 1. The expression ylB1 + y2B2 +... nBn
M
kl = 1. One conrdition which must be satisfied is y1 = 0 -= Y < m. This requiremernt becomes
Y2B2 + y3B3 + o + yrBn z rod M ( -)
where z < M for all Y27,Ys3. oYn
Consider first the case
Y' O0 Y3 =.Y = Yn = O
We have
y2B2 Y2k M
If there is an integer Q in the range 0 < K < m2 that
M M
< k <M (5-2)
condition (5-1) is violated. Expression (5-2) may be written
m2 < Kk2 < mini (5-3)
By Lemma 2, it is seen that for k2 > I, we can find an integer in the range
0 < K < m such that m2 2k2K < 2m2. Since mi >2, inequality (5-3) is satisfied.
Therefore, k2 = 1.
Assume that we have shown k = 1 for i = 1,2,...,m. Let yi = mi -1
for i = l,2j...,mym+l 0, and Ym+2 = Ym+ = + = 0. Consider
(^, )-.> M (m - ) - k) + y + m+lkm+
mim) mzmams m mm m oi ~in.mim2... m m + ml mm
or
(m2 - l)m3s..mn + (m3 - l)4...mn +.. + (mm - l)mm+l..mn + Ym+lkm+lmm+2. m n
which yields
ASD TR 61-483 65

(m2m3S..mn) - (mm+1..mn) + Ym+lk m+m+2. m
But m= m2m3. mn.
mi
Thus the sum s is
M
s m= m +- Ylkm+lmm+2...m
mi ml +l m2n +' n
If
M s <M (5-4)
mi
condition (5-1) will be compromised. Expression (5-4) becomes
mm+l mn < Ym+lkm+lmm+2~. mn < (ml - 1) M m+l mn
which upon substitution for M yields
mm+l O - mn < Ym+lkm+lmm+2 ~~ mn < [m2... m(ml - 1) + l]mm+l. o mn
Removing the common factor in the above expression one obtains
mm+l < Ym+lkm+l < [m2-...- (ml - 1) + 1]mm+. (5-5)
If mm+l < km+l < (ml-l)m2...mm+l, (5-5) is satisfied by Ym+l = 1. If
km+l < mm+l and km+l > 1, Lemma 2 guarantees that there exists a Ym+l such
that
m+l1 < Ym+lkm+l < 2mm+1
but since
2 < [m2.. mm(mL - 1) + 1].
It is necessary that km+ = 1 or that
(ml - l)m2o..nm+l < km+ < mm2.. mm+l.
To see that km+l cannot be in the range
(mi - l)m2..r m+1 < ki+1 < mlm...mm-,
consider Ym+l = 1 and Yi = 0 for i f m + 1. Then
ASD TR 61-483 66

s - Bm+lkm+lmm+2. omn
and
M
-_< (ml - l)me...m. +2omn < s < mmmi. ommn+R. om m = M.
Again we have satisfied condition (5-4); it is necessary that m+1 = 1
Therefore, the only number system which effects the partition described
is that system having ki = I for i = 1.. o,n. This system is the mixed base
number system.
Theorem XXVI. If the base moduli are ordered ml,9m,..,lmn, there is only
one number system with the property that the first coordinate partitions elements which represent consecutive integers into mi classes. That number system
is the mixed base number system.
Proof: Theorem XXV shows that there exists but one number system which partitions the elements into those elements which represent integers in the range
less than (c + 1) M but greater than or equal to cM, where c is the first
ml
coordinate of the elemento 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
t3,%.o,,.~ An element of the rumber system represents the integer
Y13 + y2B2 +.o + YnBrl mod M (5-6)
Again we may state
Bn - kn
BnA1 = kn-lmn
ASD TR 61-483 67

n
B' = k. C mi
i=j+l
B! = ki, mi
i=2
where 0 < kj < 7mi. The range imposed on kl is 0 < kl < mi. Thus we have
B' = kl M/ml
and expression (5-6) becomes
M
y1kl 1 mod M when yl 7 0, Y2... =n = 0
It will now be shown that there exists an integer c in the range 0 c < ml
such that
c m ylkl M mod M < (c + 1) M (-7)
im- - mi mi
cannot be satisfied for 0 < kl < ml, 0 < yl < mi, and yl ~ c. Take c = 0.
Expression (5-7) becomes
0 < yikiM mod M -. (5-8)
0~ Ylk ml ml (5-8)
Condition (5-8) will be satisfied only if
Ylkl - 0 mod mi.
Since yi t 0, (5-9) requires that k1 = 0. This is the desired contradiction
which completes the proof.
Corollary 1: If the base moduli are ordered ml = 2, m2, m3,...,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 integers
less than M, and the representations of integers greater than or equal to -
ASD TR 61-483 68

Proof: This corollary follows from Theorem X.XVI with mi = 2.
One now asks whether a nimber system with, base moduli mTr,m2,. o,mr exists
which partitions elements -which represent consecutive integers into mj classes
with the first coordinate where j. I?
The number of elements having the same jth coordinate in any system having
mj as a base prime is
first coordinate is
n
i=2
The number of elements in the two cases differs and the greatest common multiple
is oneO Therefore, the answer to the question posed in the preceding paragraph
is negative.
A similar argument shows that no number system with base moduli m1,m2,
~..,mn where (ml,m) = (nMm) =.. - (mnm) = 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 M, but m/M - & when 0 < & < m. Let
m - = dm. If m < ml M, M - T. If m > mi
m~i f M - & for cmir < < < ( + l)mi.
ASD TR 61-483 69

Suppose kml = Q, then m - & = mlm2,..,mn - mlk but (m,ml) = 1; therefore,
m(M-e 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 —(l) 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,...,xn) relative to the basis < 31,,B n > is expressed
with coordinates (Y1,Y2,..,Yn) relative to the mixed base basis < al,..., n >
by determining the q = Ilqi jl matrix and following with the matrix multiplication
X * Q = Y. The elements of the Q matrix are governed by the equation
ASD TR 61-483 70

Pi = ql + *. + qinn for i = 1,2,..,n (-10)
The Y so obtained vgl not in general be a li-near form with restricted coefficients Carrys murt tohen'be propagated from each position to the next more
significant posit;ion The general co-nversion will require up to n-l carries.
To reduce the maximnum possible n if.ber of carries which can occur by say m-l
carries, it will be necessary and sufficient to guarantee
y < mk for k - n-mr,..n. (5-11)
This is in turn equivalent to the condition
qik = ik for ik = n-m,...,n. (-12)
Condition (5-12) may be expressed as
n-m-l
= +k + ciki. for k = n-m,. o,n. (5-13)
If Ilaijll 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 subarray must be preserved in Ijbi(ll, the array of the 3 vectors. The only other
requirement is that Ilbij. be triangular. Other considerations which affect
the selection of the reraining elements in the 3 array stem from a desire to
simplify the carry structure in the P system.
Since aiJ - ij for i, j = n-m,.o.,n the carry structure in the last m
positions is fixed. Carries from the kth components to the jth components
whe re
k = n-m,oo.,n
j = 1,2,...,n-m-l1
can be prevented by the following constraint
ASD TR 61-483 71

bij = 0 for i - n-m,...,n
j = 1,2,...,n-m-1.
Further carries can be eliminated by making the upper right partition of the
array the identity matrix.
Since aij = b.i for i, j = n-m,...,n carries from the 2th component to
the (e-l)st component will occur for Q = n-m+l,...,n. Therefore, at least
m-l carries will occur in the ( system. The total number of carries in the 3
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 of
Chapter III, it is clear that much speed is sacrificed in multiplication.
5.3 GENERALIZATION OF SIGN DETECTION FOR THE RESIDUE NUMBER SYSTEM
Let a residue number system be defined as
Pn Pn
SRN =Y1 +' + Yn m(-14)
(mmj) = 1 except for i = j
where SRm X
XI = x.
i mi,
i= Pn
m - Pn
ASD TR 61-483 72

The residue number system is a member of the general class of nonredundant
weighted number systems wnich satisfy the following relationship:
Sr1 Z P1 +.- + ZnPn (5-15)
The necessary and sufficient conditions for the validity of this relationship
is the triangularity of the weight matrix (See Theorem XV and XVI).
Consider next the special mixed base number system which satisfies the
relationship. It has been showa in the previous sections of this chapter
that the only non-redundant number systems having simple sign properties is
the mixed base system.
n p
SM - i (5-16)
i=O Pi
ZO is identified as A(x) and zl is the high order digit of X. Any nonredundant weighted number system S must satisfy the relation
S = S. (5-17)
where S = zlp, +... + ZnPn'
The following relations are also valid if S = SM
kS = kkSM
[kS] = [kSM]
(5-18)
IkS} = IkSM)
jkSm = lmjI
Consider the normalized residue code
S =S
RN SM (5-19)
RN i SM i
SPn ] = _Pn2
ASD TR 61-483 73

n yipil i Pi
Lj=l m i o Z lP (5-20)
It is possible to further reduce the left hand side of the equation when
mj IPi. This occurs when i > j.
P n YPi i Pi
Ey - + = z i (5-21)
j'i mj J>imj I=0 P
The i-l term associated with equation (5-20) is
_i ____ oi -l
LSn YjPil 1 Pi-l
Z mi-li= ZO Pa (5-22)
Both sides of equation (5-21) are multiplied by mi and the resulting equation
is subtracted from equation (5-20) to give
n YjPi n YPi-l1
E mj^ -M E ~ mj = zi l [i] n (5-23)
j =l " J _j=1
Reduction of the left side of equation (5-23) yields
n Yj, i n ^ jPi-I
YiPi-l + Ei m mj Z = z. (5-24)
^i i-l p>i mJ j-1 mj
The identity
[f] - mi -- = [] Imi (5-25)
may be applied to equation (5-23) to give
M=1 2 = i (5-26)
= j mi -i
0 [i ] n where mo =oo
Equation (5-26) may be reduced to
Zyj Pi + Fj yjP7]i
J L J>i mj m i
ASD TR 61-483 74

ln yjPI
YiPi -1 + L i m mi (5-27)
The special case 2 mli z2 = z11 ^- + Z12; 0 < Z < 1; 0 < z < 21 may be
handled within the framework of the previous formulaso In particular
zll = r + + + Yn (5-28)
mi ml ml mn
and
Z - +.. ] 2+y+ (5-29)
Lmi mn 2
or in general when 2' mi
zm =J ml
Z1 = + L Y 2+ + +mn y2 (5-30)
Equation (5-29) and (5-30) should be regarded as the fundamental definition of the sign digit- All known methods of sign detection may be interpreted in terms of these equations.
ASD TR 61-483 75

CHAPTER VI
DIGIT ENCODING iN ARITHPvTIC OPERATIONS
This chapter discusses some coding schemes for individual moduli and
the resulting facility of arithmetic operations Two types of natural encoding result depending upon how one represents the integers with respect to
multiplication. The first approach analyzes the abstract structure of the
given prime subring, i.e., residue digito It is recognized that still a
further decomposition is possible with respect to multiplication, A representation scheme is suggested by the direct sum decomposition of the component multiplicative subgroups. The second approach treats multiplication
as a linear transformation on the additive subringo Such a treatment suggests a weighted code so that 1the fundamental property of multiplication, its
distributivity, may be employed. This is the more conventional approach.
It will be shown how codes may be constructed for arbitrary moduli by the
use of redundancy. Furthermore, the redundancy may itself be used to speed
up arithmetic operations,
6,1 CODES BASED UPON THE GROUP STRUCTURE OF THE MULTIPLICATIVE SUBGROUP
The fundamental idea of the residue number system is the ring decomposition:
RM - Rpla1 Rp a2 e — Rp m m
7p.i = M (PiPJ) = 1 i j
ASD TR 61-483 77

where Ri denotes the ring of integers modulo i.
If the pi are taken prime, there is no further ring decomposition possible. Nevertheless, the subrings Rp possess multiplicative groups which
may be further decomposed. In general, the order of the multiplicative group
of Rp a is a group of order ((pi.i) where $ is the Euler function. If p is
Pi 1
prime and a = I, then ~(p) = p-l and the multiplicative subgroup includes all
but the zero of the subring.
Since p-l is not prime, this cyclic group may be represented as the product of its prime power cyclic subgroups. In number theoretic terms we are
just saying that multiplication may be done by taking the index function of
the additively expressed integers and performing a residue encoding.
As an example, take R31o Column I contains the additive code for R31,
column II the index or multiplicative representation, and columns II a, b,
c the decomposed or residue representation of II.
If ai 1 then the multiplicative subgroup will no longer include all
but the zero of Rp a, since p, 2p, 3p, etc., will be "divisors of zero."
In this case, a larger system may be constructed of which Rp ii is a homomorphic image. A semigroup acting like an exponent of p is adjoined to the
multiplicative subgroup representation. This semigroup EF = (0,1,..., l has
the operation defined as follows:
x - y = max(a; x+y) x,yeEa
Every element in %X is represented in the form x = ypi where y is in
the multiplicative subgroup and i is in E1. The whole system is then
ASD TR 61-483 78

Cq1 @ Cq2 ~ Cqn E Fa
fqi = (pai)
i=l
TABLE 1
ENCODING OF THE MULTIPLICATIVE SUBGROUP
I II III I II III
a b c a b c
C31 C30 C2 C3 C5 C31 C30 C2 C3 C5
0 -- -- -- -- 16 6 0 1 1
1 0 0 0 0 17 7 1 1 2
2 24 0 0 4 18 26 0 2 1
3 1 1 1 1 19 4 0 1 4
4 18 0 0 3 20 8 0 2 3
5 20 0 2 0 21 29 1 2 4
6 25 1 1 0 22 17 1 2 2
7 28 0 1 3 23 27 1 0 2
8 12 0 0 2 24 13 1 1 3
9 2 0 2 2 25 10 0 1 0
10 14 0 2 4 26 5 1 2 0
11 23 1 2 3 27 3 1 0 3
12 19 1 1 4 28 16 0 1 1
13 11 1 2 1 29 91 0 4
14 22 0 1 2 30 15 1 0 0
15 21 1 0 1
As an example take R27 = R3. Column I gives their additive representation, column II the index if it exists or a factorization ypi if i O0.
Column III a, b the residue representation of the index and column IV the
exponent. Notice that the system contains a certain amount of redundancy.
The number six could have just as easily been represented at 11.3 or 20.3.
ASD TR 61-483 79

TABLE 2
FACTORIZATION PROCEDURE
I II III IV I II III IV
a b a b
C27 CL8 C9 C2 E3 C27 CL8 C9 C2 E3
or or
Factorization Factorization
0 1.33 0 0 3 14 17 8 1 0
1 0 0 0 0 15 5.31 5 1 1
2 11 1 0 0 16 4 4 0 0
3 1.31 0 0 1 17 15 6 1 0
4 2 2 0 0 18 2.32 1 0 2
5 5 5 1 0 19 12 3 0 0
6 2.31 1 0 1 20 7 7 1 0
7 16 7 0 0 21 7.31 7 0 1
8 3 3 1 0 22 14 5 0 0
9 1.32 0 0 2 23 11 2 1 0
10 6 6 0 0 24 8.31 3 1 1
11 13 4 1 0 25 10 1 0 0
12 4.31 2 0 1 26 9 1 0 0
13 8 8 0 0
There appears to be at least two possibilities for application of the
multiplication decomposition exhibited above.
The most obvious is to use a machine code that is based on this decomposition. The desirability of such a scheme appears questionable except in rather
exceptional circumstances. The fundamental question, of course, is how one
adds in such a code. If a reasonably fast technique for addition were forthcoming, it might be reasonable to consider using the multiplication code since
multiplication in the multiplication code is considerably more easily accomplished than addition in the normal code due to reduction of carry problems.
Nevertheless we are not too hopeful since there is no distributive law operatASD TR 61-Lv83 80

ing so that, addition can be done by only multiplication as one can the converse in the normal situation.
The other possibility is to somehow use the multiplicative decomposition
in the logical design of the multipliers where a more conventional code is
used as the basic machine language, This is essentially dependent on conversion from conventional to multIiplication code and reconversiono This problem
ressembles the radix based-residue conversion problem except on a much reduced scale and the techniques developed there are applicable. Some techniques
which appear quite expensive in time and hardware for the gross conversion
problems will be applicable at this level because the order of the subring
being decomposed will be of very moderate magnitude. A further distinction
is that the completely reduced codes would only have to be added whereas in
the ring decomposition one must both add and multiply in the subrings, The
use of this code within residue multipliers would be indicated if mappings
were used rather than sequential methods,
6.2 CODES BASED ON MULTIPLICATION AS A LINEAR TRANSFORMATION
The type of weighted binary code with which this section deals in the
following. It consists of a set X= [Xo,. oxn-l], xe{O;l1 of 2n elements.
The set is interpreted by a set of weights W = wloo wnj and a modulus M
where the wi and M are integers with wi < Mo We further require the following relation on the weights
I~W ecW= (2~ mod M)eW
ASD TR 61-483 81

This latter property ensures that addition of code elements may be done using
ordinary carry procedures. Also we shall consider only the case where M is
an odd primeo The work is easily generalized to the case of composite moduli,
at the expense of a certain amount of notational inconvenience.
A code or a subset of a code is said to be complet if for every positive
integer k < M there is at least one xEX such that
/n-1 X
k L {L xiwi)mod M.
It can be noted immediately that if M < 2m the entire code will be complete.
We shall be primarily interested in the completeness of certain subsets of
codes.
If wo = i and wi+ - 2wimod M, then because of the restriction on the
weights and modulus, it must be that 2wn_1 1 mod M. Since for each wi,
there exists a wj such that wj - 2wi mod M then a permutation xi->xj results
in multiplication by 2, Repeated shifts will therefore generate all powers
of 2 modulo Mo Thus there is set up a correspondence between certain elements of the code set and a cyclic permutation of the bits of the code. This
correspondence is the basis of the ordinary pencil and paper method of doing
multiplication as well as conventional machine multiplication with the slight
difference that in our case we have a true permutation whereas conventionally
one bit is "lost" and a zero introduced.
It should be clear at this point that we have described what is sometimes
called a reduced radix code. This is the special case obtained when M = 2 -1.
We mention another coinmonly known example of this class which is not usually
ASD TR 61-483 82

thought of as a weighted code at all. It is the one digit per wire code. In
this case n = M-l, and the weight set includes all possible weights,
These two well known coding schemes are the extremes of all codes of this
class. In the case of the former, there is almost no redundancy (zero has
two forms) but the arithmetic must be sequentially, The one digit per wire
code on the other hand has extremely high redundancy while permitting simple
combinational arithmetic, It is our purpose to investigate those codes lying
somewhere inbetween,
Consider the code M = 17, n - 8, W = (1,2,4,8,16,15,13,9}. In this case
the weights are entirely generated by powers of two. This code may be viewed
as using the reduced radix code for 28 = 255 to represent numbers modulo a
divisor of 255. Notice, however, that by introducing all this redundancy it
is possible to select a complete subset of this code with some very nice
properties. The following subset has the useful property that no element has
more than two bits which take the value one.
This property ressembles the property of the one digit per wire code in
that it facilitates arithmetic. It is not quite as easy to do arithmetic
in this code, but on the other hand it is much less redundant. Addition may
be done quite easily in this code using adders in each position consisting
of one two input "and" and one three input "or."
At most, 2 levels of logic are required regardless of carries because
carries can propagate only one levelo This results from the additional property of the set chosen that no element has two adjacent "oneso"
ASD TR 61-483 83

TABLE 3
THE CODE M = 17, n = 8
Wi 1 2 4 8 16 15 13 9
X0 Xl X2 X3 X4 X5 X, X7
0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
2 0 1 0 0 0 0 0 0
3 0 0 1 0 1 0 0 0
4 0 O 1 0 0 0 0 0
5 1 0 10 0 0 0 0
6 0 0 0 1 0 1 0 0
7 0 0 0 0 0 1 0 1
8 0 0 0 1 0 0 0 0
9 0 0 0 0 0 0 0 1
10 0 1 0 1 0 0 0 0
11 0 1 0 0 0 0 0 1
12 0 0 0 0 1 0 1 0
13 0 0 0 0 0 0 1 0
14 1 0 0 0 0 0 1 0
15 0 0 0 0 0 1 0 0
16 0 0 0 0 1 0 0 0
YXi
Ci
Or
Si
Figure 1. An adder for the M = 17, n = 8 code.
ASD TR 61-483 84

Unfortunately the sum produced may no longer be a member of this special
subseto It is necessary to retrieve this proper form prior to doing further
arithmetic. The nature of the ccomplexity of this problem is not yet known
sufficiently to make final judgemento It is known that in special cases, reduction networks may be designed such that the total addition time plus reduction is competitive if not superior to conventional binary addition, Futthermore the complexity of the coding networks seems to increase only linearly
with the number of bitso
Notice that complementation may" be done either by complementing each bit
individually or by a simple permutation since "-1" is included as one of the
weights.
If a complete set exists having only at most 2"one" bits per digit, multiplication is reduced to a single addition of the two appropriate permutations
of the multiplicand0 In the example given above, the weights were generated
by successive powers of two, This is not the only manner in which a set of
weights meeting the criteria may be generated. The set of powers of two form
a multiplicative subgroupo Any coset of this subgroup is also closed under
multiplcation by two and therefore may be included in the weight seto Consider
1,2,4,8,16 1.
the set of weights 1>6,12,24,17J and M 31. This code has a complete subset having the 2 "one" bit property. The only difficulty here is that there
are no permutations corresponding to the coset weights {3,6,12,24,17], and
therefore multiplication cannot be carried out by successive shifts and adds,
In order for this property to be retained, it is necessary that the cosets
p1,2,4,8,16 X
themselves form a subgroup under multiplication. Thus the set j3029,27, 23,1J
ASD TR 61-483 85

would be a better choice since the cosets are now isomorphic to the 2 element
group (1,303.
In general, it is easy to determine closed sets of weights of arbitrary
order dividing M, using powers of primitive roots as generators. The problem
of determing whether a code has a complete "2 one's" subset is more difficult.
The coset decomposition of the entire multiplicative group allows a short cut
to be usedo If any element of a coset is representable with only 2 one bits,
then every other element in the coset also is, since each is only a permutation away. Thus, only the least element in each coset need be examined.
Consider as a final example a coding for M = 127. Certainly the weight
set must include (1,2,4,16,32,64 } If no additional weights are used, the
almost non-redundant reduced radix code of seven bits results by adding the
]1,2,4,8,16,32,64
subgroup generated by 36 126, the 14 element subgroup 126,125,123,119,11
95,63 results.
This code has a "3 one's" complete subset but no "2 one's" complete
set, If the subgroup of order 3 generated by 342 is used, the resulting 21
weight set does yield a "2 one's" complete subset.
In concluding these remarks about redundant weighted codes it should be
emphasized again that the recovery of the cannonical form of a number is the
big question in the practical utilization of these codes. If moderate success
is met here, the way is open to use very large moduli with a resulting saving
of scaling and base extension time.
ASD TR 61-438 86

CHAPTER VII
DIVIS ION
7.1 INTRODUCTION
The definition of a division in Euclidean rings suggests that algorithms
for performing it will be crucially tied up with magnitude comparison. Given
two elements (ab) it is desirable to find a (q,r) such that.
a = bq + r and r < b
The difficulty of recovering the natural magnitude ordering from the residue
representation had initially led us to suppose that division within the system would be very difficult also. Recent workers have recognized essentially
three different approaches.
a, Devise a really efficient magnitude comparison scheme; more
conventional algorithms will then prove feasibleo
b. Do division in some other closely related systems such as a
mixed base system.
c, Find an algorithm which is independent of magnitude tests,
This chapter is devoted almost entirely to the approaches of the third type,
The brief discussion of the first two approaches is given for purposes of
contrast
Considerations of the nature of the sign detection problem have been made
in other parts of this report. While it is not so fair to say that no improvement can be made in the presently knowri sign determination scheme, it
is clear that sign detection will remain essentially as time consuming as
ASD TR 61-483 87

division by a divisor of the moduli of the system.
Since, the division algorithms used in class C also use these "division
by a constant" procedures any improvements in sign determination techniques
would yield a corresponding improvement in techniques of type C also. With
regard to algorithms of type B, mixed base system division seems to be awkward
at beste It certainly is more complex than any binary division even without
consideration of translation time. This approach appears to be the least
valuable of the three, since it has rather extensive hardware requirements
without really being very fast,
The magnitude determination free techniques known to us are all iterative
in nature and resemble most closely the non-replacement techniques of conventional binary division. With respect to these algorithms, several important
questions must be asked.
1. What is the rate of convergence?
2. What are the hardware requirements?
3. Are any initial estimates needed, and if so, how are they
determined?
4, What is the stopping procedure?
5. What type of arithmetic systems can this algorithm easily be
fit into?
7.2 AN APPROXIMATE DIVISOR METHOD
This algorithm utilizes the fact that inverse multiplication corresponds
to ring division if the remainder is zero.
Let:
m
M = pi (i=,2,..m)
i-=l
ASD TR 61-438 88

be the modulus of a residue number system, Let Z be the set of 2m numbers
less than M of the form
m bi
7Pi bi (0,1}.
i=l
It is well known that division of any number in. the ring of integers, modulo
M by zcZ may be performed in a straightforward way by successively reducing
the dividend by an amount necessary to make it exactly divisible by one of
the component primes of the diviser, and multiplying by the reciprocal of
that prime, In general, the division of x by z will take either 2n or n
steps depending on whether one counts substraction and multiplication as 1
or 2 steps, If m primes compose z, then the remainder of the n-m stages are
necessary to re-extend the quotient to full length. Using the set Z to approximate y for divisors the following algorithm; may now be employed, To
divide x/y; x,yeR; 2y > z > y; zcZ
= r J =X - y
qi qi-l ri ri -= r - L-i
stop when qi = qi- L
An error of 1 will occur if every y < ri < z which may be corrected by
comparison of ri with y following qi = qj if an exact answer is necessary,
It is not necessary that z > y; however, the partial quotients will be
of opposite signs on successive iterations if z < yo
The rate of convergence depends on z/y. Let y = (l-e)z and x/y = qo
ASD TR 61-438 89

The Si are the partial sumands qi-qi _(l-c)x q(l-) r X (l-C)x y =
o y x y -
Si = = q(l-E) ri = xE y
y y
= x[E-c(l-C) ] = X
Si XC (l)- = q(l-c) i ri = xci - xi(1-) y
= x[Ci-(l-e = x
x[i-(j-E)EJi] = XE
The error after i iterations will be
q(l-e)(Ci + i+l..) = qi
for
q <10
then for
qi < 1
ci < 10-a i loge < -a i > a/loge'expressing e as a function of i and a, then e < 10 /
The convergence of this algorithm is crucially dependent upon how well
the set Z approximates arbitrary divisorso In the partical cases where only
a few moduli are used it would appear that this algorithm would not be feasible if a fast division were sought. However, in systems including a large
number of different moduli the closeness of approximation is remarkable, The
system consisting of the primes less than or equal to 31 was considered in
detail. The set Z was tabulated and ordered, A set of twenty-five random
divisors in the range 105 to 106 was examined to see how closely they might
ASD TR 61-438 90

be approximated. Assunming these nunmbers to be divisors of dividends of the
order 101 a quotient of less than 106 will, be produced, The approximating
zcZ for each number was determined along with the necessary number of iterationso For all numbers examined the number of iterations was either 3 or 2,
As an example consider the computation of 10,00,000,000o/815,392
z = 817,190
= 10,000,000,000 12237 r = 10 - (12,237)(815,392)
817,190
22,048,096
q = 12,237 + 22 048096 12,263 ri - 22,048096 - (26)(815,392)
817,190
847,904
q2 = 12,263 84790 12264 r 847,94 - (1)(815,392)
817,190
q = 12,264 * 32,512
r - 32,512
Note that for this particular divisor, which was chosen at random, the
probability of an error of one in the quotient for a random dividend is less
than 1%o
There are three possible means of terminating this procedure. A fixed
number of iterations can be usedo If indeed it were shown that three is the
largest ever needed, such procedure would be the best, For a very small
divisor however, this may not be sufficient as the approximations are not as
good. The test ri+1 = ri does not involve either additional hardware nor
significant additional controls, However, given ri +l = ri, one additional
unnecessary iteration has already been performed. Nevertheless, the insurance
ASD TR 61-438 91

that the error in the quotient is at most one, makes it more desirable than
the fixed length procedure, unless the particular arithmetic system used
scales a.. nunmbers in!to a range where the approximations are always goodo
The third method involves c-omparison of rL with a real divisor and therefore, an additional cycle of n operations following the conditions ri = i+i~
This is the only method for determining an exact quotient0 It appears that
this additional test would best be left tc the prograJmner just in case an
exact quotient is required, since for most uses the error involved is unimportanto The hardware requirements for this algorithm are moderate in addition. to the residue multipliers and adders which will already be available,
A control register of n bits is necessary to indicate the base primes used
in the approximate divisor, D.e hardware for producing the approximate divisor
is an additional problemo It appears that this may most efficiently be implemented by a'table-look-up procedure, Indexing this table requires the first
two or three digits of the mixed base representation of the divisor and requires the equivalent of an additional iteration~ The magnitude of the table
required for this system illustrated would be about 2000 eleven bit words,
which is not prohibitive,
The remaining two algorithms are essentiality unrelated to the residue
number systems itself, )but it is of interest to see what difficulties ensue
in their realizatio.no Both methods require a fractional multiply operation.
It is not yet certain that; alle possible utilizations of residue arithmetic
would entail, having a fractional multiply, however, for any conventional numerical analysis it seems likely. Fractional multiplication schemes all inASD TR 61-438 92

volve division by one of the divisors of the moduli. It is fair to compare
the number of iterations of the above described algorithm with the number of
fractional multiplications of the two algorithms described below. In a system
that permits postponement of scaling, i i reasonable to count the number
of scalings necessary, rather than the number of multiplications.
703 A NEWTON-RAPHSON METHOD
A Newton-Raphson method is derivable from
b 0 A b. - x
ax a
i.e.,
xi+ = Xi - f(xi)/f'(xi)
b b ax0
= Xi - (x _)/( ax 2)^ ~ < 1
ax.
i(2 - )
This is useless directly since it involves the calculation of a/b. If b 1
however, then
xi+ - xi ~ (2 ax), laxo - I < 1
is quite satisfactory since one may compute I/a and then multiply by b.
These procedures converge exponentially since if
Xi = (l-c) o x
then
xi + = (l-~) e x[2 - (a/b)(1-c)x]
(l-e2) ~ x
ASD TR 61-438 93

so. 1 + 1
il
Given an xo suc-h that co < 2' then c < 2 40 which is of'the order requiredo This con:rtrasts favoraily w'ith -the third algorithm.
Xi+i = xi ~ I+b-axi) b <
for xi = (1-c) ox,
x i = x(ti-) [Tl+b-a(l-c))x
= x(i-G) ~ ('-Fb) = xyl-e(l-b)-bc2]
so'i~l _-(l-b) i~b+b
1 - b +- bec
which is very poor if (i-b-) is not very close to 0o
It is possibole to scale b by one of the divisors of the modulus of the
residue system, howevser this still results in a geomet ric convergence to
better than tlhat provided by the approximate divisor method which does not
require fractional multiplication,o Te scaling would require hardware similar to the obtaining of,the approximate divisor as in t;:e first method
described,
74 INIIAL APPROX7IMA!TO7N..S
it is possible to use a uniform xo in the reciprocation formula. For
integral a, then a very small x0 will always sati sfy Il-axol < I A decent
approximation, however, is clearly necessary since if (!-c) is the requ:ired
ASD TR 61-843 94

precision then the number of iteration i must be such that
2i (
C < 2f >(logc)/iOgo
i > iog2 loge/logEo
1i -,.1
i > iog2log E - iog21og E
which for co close to 1 becomes largeo
As an initial approximation, one may use a table-look-up; however, the
index to such a table must reflect relative magnitude and therefore, for
residue numbers, requires a conversion to mixed base, Still, such an approximation is superior to a linear approximation which would require about the
same time but no table. We consider now a system which is mentioned else
where in the report which involves the use of a "double length plus" expression of numbers when in the arithmetic unit. The use of this system is convenient in both the initial approximation procedure and in performing the
iterations themselves,
If the size of the system is such that the double length magnitude M*
is of the order IM2 where MvI is the single length magnitude then in approximately the same time, one can compute a quadratic approximation where the coefficient of the second order term is a small integer less than L. This is
possible since where the fraction x is represented as [xM], the first coefficient is represented directly [a] while the second and third as bM and cM2,
so that
ax2 + bx + c
is represented before scaling
ASD TR 61-438 95

[a][xM]2 + [bM][xM] + [cM2]
= [ax2M2 + bx] + [cM2]
[(ax +bx)M2] + [cM2]
which becomes
[(ax2 + bx + c)M2]
Overflow will not occur as long as [(a+b) < L], A comparison of approximation
techniques is somewhat difficult because of the measure of goodness of fit.
Ideally one wishes to minimize the expected number of iterations which is
I I
c + [- log log - (a)l]da
given a uniform distribution of Xo If f(a) is the approximation of 1/a then
co = l-af(a) and only a numerical solution appears feasible. A simple least
squares measure should, however, give a rough comparison.
The best-fitting quadratic using a least squares criterion results from
the solution of the system of linear partial differential equations:
_ = 0 = _ 1
_a ab bc
1
[ l-x(ax2 + bx + c) ]2dx.
These equations easily reduce to three linear equations in the coefficients.
The solution yields a nonintegral value for a, however the linearity of the
system insures a unique local maximum, and the best integer values for a may
be determined by inspecting the two nearest integers.
The hardware requirements in addition to those already needed for the
fractional multiple are almost negligible= The only additional equipment is
ASD TR 61-438 96

that associated with determining the initial approximationo Depending on the
type of instructional organization used in the machine, it may be possible to
do away with the division instruction per se, altogether. The condition under
which this would be possible without loss of speed would essentially involve
a streaming mode of operation, similiar to that used in computing the vector
dot product
Before concluding this chapter, it is important to emphasize again the
impossibility of deciding on a'best division algoritbm without considering
the system on a whole. In our opinion, the Newton-Raphson Reciprocation procedure is clearly superior to any other known if a fast fractional multiplication has already been purchased. Its exponential rather than geometrical con.vergence plus its lower hardware requirements make it quite satisfactory., The
other algorithms might have use in certain limited, special purpose applications where a full fractional multiplication is not desiredo
ASD TR 61-438 97

I
I
I
I

CHAPTEFE VII
TEE MUL IIT PLI2ATIVE OVERFT LO PROBLEM
8.1 INTRODUCTION
The problem of multiplicative over-fl.ow detection is one that is unique
to systems in which the multiplication operation is accomplished in one step.
In conventional systems, those in which multiplication is performed as a
series of additions, the detection of multiplicative overflow can be handled
by the detection of additive overflow.
One of the main advantages of a Residue Number System (RNS) is its
adaptability to a one-step multiplication operation. it follows that one of
the more pressing probl ems of a RNS is that of detection of multiplicative
overflow.
In any finite number system, an obvious way to prevent overflow under
multiplication is to require that every number to be processed be less than
the square-root of the system's limit, The product of any two such numbers
will be less than the limit of the system, and no multiplicative overflow
will exist. But this restriction must apply to every step of each calculation, and merely represents the substitution of a scaling problem for the one
of overflow detection.
A universal problem of finite machines, whether their organization is
integer or fractional, is the one of scaling the double-length result of
multiplication back into single-length form, This problem has a solution
ASD TR 61-438 99

that takes the form of multiplication by a constant. In a RNS of singlelength capacity m, where the residue representations are interpreted as integers, that constant is the inverse of mo
In his work on RNS, Svoboda2 suggests handling this scaling problem by
employing a double-length multiplier whose capacity is at least as great as
the square of the capacity of the single-length system, He then employs a
procedure which is essentially division by m (the single-length capacity) to
rescale the result of multiplication into suitable form for further calculations. The unfortunate feature of this method is the amount of time required
for the digit-fill-in operations (single-to-double-length and vice versa) used
to implement the scaling processo
Cheney9 has suggested a method which involves scaling by combinations of
the individual base primes. The precision achieved by this method is not as
good as Svoboda s, but the comparison is somewhat unfair since Cheney does
not use the double-length idea. The question of precision will be treated
more fully in the last section of this chapter.
The individual-base scaling procedure is awkward and cumbersome. As a
result it is time-consumingo Even if precision were equal for the two procedures, this one suffers by speed-comparison.
Consider now an, extension of Svoboda's concept to include what will be
termed multiple-precision. This title may be misleading, as the direct result
is a gain in speed while precision is increased non-uniformly. That is, the
increase is slight (or non-existent) in some cases, while present to a greater
degree in otherso
ASD TR 61-438 100

The proposed extension is accomplished by attaching positional significance to each of a group of RNS representations (as in, for example, a decimal number) and allowing the propagation of carries between subgroups of
these representations.
Such an arrangement, with the operations of truncation and scale-factor
multiplication, constitutes a Floating-Point number system. The arithmetic
of this system is apparently retarded by the necessity for carries, but carry
assimilation is accomplished as a part of the scaling operation.
The speed advantage of this system comes from the fact that the subgroups of RNS representations (the coefficients) are small. This permits the
standard RNS operations to be accomplished rapidly. The digit-fill-in and
scaling operations are performed on the entire number by processing several
small parts of its simultaneously. A complete description of these operations
is continued in the following sections,
The two parts of this chapter which follow are both methods of employing this parallel structure. The system contained in Sections 8.2 through
8.8 is primarily a general purpose structure, while that of the remaining
sections of the chapter is intended for special purpose use. That is, the
one considers everything that might occur, while the other ignores or minimizes certain problems under the assumption that they will occur infrequently,
if at all.
The original starting point for the two developments was different. The
former is a result of an inquiry into the general problem of multiplicative
overflow. The latter came about as a use for the redundancy established by
ASD TR 61-438 101

an extra-length representation.
There are two main areas of dissimilarity between the two methods. The
first is the question of whether the sign of a number should be carried along
explicitly in the representation, or be allowed to remain implicit within the
representation. The second is a question of the size of the double-length
system; whether its capacity should be the square of the capacity of the
single-length system, or slightly larger than the square. Rather closely connected to these two areas is the question of when and/or how often the internal
scaling procedure must occuro
Perhaps each system is superior for its intended use, or even for a series
of specified uses. Given a well-specified purpose, the two systems could be
carefully compared to determine equality or the superiority of one over the
other.
8,2 APPLICATION OF THE SQUARE-ROOT CRITERION
This direction of attack upon the overflow problem branches off from the
square-root criterion.
Consider, for the bases of a RNS, some sequence, 3, of composite numbers
3 = 5ioo^n
subject to two restrictions:
(ij) = 1, j(8-1)
31 - pf (8-2)
ASD TR 61-438 102

The first restriction is equivalent to, and may be replaced by, the following
restriction on the set, P, of su-bbaseso
(Pi,pj) = 1, i A j (8-3)
The set, P, may be thought of as a sequence of prime numbers with no resulting loss of generality,
Consider also, in the matter of coding the modular representations of
the RNS with respect to the base i3, the use of a two-digit uniformly-based
number with base pi. Such a coding does indeed accomplish the representation,
although it requires one carry-digit within each composite-base representation,
The following formulas serve as a summary of the discussion of this section:
N - imod Pi, 0 N < M (8-4)
n
X = M H i = P2 (8-5)
i=l
~i = ailPi + aio (8-6)
It follows that the zero power, or units, digit (aio) represents the
residue of N with respect to p.i Thus there exists a readily available ndigit number which represents the residue of N with respect to m, where
m= vM = (pi (8-7)
i=i
These n digits are the units digits (aio) of the n representations of N modulo
i(i = 1,2,.8,n).
ASD TR 61- 43 8 103

8.3 CONSIDERATIONS OF THE DOUBLE-LENGTH SYSTEM
If a number, A(O < A < M), is considered to be of the form
A = am + a (8-8)
it is clear that ao may be found by some reduction process involving the
single-length system m: if you will, the "square-root" system m. That is,
since Oao<m and the n units-digits of A(aio; i = 1,2,...,n) are available
by inspection, the search to find ao may be limited to the m-system. Digitfill-in of ao from the m-system into the M-system acquires the first-power
digits of ao, and subtraction of this result from the original representation of A leaves alm as the new representation.
Because alm is an integer multiple of m, the units-digits of this representation are all zeros. For this reason, consideration may be limited once
more to an m-system representation, in this case involving the first-power
digits. Division of this representation by the first-power digits of the
representation of m, along with m-system to M-system digit-fill-in, yields a,.
The above paragraphs describe a complete reduction of the M-system representation of a number to more conventional form by means of m-system operations. With the background established so far, investigation of some properties of this "square" system may be undertaken.
The redundancy established by this particular system, the easy availability of the square-root residue, is gained only at the expense of providing a carry-digit within each composite-moduli group. But this system is
useful in the scaling aspect of the problem. The redundancy provides the
ASD TR 61-438 104

necessary magnitude information for scaling, which makes division by m a
simple operation.
8.4 MULTIPLICATION
Consider the multiplication of two numbers A and B (0 < A, B < M) in
algebraic form.
A = aim + ao, B = blm +bo (8-9)
AB = alblm2 + (aobl+albo)m + aobo (8-10)
Each of the ordered pairs (aibj) represents a non-overflow situation since, by
the nature of the system, every ai, bj < m.
The interesting part of this is not in the possibilities for detection of
overflow, but in other possibilities suggested by the ordered pairs. These
numbers are all readily available in the system, and the products are guaranteed non-overflow. Through some system of manipulations they may be carried
along to give a complete description of any number, though it be arbitrarily
larger than the finite limit of the sub-system,
Such factors as truncation and round-off may be considered if an approximate answer is acceptableo For example, it may be considered necessary to
keep only the four most significant coefficients, any remaining terms then
being discarded.
Now consider a more general multiplication, AB, with A and B not restricted in magnitude as they were previouslyo Let R be defined as the reduction operation of Section 8.3, and understand R1 to be the first (ao) portion of this operation, while R2 shall be the remaining (al) portion.
ASD TR 61-438 105

Let
r
A = 7 aimi (8-11)
i=O
s
B = E bjmi (8-12)
j=O
r s +i
AB = C = Z cdmd (8-13)
d=0
where
0 < ai,bj,cd < m. (8-14)
The multiplication AB results in several ordered pairs, aibj, and by the restriction of equation (8-14)
0: aibj < M (8-15)
so that the operation R, when applied to these products, gives
R
aibj Cijim + cijo (8-16)
in which
0 cjji < m-i; 0 cijo < m. (8-17)
Define, for the collected term of multiplication:
Ck = z cijt (8-18)
i +j +t=k
Since the number of terms collected is very small compared to m,
0 < Ck <<m2 (8-19)
ASD TR 61-438 106

Now, under a further reduction step:
R (8-2O)
ck -> ckm + Cko (820)
The restrictions upon these coefficients follow from equation (8-19)
0 < cki << m; 0 < Cko < m (8-21)
At this point, AB = C may be expressed as follows:
r+s
C = S (cklm+cko)mk (8-22)
k=O
Since the largest number expressible in this form is given when
A = m -- 1 (8-23)
B = m S - 1 (8-24)
AB = mr - - ms+1 + 1 (8-25)
it follows that
C = AB < mr 2 (8-26)
and
Cr+s+2 = 0 (8-27)
Thus, finally, the form of equation (8-13) is obtained
r +s +1
C = z cdmd.
d=O
Since the cd's must satisfy the restriction of equation (8-14), they must result from a process of reduction upon the ckt's and completion of the carry
ASD TR 61-438 107

(or scaling) processo An exception is cr+s+l which will never propagate a
carry, as a result of equation (8-27)
An estimate of truncation error would be in order at this point. Let
the decision be made to store only the four most significant coefficients of
any number, the highest-order of which is non-zeroo Thus if
A = armr + arlmrl + ar_2mr-2 + ar_3mr3 + ar_4mr +... (8-28)
bsms + bs2lms-3 s-4
B = bsm + b 1m s-l ~b2ms + bsms-2 + bs-2ms + bs +... (8-29)
certainly
AB < arbsm (8-30)
while the highest-order neglected term is
(ar-4bs + arbs-4)m 4 (8-31)
Therefore the error is given approximately by
arbs 4 + ar-4bs
arb m4 (8-32)
In the worst case, with ar, bs — 1 and ar-, bs,4'v m, a rough upper bound on
the error as obtained from equation (8-32) is 2/m3o While if ar, b ^ m and
ar_4, bs_4 - 1, a bound on the error is 2/m5 In any case m need not be too
large to result in quite a few significant demical digits with such an arrangemento For example, if the set P of sub-bases is (2, 3, 5, 7), m = 210 and
2/m3 - 2.16 x 10-7 And if P is (3, 5, 7, 11), m = 1155, 2/m3 -v 1.3 x 10-9
This demonstrates the feasibility of a "small" BRNS
ASD TR 61-438 108

Figare 2 is a schematic description of multiplication in the proposed,
floating-point RNS. The justapositions (aibj) all indicate non-overflow RNS
multiplications, the R operations are as defined earlier in this section, and
the additions indicated are also non-overflow RNS operations.
a3b3 a3b2 a2b3 a3b1 a2b2 alb3 a3b0 a2b1 a1b2 aob3 a2bo albl aob2
R R R 1R j; R R R R IR jR R R
C331 C330 C320 c310 c300 C200
C0321 +C230 +C220 +C210 + 110
i 0231 3 1 1 + 130 120 + 020
+C221 +C301 0+30
+ 131 +211 +2201
+12 1 + 1 1
_c_031 +C021
C7 06 C5 C4 3 02
R R R R R
C7 C60 C50 C40 C30 C20 Vc61 < 2; c51 < 4; c41 < 6;
+061 +051 i041 +-31 +021 *** 1C31 < 6; C21 < 2; c7,cio < mj
C7 C6 c5 04 03 X
R R IR R
C7 C60 050 C40 C30
+061 -+51 +041 +031 { cil 1; C7,Cio < mi
C7 c6 5 04 C3
R R R
C7 C60 C50 C40 C3 (T: Truncate, if C7 0O)
c61 +051 +041
07 C60 C50 C4 03
R R ***See Section 808 for
^ ~\ ~ ~~ J^~~~/ >carry-completion
c7 C60 C50 C4 C3 sensing.
+ 61 +051
C7 06 C5 04 03
Figure 2, Multiplication in the floating point BRSo
ASD TR 61-438 109

The first level shown is actually the only multiplication involved, the
remainder of the operation can be regarded as scaling to get the respective
digits back intc the C < mi < m rangeO This scaling can take place quite
separately from the multiplicationc leaving the thirteen side-by-side Msystem multip lication units free immediately for a new cperationo The results are no't immediately available for further computation, however, but
must first be processed through the reduction "grinder "
The red:cti-cn ma -hine will consist of various levels and may operate as
a unit- or as several semi-independent stages. Some of the stages may prove
useful for operations on, added numbers, etco The "grinder" may also be processing a sequence of numbers at the same time in different stages, with a
continuous flow of results from the outputs
In Figure 2, A and B are taken to be of the following form:
A = mr(a.sm3 + a2m2 + alm + ao) (8-33)
B = m (b3m + b2m2 + b1m + bo) (8-34)
Manipulation of the "exponent" (m ) is not shown, but understood,
At the first level of reduction, thirteen side-by-side R-type units are
necessary' These are folloowed by five adders, followed in turn by five Rtype unirtso N'ext come five adders, followed by four R-type units, As was
seen in equatiion (8-2'7) further attention to c7 is unnecessary as it cannot
overflowo
At this level, fs ou ad.es a re necessary and truncation can occur by
dropping 030 In the worst case three more levels are necessary, with R folASD TR 6!-438 110

lowed by adder, The number of elements needed would decrease with each stage,
It is possible that carry-completion sensing would be both possible and profitable. That subject will be taken up in a later sectiono
8.5 NUMBER FORMAT AND MAGNITUDE COMPARISON
A description of number format is now presented in order to lay the
groundwork for a discussion of some other operations in the system. The system-description of a number, A, shall consist of a magnitude-plus-sign arrangement. The magnitude is to be represented by four coefficients with positional significance, and an exponent term, S(A) is defined to be the sign of
A, and may be represented by one bit.
S(A) a3 a2 al ao r (8-35)
where
0 a a1 < m,
while
r = 0 41, ~+2,,.o~q (8-36)
Equation (8-35) is then defined to mean
A = S(A)(a3m3 + a2m2 + a1m + ao)mr (8-37)
The magnitude comparison operation may now be accomplished by a threestep procedure. If A and B are represented as suggested in equations (8-35,
36, 37), then:
1. Inspect the signs;
ao If they are different, the positive one is larger.
b. If they are the same, proceed to step 2.
ASD TR 61-438 111

2, Inspect the exponents;
a, If they are different, the more-positive one corresponds to
the larger nurmbero
b, If they are the same, proceed to step 3o
50 Complement bi(i = 0 1, 2, 3) with respect to M, add A+B = C.
Operate on ci with Ri, Ispect c31m
a, If c3im n C, B > A>
b, If c31m = 0, inspect C3o.
1. If c 30 00 A > Bo
2. If C3 = 0 inspect C21m,
The complete operat-ion R is not needed in step 3, because the question of
magnitude is determined by whether or not cilm is zero, This information is
available at the output of Ri,
Figure 3 is a graphical aid for step 3 above, The X under sign and exponent indicates that they are of no interest in this step.
S(A) as a2 al ao r
S(B) b3 b2 b1 bo r
X 0C3 c2 C i Co X,I jRi j1 RI
C31mnC30; 212MC20; ClmC10; C01om,00
Figure 3, Step 3 of the magnitude comparison.
806.TIfE FOUR CASE-SS OF ADDITION
For the addition of two numbers, there are four cases of interest, Inspection of -the signs and exponents of A and B determines the case in any
particular instance, For convenience and simplicity, A is assumed always
positive, with more-positive relative exponent if the exponents are different.
The four cases are:
ASD TR 61-438 112

1. Same exponent, same sign;
2o Same exponent, different signs;
3o Different exponents, same sign;
4, Different exponents, different signs,
Addition in case 1 is acom nplished by positional addition of corresponding coefficients. The sign of the result is the same as the signs of the two
numbers. The exponent must be determined in the scaling process. Truncation
(T), the right-shift of coefficients, and augmentation of the exponent as
shown in the final stage of Figure 4, take place only if c31 A O No further
carries are possible out of c3 or c2_, but in the worst possible case, three
more sequential (R, Add) operations will be necessary to complete the carry
process. It can be seen that only one carry (and of unit magnitude) can be
transmitted from any position. That is, a position that generates a carry
cannot propagate one. Thus, carry-completion sensing is suggested.
+ a3 a2 a1 ao r
+ b3 b2 bl bo r
+ c3 C2 cl Co r
R R R m
+ Cc31 c30+C21 c20-I 11 010+01 Co
+ C3 C2 C1 C0 c c lr+l
T
Figure 4. Addition in the floating point RNS,
Addition in case 2 is accomplished by, first, step three of the magnitude
comparison operation. The next step is complementation of the smaller number,
and then positional addition. This is followed by the R1 operation as in
Figure 3. Then a check must be made on cii(i = 0,1,2). If cil = 0, the process is complete. if cil ~ 0:
ASD TR 61-438 113

1. Add m to ci;
2. Add M-1 to ci+.
This reduction process must be carried out three times in the worst possible
case. However, a borrow can be propagated through the ith position only if
cil = cio = O0 which suggests a possible borrow-completion sensing method.
The sign of C is that of the larger number, A or B. The determination of r
must, upon borrow completion, be determined by the highest-order non-zero
ci, and a shift accomplished to put that ci into the c3 position.
Addition in case 3 involves a relative shift to the right, of (r-s) positions, for the smaller number. At most four reduction processes are necessary to complete carry-propagation. Sign is carried along unchanged, while
truncation and r-augmentation are accomplished as the last step.
Addition in case 4 combines the right-shift of case 3 and the complementation of bi with respect to M as in case 2. Once again, borrow-completion requires at most three reductions (R1). The resulting sign is that of the
larger number, while positional-shift and r-determination are accomplished as
the final step.
8.7 DIVISION
The division procedure in this floating-point system must be some combination of the familiar and the unfamiliar. The familiar portion is due to the
similarity of the gross system-structure to the decimal system. The unfamiliar portion is due to the modular arithmetic of the sub-structure,
One possible division procedure is graphically displayed in the flowdiagram of Figure 5. Some prior attention must be given to the orerations
ASD TR 61-438 114

~ cd=cd+t l A j cdto:~t
|~'' ~' "- yes
A^ Add cd 1t^ ^^ ^ 118^ <0 -a — aPfa t A Arm ta), r
A > B a a ~ a b a b
__ Add Cd -^ do0l= C-C do^ )
x=2
( Rab) cdod 0 l o " I'l (r) cdo dodi
OloO.f.
~1^~I " do - "d IOC I''
a cd- * dCheck 1 ~ If: 03/A0; stop
r6~~M3(a~~~~~b) I~~c2-0, "Hi~ c-cm, t-t-1, stop
Figure 5. DabivisicOn coo; cncmS, ttt-i, stopt
(Db ana - Cdo t tQ c, C^; c^ ^2. stop
I~ A r_; a. 3 r i~ )!
x=2
A-Bcd= r' I~j ^' " (r') i i+- C1 " cd-cdo Q
I ______, N~ x o;o.f.
*~1 - 1i1. gd * Cdtedo a i Cin R N
Figure 5. Division in the floating point RNS.

involved, and the intent of the over-all operation explained, in order that
the flow-diagram may be more easily interpreted.
Given two numbers, A and B, in the form of equation (8-35), the sign of
A/B = C will be determined, as in multiplication:
If
S(A) = S(B), S(C) = + (8-38)
S(A) # S(B), S(C) = - (8-39)
While the initial determination of the exponent (t) of C will be accomplished
as
t = r-s-3 (8-40)
and may or may not require modification in the final step of the division
procedure. This the number, C, will be represented by
S(C). I c j t (8-41)
where the box around cd(d = 0, 1, 2, 3), here and in Figure 5, implies that
the number is in the storage location reserved for that particular final result
For the calculation as shown in the flow-diagram, the signs of the numbers are ignored and the exponents are treated as though they were zero (excepting the final step). In other words, only the stems of the numbers (their
coefficients) are treated in the calculation.
The operation M3(A,B) is the step-three magnitude comparison operation
of Section 8.5. The operation M3(a,b) is a reduced version of the same thing,
ASD TR 61-438 116

operating on a pair of single coefficients rather than on two complete numbers, The A = Am operation is a single left-shift of the dividend, while
the operation a3 = a3-,ra2a is a sub-system computation to obtain the new coefficient a3o The operation, Add cd to., is understood to leave cd = 0
upon completion, R1(x) is the reduction operation of Section 8,3, but is
used only to detect overflow of the m-system in this procedure,
The multiplications used in this procedure are not the full-scale multiplications of Section 8,4, The multiplication in the) sequence involves no
carries at all and is a single-step operation involving two m-system coefficients, The (D sequence multiplication does involve carries, but it is the
multiplication of a number, B, by a single coefficient, cd, and might be
thought of as a "scalar multiplication" as opposed to the complete "vector
multiplication" described in Section 8.4.
The R3(a,b) operation is one for the selection of a reasonable first
approximation for the quotient digit. It could be done by a table-look-up
procedure; since the m-system may be relatively small, such a table could
also be of reasonable sizeo However, it can be done by a simultaneous-reduction process, the reduction being to a non-uniformly-based number system,
If a3 is of the form (0 < a3 < m)
a3 - 1 UO2 x03 O4 (8-42)
corresponding to the definition of equation (8-4), then the process
a3 - a4 - o3
P4 - d2
p3____ -- il (8-43)
P2
ASD TR 61-438 117

an operation in the m-system, must go to zero at one of the steps. If the
pair of coefficients (ai,bj; ai > bj) are reduced simultaneously, when the
b-sequence goes to zero the remainder of the a-sequence may be re-expanded
into the M-system and used as the desired approximation. If both sequences
go to zero at the same time, unity may be taken as the approximation.
The ( and () sequences of Figure 5 are used to find and improve a series
of quotient-digit approximations. The first approximation in each case is
chosen in such a way as to be smaller than (if not equal to) the correct one.
The loops increase the approximations by consecutive-integer-multiples until
overflow results, thereby bracketing the correct result. Restoration is used,
upon overflow, and a new approximation is then found from the remainder term.
The remainders are always compared with the divisor for relative magnitude
to determine the subsequent operation. When the remainder is smaller, the
correct quotient-digit is the current sum in jc.
Note that the M3(a,b) operations in the A > B portion of the sequence
show only two alternatives, because the third one (a < b) does not exist as
a possibility at that point.
The convergence of this division scheme is roughly geometric. A NewtonRaphson scheme converges nearly exponentially and would thus be more desirable. This method has been presented in the spirit that these straightforward
algorithms serve to demonstrate that the system is feasible with rather simple
operations.
8.8 CARRY-COMPLETION SENSING
There are several tools that might be of use in the carry-completion probASD TR 61-438 118

lemo For example, borrow-completion, in addition cases 2 and 4, may be sensed
by testing every cil and cio after the application of R1 (as in Figure 3).
If, for all i; cil, Cio C 0 then no further steps are necessary.
Carry completion, in addition cases 1 and 3, is aided by the fact that
carries cannot be both generated and propagated by the ith position. Obviously, if cil = 0 or 1 (for all i) the process is completed. Moreover, if
any cil = 1 (it cannot be greater) then it need not be checked further. Figure 6 is a chart specifying the situation in detail, following the additional
rule that if cil = 0, c(il) B 0 a further step is necessary.
If i equals 3 2 1 0 N
And ci equals 0 0 0 0 0 Then N corresponds to
0 0 0 1 3 the number of further
O0 1 0 2 possible steps.
0 0 1 1 2
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 0
1 0 0 1 2
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0
Figure 6. Carry completion.
The scaling operation after multiplication is not as slow as it looks in
Figure 2. It may be seen that carries occur only if m-6 n cio < m (in the
worst case) at the starred level. Under the assumption of a uniform distribution of numbers in the range 0 \< cio < m, and taking m to be 1155, this
ASD TR 61-438 119

represents less than a 1 percent probability. This may be detected by the
criterion that cil = 0 (for all i) represents completion of the scaling process, Moreover, if carries do exist at that level, at the next level Figure
6 is directly applicable to the completion problem, under a change of the
subscripts given by i = i+3.
8.9 POSTPONED SCALING AND SPECIAL PURPOSE MACHINES
The most striking characteristic of RNS arithmetic is the substitution
of the magnitude-control problem for the one of pure integer multiplication.
The first approach discussed in this chapter demonstrates how ENS arithmetic
may be used to construct a conventionally-organized machine. This means that
the machine instruction code employed might be indistinguishable from a conventional machine instruction code. The difficulties in the RNS, however,
might well demand a machine organization of a different type. The direction
of exploration here is based on the maximum postponement of the time-consuming
magnitude-control operation.
The primary characteristic of a system using such an organization is an
arithmetic unit capable of operating on longer-than-double-length numbers.
This feature permits addition and subtraction operations on a set of products
before scaling. Postponement of scaling necessitates "remembering," between
operations, which numbers have been properly scaled and which have not. The
best method of handling this difficulty depends on whether a general-purpose
or special-purpose use is intended,
General-purpose organization will require special scaling instructions,
or perhaps tag bits in the ordinary instructions, indicating whether or not
ASD TR 61-438 120

a result is to be scaled. The difficulties for the programmer, in keeping
track of magnitudes, should be overcome by the use of compilers. Such compilers initially would need information as to the possible range of all input
variables; they would keep track of each variable, inserting scaling instructions where necessary.
The postponement of scaling requires an implicit sign scheme, since signdetermination is as difficult, in general, as scaling itself. An ordinary
complement-system appears applicable to a multiple-precision RNS, with one
slight difficulty. The base-extension procedure must differentiate between
negative and positive numbers. The former must then be placed in the upper
half of the double-length system.
There are certain numerical-analysis procedures which can take quite
natural advantage of scaling-postponement. The computation of the dot-product
of two vectors is typical of these procedures. This operation occurs in relaxation methods for differential equations, in the formation of a weighted
sum of neighbors. This procedure is basic to several matrix inversion algorithms.
The design of a special-purpose machine for matrix inversion was considered in some detail during the past year. That portion of this study having
to do with organization is included here. The suggested configuration appears
to be considerably faster, at no great cost than conventionally-organized
machines. The "streaming mode" of operation, with its resulting savings in
instruction fetch, is of particular interest, apart from the use of the RNSo
In some respects this organization resembles the "Harvest" device of IBM.0
ASD TR 61-438 121

8.10 A MATRIX-INVERSION COMPUTER
The matrix-inversion problem involves little input-output data, but a
great deal of arithmetic computation. The proposed computer is capable of
handling up to 100 by 100 matrices.
In any residue machine, the digits of the residue number may be coded in
binary form. Only prospective moduli which are equal to (or slightly less
than) powers of 2 can be coded efficiently in binary form. If a sufficient
number of digits are carried throughout the computation (in this case the
equivalent of 16 decimal digits will be carried) to insure the desired accuracy, either the number of residue digits required, or the size of the individual moduli, becomes excessively large. The time required for magnitude
and/or sign determination is almost directly proportional to the number of
residue digits.
A multiple-precision system was selected as the best way to reduce the
number of residue digits and to insure an efficiently coded number for storage. Sufficient accuracy can be obtained, using multiple-precision, to carry
the equivalent of 16 decimal digits throughout the computation. The basic
machine number will consist of four base "b" digits, where "b" is 127 x 128.
A scaling factor, a, will also be part of the number. Each base "b" digit
will be expressed in a two-digit residue code, the two digits of which are
127 and 128. These residue digits are then binary-coded, using 7 bits for the
127-digit and the same number for the 128-digit. A 64-bit storage word allows
an additional 8 bits for exponent.
The problem of matrix inversion can be broken down into a series of
ASD TR 61-438 122

matrix multiplications. Matrix multiplication can be broken down into a series
of "sum of products" operations'
n
=ij " aikbkj~
f the arithetic unit e r i to compute is "s of products" opIf the arithmetic unit can be organized to compute this "sum of products" operation efficiently, it will be ideally suited for the matrix inversion problemo
In a conventional machine, a double-length accumulator is provided to
insure that multiplicative overflow does not occur, The accumulator is made
somewhat larger than double-length so that it is possible to computse the sum
of several products without overflow, To this end each base "b" digit (expressed in a 127, 128 residue code) will be extended to a 127, 128, 63, 61,
59, and 31 code as soon as it is obtained from storage, These numbers are
pairwise prime, Furthermore, their product is greater than 400 (127 x 128).
The extended-base representation of each base "b" digit will be carried
throughout the arithmetic unit, A block diagram of the proposed arithmetic
unit is shown in Figure 7.
The machine will be basically a two-address machine, The general storage is to be word organized, and divided into X and Y halves. The cycles of
the two halves can be interlaced to reduce the time required to obtain both
operands
The "sum of products" operation will proceed as follows:
i1 The two operands X and Y are obtained successively from storage.
2. Each operand passes through the base-extension unit and then to one
ASD TR 61-438 123

X Storage Y Storage
Base
Extension, X2 X3 X4 Oxp Yi Y2 Ya Y1 exp
ault. Unit _ Q)
zt zt i_ 2l
Exponent
Coaparison
Unit I I
C ~ I ControlI
0Q ^'~'^~ ___ Shift Unit
Scaling 7unt Zo Zc Zd Zs 2m ZS Zs Z, exp
Figure 7. Block diagram of a computer.
124

of the operand registers.
3. When both operands are present in the operand registers, the actual
multiplication can begin. The multiplication operation will involve forming
several sets of cross products. As each set of cross products is formed, they
are added into the Z registers through the shift unit (SU). To multiply two
numbers together, it will be necessary to form four sets of four cross products each. It is evident that in the worst case, after one multiplication,
some one of the Z registers will contain a number of order 4b2.
4. The SU is controlled by the Exponent-Comparing unit (ECU). The ECU
adds the exponents of the X and Y operands and compares the results with the
exponent already present in the Z register.
a. If the exponent already present in the Z register is greater
than or equal to that of the new product, the cross products are added
through SU into the appropriate Z registers.
b. If the exponent of the new product is greater than that already
present in the Z register, the contents of the Z register are shifted
right enough positions so that the most-significant digit of the product
will add into the Z1 position.
5. This process is continued until a maximum of 100 of these products
have been summed.
At the end of the "sum of products" operation, each of the Z registers
will in general contain a number of order 400 b2 But since the capacity
of the register exceeds 400 b2, no overflow will have occurred. Before the
result can be stored, it must be scaled so that the number in each of the Z
ASD TR 61-438 125

registers is less than b. When this condition is met, the 127, and 128 digits
will express the number uniquely and the 63, 61, 59, and 31 digits may be
dropped. The scaling operation proceeds as follows: consider the set of
digits (Zo, Z1, Z2, Z3, Z4, Z5, Z6, Z7).
ZO represents an overflow digit and will be zero at the start of the
scaling operation. Each of the Zi digits will be divided by b. The remainder
in the nth position will be added to the quotient from the (n-l)th position
and the sum placed in the nth register. The resulting number is exactly the
same as the original number except that each digit is smaller by a factor of
b. The only exception will be the ZO digit which will be larger if there was
a quotient in the Z1 position. This process is repeated until all of the
quotients are zero, at which point the contents of any digit position will be
less than b. Consider the set of digits:
Z1 Z2 Z3 -.. Z7
which are of order 400 b2 where b = 127 x 128. If Z1 is replaced by:
Ri + i.
b
Where Ri is the remainder when Zi is divided by b, and Zi-l/b is the integer
part of the division Zi-l/b. The procedure for scaling should proceed as
follows:
1. Decode each Z digit
2. Divide by 127
3. Divide the quotient of step 2 by 128
4. The quotient from step 3 consists only of the modulo 63, 61, 59,
and 31 digits. These are now extended to include modulo 127 and
128 digits.
ASD TR 61-438 126

5o The remainder of this division is taken as the number expressed by
the 127 and 128 digits before division. This number is extended to
include modulo 63, 61, 59 and 31 digitso
6. The quotients and remainders are now added.
A block diagram of this operation is shown in Figure 8o
A floating-point mode of operation has been implied in the discussion,
However, the arithmetic structure as defined will work equally well in a fixed
point mode.
Floating-point round-off may be accomplished by adding a constant K = 1/2b
into position Z5 just prior to the scaling operation. After scaling, if Zo is
non-zero, the contents of the Z registers are to be shifted right and the exponent increased by one, The four high-order digits and the exponent are then
to be stored.
8.11 A METHOD-PRECISION CGOMPARISON
In Cheney's9 procedure, the scaling is accomplished before multiplication. Because of this feature, Cheney's method is the worst in terms of precision.
If A is scaled by m1 and B by m2
A = Lklmi + JAKl = a o ml + a (8-44)
B = L2jm2 + IB~m = b_ o m2 +bo (8-5)
where
mi o m2 = m (8-46)
then
__ -ab1 anbo aob o (847)
=, a b (8-47)+
m ml m2 m
ASD TR 61-438 127

Inputs From Z - Register
Decode
112 112I
128 128
Base Ext.
B.E. B.E. r 63,61,59,31
Base Ext.
B. E. B.E.I 127, 128
Add
Encode
O utput
Register
Figure 8. Block diagram for scaling operation.
128

By scaling before multiplication only a.b1b is kept. Thus the contributions
of
aobi 1 alb~ o t E
abi m to
are lost.
In Svoboda'ts method, AB = C is completely available in the double-length
form. C is then scaled by m, with the result that
rq= _ AB]
suffers no contribution losses as above. However, it should be observed that
the comparison between the two systems does not take into account that the
Cheney method employs a single-length operand, while the Svoboda method involves a double-length operand.
The precision advantage of the floating-point system over Svoboda's method
follows from the degree to which IABIm must be discarded.
In the most extreme case, when ~ is on the order of unity, the loss
of precision in Svoboda's method can approach m/2, The corresponding worst
case in the floating-point system occurs when the most-significant coefficient
is on the order of unity, The error is then bounded by 2/m3, as was demonstrated in Section 8,4.
Certain assumptions must be made about the capacities of the systems in
order to make further comparisons. If one takes the magnitude of Svoboda's
single-length capacity to be equal to the mantissa-magnitude (approximately
m5 in Section 8.4) of the floating-point system, there exists a common basis
for comparison,
ASD TR 61-438 129

The precision of Svoboda's method will, at best, be equal to that of the
floating-point system. This occurs only when'A = 0 or X m
In the ideal case, with K]_ = 0, neither method loses any precision.
This case is one of no multiplicative overflow, and represents only 1/m of the
total number range. In the larger range, with __ = E(E # O), Svoboda's
method loses precision approximately linearly as compared to the floatingpoint system; from equal precision when E ~ m, to the extreme case (m/2 when
E A 1) described above.
ASD TR 61-438 130

CHAPTER IX
IPTLvZEi:i\TA TL>ON OF SIGN DET-ERMINATION TETHODS
9,1 INTRODUCTION
The problem of sign determination in a RNS has received a great deal of
attention, and five different met-hods have been proposed for the solution of
that problem in an efficient manner,
Efficiency here means the capability of operating in a very short time,
of the order of one or two pulse-times, and the possibility of implementing
in practice the conversion network with a reasonable number of switching elements The methods referred to are the following:
(1) Implementation of the conversion equations;
(2) Change of representation;'1
i Xx
(3) Addition of m- 1- quantities;l
mi mi mi
(4) Method of estimates;12 and
(5) Successive reductionol
These five methods can be grouped in three categories, according to the means
by which the conversion is achieved~
(a) Methods implementing the conversion equations: (1) (2)
(b) Methods using stored tatlies: (3) (4)
(c) Methods using a reduction procedure (5).
If one is interested in extreme economy of equipment, the methods under
(a) must be considered, taking into account that any gain in simplicity is
ASD TR 61-438 131

paid for by a loss in speed. In general, this method takes (n-l) pulse-times
to be completed, where n is the number of moduli used in the system.
This type of conversion procedure has been dealt with only as an elegant
but impractical solution because it has been considered that for a practical
RNS, for example one with a range equal to 230, the number of elements would
become impractically large. This statement appears in practically every paper
on the subject, and must have been suggested by a wrong association with the
idea of a decoding network in the form of a complete tree.
This type of network requires 2n1 elements for n variables (levels in
this case). In a system with a range of 230, a set of at least 8 prime moduli
is needed if small moduli are used, and an examination of the number of binary
digits necessary to encode the coefficients of the associated mixed radix
representation leads to the conclusion that the decoding tree for performing
conversion from the mixed radix to the residue system comprises 29 levels.
If this network were a complete tree, the number of elements would be
536,870,911 = 22s91.
The networks for obtaining the other residues have a progressivelydiminishing number of elements, but the number of elements in the veryfirst
network is enough to discourage any further attempt.
It will be shown that the number of elements for such a conversion is
actually very small and depends on the encoding used. For a RNS with a range
of 230 it is never much greater than 1,000.
An implementation of this method, using current steering techniques, is
given in Section 9.2, and Section 9.3 deals with the procedure for determining
ASD TR 61-438 132

the number of elements of the conversion network for the general case of
several moduli and large range.
A criterion for the choice of moduli, resulting in an economy in the number of switching elements, is given in Section 9.4o
If a very fast conversion procedure is desired, only those methods which
are inherently non-sequential should be considered. In this case only those
under (b) are capable of being implemented with a reasonable amount of circuitry,
Section 9.5 covers the application of fractional-binary-coding, to the
necessary tables for further reduction of the number of elements, at the expense of one additional pulse-time, bringing the total time needed for signdetermination to two pulse-times. This procedure, although presented as part
of an algorithm using a table of i I-rlm quantities, actually can be applied
mi mi mi
to any method using a table-look-up operation together with subsequent addition of the quantities thus obtained.
Section 9,6 explains the general structure of the network, and Sections
9.7, 9.8 and 9.9 present a systematic procedure for determining the number of
required elements without actually drawing thae network, This procedure is
based on a general algorithm for developing a carry determining network (for
any number of variables) from a smaller network that is easily drawn,
902 RESIDUE TO MIXED BASIS CONVEFSION USING CURRENT STEERING CIRCUITRY
The networks used to perform the conversion from residue to mixed basis
representation implement the equations of procedure number 1o
ASD TR 61-438 133

an = lxIm (9-1)
anl = 1 mn mnl I (Xmn-1 an) Imnl m 1 (9-2)
"m-n mi^ n-n-l in-l
an_2 =. i i - a
an-2 m nmn-2'mn-l _n-2 mn-mn_2 _ n
I- mnmn2' an-1 mn-2 mn_2 (
In general:
1 1 1
ai l= l mnimi Imn-llmi'mn-21mi Imn-1+1 mi.
iXmi - an - Imnmi an-1 - Imn * mn-1mi' n-2 - Imn mn-l'' mn-i+21mi' ai+l mi mi
If one considers the case where only three moduli are used, the preceding
equations take the form:
a3 = xlm (9-4)
a2 = M3lM2 IXlm2 - a3 m2 m295)
m3 1 Ml1
^ = ^m3 ~ lm | a3|l - ~3 lmlmi e ~m (9-6)
Each of the equations (9-2) and (9-3) is implemented by an independent network, but as an is always equal to IX mn, only n-l networks are
required.
The inputs to each network are the residues, coded as one number per
wire, therefore the number of input lines is equal to the corresponding modulus.
ASD TR 61-438 134

As an example, Figures 9 and 10 represent the conversion networks to perform conversion from the system mi: (4'3,5) to the associated mixed basis
system.
The broken line is the path of information when the number 53 in residue
notation (1,2,3) is converted to the mixed basis representation: (3,1,3).
The procedure includes the following steps, as indicated on Figures 9
and 10:
1. The input (al) is received on wire number lo
2o The first binary digit of la3m = 131 = 3 = 11 is inspected.
3. The first binary digit of lasm is subtracted.
4. The interchange of wires in this step has no arithmetic meaning.
It is only a rearrangement to simplify the drawing. Every wire retains
its original weight.
5. The second binary digit of las3m is inspected. In this
case ia31lm in binary is 11, and the second digit is also a 1.
6. The second binary digit of las3ml is subtracted. Weight = 2.
7. Multiplication by Il/ms3lm is performed. In this example
1l/ms3lm = I/51 = lo
8. The first binary digit of la2lmi is inspected. 1a2lm1 = 1.
First binary digit is 1.
9. The first binary digit of la2lmj is subtracted, with a weight
of 1.
10. No operation.
ASD TR 61-438 135

Control Signals Inpt: Ix ImxI tep' perion
lit bin. digit of lal 31 2
I's &3 3 13 1lt digit of Ia3lm
4 No operation
2nd bin. digit of 1a31 o 0 3
3a -3- 11 3 - 6 2nd digit orf Issl1
12 0 1 3
^_ __ 1_ 7 x1 1.1I
7 xlIl j3 IM 1
Ist bin. digit of tlale 0 1x i 8
|1B a 1 - 01 9 I1st digit of I&2lm1
10
2nd bin. digit of la21i 0 2d d t3 IO
l86214 - 1 = 01 12 I2nd digit of xll2
2 0 11 3
13 x 1*14 I
Otput put a 3
Figure 9. Switching network for residue to mixed basis conversion network (1st part).
136

Control Signals Input: x1 1-2 Ste a Operations
1
let bin. digit of las1m2 2
1a3I1 -- 131 o0 25X 3 -lst digit of laSlm200
h I |4 No operation
2nd bin. digit of Ia3lm2 2
=m 131= 00
6 -2nd digit of jas m2EX2
I1 0o 112
7 No operation
81 xmL ill =2
Output: a2 = 1
Figure 10. Switching network for residue to mixed basis conversion network (2nd part).
137

11. The second binary digit of la21 is inspected. 1a2lm =
Therefore the second binary digit is 0.
12. The second binary digit, with a weight of 2, is subtracted.
13. Multiplication by l/m21ml is performed: l1/m21ml = 11/31 = 3.
14. The output is al = 3.
It is to be noted that the number of levels that are necessary depends on
the number of a coefficients to be inspected, which is (n-l) for the first
network, and on the number of binary bits needed to represent the a coefficients modulo mi. As ml = 4, the largest magnitude to be dealt with is 3, and
therefore only two binary bits are necessary for each coefficient.
The complete network to perform conversion in this system is shown in
Figure 11, and in more detail in Figure 12 where the I andC] elements and
connections indicate auxiliary equipment performing notation changes, encoding
or modulo operations not essential to the conversion procedure.
The operation is sequential, that is, the coefficient as appears first
at the output; after a certain time interval a7 is obtained, and so forth,
Therefore the total delay to obtain the complete conversion is the sum
of the propagation times through the path shown as a broken line in Figure
12.
All the Ixlmi are applied simultaneously as inputs, but they are delayed
by the delay elements 3 to allow time for the modulo and conversion operations to take place on Ix ms.
After that delay, both signals, that is, the individual Ixlmi and the
corresponding setting signal for the switching elements obtained from |x m,
ASD TR 61-438 138

1XI.I X.., XIM
as
as
IX~~~~~~~~~~m~m
a2
a2
mi I I I ~~~~~~~~~~1 level of' switching elements
(a,~'kxi. 5 operation
-Q}- Binary encoder
81 ^8 "~ f^
Figure 11. Simplified schematic of the complete residue to mixed basis
conversion network.

mi = 3 5 7 11 13 17 23 31
XIml XIm2 XmS XKm4 xIm II XIm8
I C^J I C~l \^/ 2 levels of
all a \4 1 I:~~ L' r'm
47 )|2 levels of switching elem
I ___ |^J | {|- - Binary encoder
1,~ ~ ~1 13 ^a~~~~ (~ ModrI. 5 operation
Figure 12. Block diagram of the conversion network from the residue
system to mixed basis.

are applied to the first group of switching levels, indicated in Figure 2 as:. The number inside the indicates the number of levels actually comprising the group.
The output of the modulo 23 column is already a7, from which the setting
signals for the second group (second row) of switching elements are derived
by modulo and conversion operations.
Therefore, initially there are no outputs, and the ai coefficients begin
to appear successively in decreasing order until they are all available after
a time equal to the total propagation time through the chain of elements indicated by the broken line in Figure 12.
A slightly simpler network can be obtained by omitting the delay elements
# lin Figure 12; but then the output has to be strobed after a time equal to
the total delay A, because in this case there are output signals present since
the moment the Ixmi input signals are applied, but it is only after a time A
that they are all correct.
The initial values present at the output depend on the state in which
previous operations left the switching elements, and they change successively
into the correct value as the signal travels through the broken line diagonal
path of Figure 12.
9.3 NUMBER OF ELEMENTS IN A CONVERSION NETWORK
When performing conversion from a residue number representation, the number of independent conversion networks is one less than the number of moduli
of the system, because the coefficient an in the mixed radix representation
in equal to the residue x lm.
ASD TR 61-438 141

The number of input lines to the ith network is equal to the corresponding modulus mi. For example, if for a network mi = 3, the number of input
lines will be 3, because the input is ai, and this can take any value up to
mi-l; therefore the largest possible value is 2, but an additional line is
needed for the 0 (zero) signal, which brings the total back to 3.
The number of levels is the product of the number of binary digits necessary to represent moduli i the coefficients ai from ai+l to an, times the
number of coefficients to be added up, which is equal to (n-i).
The itemized calculation for a residue system with 8 moduli is given in
Table 8.
For the first network, mi = 3, and the number of coefficients to be
added is 7: a2 through a8. All these coefficients are taken moduli 3 and
therefore are represented in a binary notation by only two digits. The
total number of levels needed is therefore: 2x7 = 14
The following general formula can be used to calculate the total number
of switching elements of a conversion network for a system of any number of
moduli:
(n-l)
No. of elements = Z (n-i) x mi x F(mi) (9-7)
i=l
F(mi) is a function giving the number of binary digits necessary to represent a number modulus mi.
When operating moduli mi, the largest number that can occur is evidently
(mi-l), and for systems with a small number of moduli, F(mi) can be obtained
from the following table:
ASD TR 61-438 142

TABLE 4
TABLE OF THE FUNCTION F(mi)
Any mi up to 2 4 8 16 32 64 128
Largest No. posSo 1 3 7 15 31 63 127
F(mi) 1 2 3 45 6 7
In those cases where the number of moduli is very large, or the calculation is to be included in a program as a subroutine, F(mi) can be obtained
from the expression:
log (m~+l)
F(mi) = integer part of lg + 0o99 (9-8)
0.3010
It is interesting to note that given a residue number system and the
associated mixed basis system, the conversion either way takes the same number of switching elements, although the networks are quite different in their
circuitry, and in the time required for the conversion.
Modular system with moduli: 3, 5, 7,,, 13, 17, 23, 31.
TABLE 5
PROCEDURE FOR THE CALCULATION OF THE TOTAL NUMBER OF ELEMENTS
1.2 3.4.. =..3x4 6 7 = 5x6
1 3 7 2 14 3 42
2 6 3 18 5 90
3 7 5 3 15 7 105
4 11 4 4 16 11 176
5 13 3 4 12 13 156
6 17 2 5 10 17 170
7 23 1 5 5 23 115
Total number of elem. = 854
Column 1: network number
Column 2: mi
Column 3: number of coefficients to be added
Column 4: number of binary digits necessary to represent the
coefficients moduli mi
Column 5: number of levels
Column 6: number of input lines
Column 7: number of elements
ASD TR 61-438 143

The table beginning on page 145 gives the number of elements necessary
to implement the conversion network for different sets of moduli, all giving
a range equal or greater than a specified value. The results are a direct
application of the equation (9-7) and have been calculated for values of M
27 34 27
from 22 through 2. Only the table for 2 is included here,
For the calculation of these tables, the first 400 prime numbers, excluding 2, have been considered as numbered from 1 to 400. Therefore, the
numbers in columns 1 and 2 identify the first and last moduli of the set by
their ordinal position; ioe, 3 indicates the third prime number, that is 7o
The tables contain the following information:
Column 1: The first modulus.
Column 2: The last moduluso
Column 3: The number of moduli in the set.
Column 4: The actual range obtained, in floating point notation.
Column 5: The number of elements in the conversion network.
Column 6: The number of elements normalized for a range of 101~.
Column 7: The minimum range, in floating point notation, as prescribed in the program.
The same type of information is presented in Figure 13, beginning on
page 146.
Here only the first and last moduli are indicated, together with the number of elements. The length of the lines of 8's in the scale indicated, is
proportional to the number of elements.
ASD TR 61-438 144

TABLE 6
NUMBER OF ELEMENTS IN THE CONVERSION NETWORK FOR DIFFERENT SETS OF MODULI
nrt $IadulMw tat Modulus uv&*r of Bange Number of Rmber of Elements
Pri No. Prim o.e. oduli Obtained Elements for a Ranu - 10~O 2
~ ~) ~ ~~' ~ 9 7 215656239 1114 51(56 134217759
4 10 7 955048459 1524 15957 154217759
6 11 6 247110459 1595 64546 134217759
7 12 6 959971659 1902 51914 134217759
8 13 6 134877760 2310 17126 154217759
9 14 6 275619560 2761 10017 13421'759
%1 15 5 1(2489759 2424 149178 134217759
12 16 5 259105159 2(40 101889 154217759
13 17 585497559 2868 73597 134217759
31 18 5 60065559 15242 1'4217759
15 19 5 907376959 3555 58958 1'L21775,
16 20 5 124978260 3949 31597 1542177517 21 5 17343660 45376 26149 144217759
18 22 5 227696860 4942 21701 134217759
19 23 5 302462760 5208 17218 1',217759
20 24 5 413223560 5488 13280 13521775;
21 23 5 571720060 5880 10284 13421775 9
22 26 5 745406960 (258 8'95 1,421775,
23 27 5 960945460 6664 6934 1'L217759
24 28 5 117688661 7028 5971 1 4217159
26 29.4 135743659 3879 285759 1-421775;
27 30 4 167373059 5474 2075(0 154217759
28 1 4 204914459 3125 152502 134217'59
29 32 4 257552659 5199 2018(1 154217759
30 33 4 316812259 5859 184936 17x217759
31 34 4 371692699 6448 173476 134217759
32 359 4 428439559 6704 15(474 14721477
33 36 4 490985159 6928 141104 1!:-21779
34 37 4 575759259 7248 125885 1'-21'759
39 38 4 645313759 7440 115292 1'21-75
36 39 4 739332659 7386 99900 1,-217759
37 40 4 804900059 7968 94507 1~217759
38 41 4 936017299 8208 87690 13-217759
39 42 4 107093460 8464 79063 114217759
C 43 4 119429460 8720 73013 1i4217759 9
4. 44 4 131439060 8944 68046 154217759
14 45 4 144510260 9248 63995 13421779
43 46 4 159642160 9376 58731 134217759
44 47 4 184456960 9600 52044 154217759
45 48 4 212546760 9936 46747 135217759
46 49 4 244588660 10118 42716 1354217795
47 50 4 270090460 10616 40045 154217759
4 51 4 289468860 10976 37917 134217759
49 52 307321260 11136 36235 134217759
50 53 336845060 11344 33677 134217759
1 54 3 71541260 11600 31221 154217759
52 55 4 408850460 12113 29626 134217759
56 45 16351360 13017 28524 134217'59
57 4 492713760 14094 28604 15217'?
58 1 531056760 1438 27081 17.421.759
56 59 5 67402260 1463 25791 154217759
57 60 4 596931960 14832 2487 14217759
sS 61 4 645390860 1908 2335571 1217759
39 62 4 715288360 15318 21415 151217759
60 63 4 791653160 15678 19804 15-217759
61 64 4 875573360 16236 18543 134217'59
62 65 4 947292060 16704 17633 134217-59
63 66 4 102134761 16884 16531 134217759
64 67 4 110673161 17136 15483 121779
65 68 4 122694961 17550 14303 15421779;
66 69 4 135080461 18126 13418 154217759
67 70 4 144058461 18486 12832 13421759;
68 7. 4 154162661 1882 12268 134217759
69 72 4 162307661 19006 11711 13-21-59
70 73 4 173469061 19296 11123 15221,5
71 74 4 186245561 19656 1093 1; 217799
72 7 4 198696261 20034 10082 1' 217759
73 76 4 210606961 20340 9697 1-h21'759
74 77 4 224157961 20628 9209 1"42177?=
7 ^78 4 237169661 20916 8819
76 79 4 253269661 21278 8393 1P2-'5
77 80 4 27281861 21618 7924 1:21-'5
78 81 4 289293561 21960 7590 1 2 -
79 82 4 310936161 22374 7199. 217159
So 83 4 3291816610 6917 21
84 4 3447894261 23062 6675 1 -21"
^82 854 362917061 23382 6442 5'
83 86 4 37807361 23580 6256 1' 21";9
4 87 4 399028861 2368 981 14217759
85 88 e~ ~4 4 19025563 24156 5764 15-217759
86 89 1* 437943061 24498 5593 1,421-'5
87 90 4 45549461 24804 5445 1-4211" 9
88^~ ^^ll^7896 4 147'7426861 24964 55 12179
69 92 4 904352361 2210 5000 152P7
90 93 4 548522361 25614 4788 154217759
91 94 4 571500661 26118 4570 154217759
92 95 4 60013461 26478 441 151217759
91 97 4 66561)63.^ 271076 407 1321779
93 28 t r18683659 14372 1036313 134217779
^ ^ ^ 1708579 15650 1061720 1?4217759
~10541 114217759
988558 15421"779
1]0

Number of elements
Scale: 1000 ele/cm
Last modulus,
prime No.
First modulus,
prime No. 1114
3 9 lll4
4 10 1524
6 11 1595
7 12 1902
8 13 2310
9 14 2761
- 1 —-lst type 11 15 2424
12 16 2640
13 17 2868
14 18 3156
0\^~~ 1^~15 19 3535.\^0~~~ \16 20 3949,\^0~~~ \ 17 21 4376.0^~~ \ ~18 22 4942. 0~~l\ 19 23 5208.\^0~~~ \20 24 5488
21 25 5880
22 26 6258
23 27 6664
24 28 7028
^~- 1st type 26 29 3879
27 30 3474
-1 ~ 2nd type 28 31 3125
29 32 5199
30 33 5859
31 34 6448
32 35 6704
33 36 6928
34 37 7248
35 38 7440
36 39 7386
37 40 7968
38 41 8208
39 42 8464
40 43 8720
41 44 8944
42 45 9248
43 46 9376
44 47 9600
45 48 9936
46 49 10448
47 50 10816
1 2 3 4 5 6 7 8 9 10 11 12
Figure 13. Variation of the number of elements in the conversion network.
146

8 6151 1097684
9 62 111536
~~~6o0~~~~~~~~50 63 15678
2 12111 64 162600
62 65 16704
63 66 1688401
64 67 17109
65 68 17550
66 69 18126
67 70 18486
68 71 108828
69 2 19008
70 73 1929678
71 74 1966 6
62 65 16704
63 76 2016840
74 77 171320628
75 78 20916
76 79 212586
77 0 2161886
78 1 219608828
79 82 19008
0 3 2277096
81 4 196022
82 85 2003382
83 86 2580
84 87 20868
85 88 24156
76 79 24498
87 90 24804
88 91 2498460
89 92 252187
80 93 225614
81 94 20226118
92 95 26478
83 86 2676680
94 87 2710868
85 88 24156
86 89 24498
96 98 148072
88 91 24984
89 92 25218
97 99 15614
91 94 26118
92 95 26478
93 96 26766
94 97 27108
96 98 14372
98 100 15870 1st type
99 101 16290
1011 12 15 4 15 16 17 18 19 20 21 22 3 24 2 2627
Figure 13 (Concluded).
147

9.4 SELECTION OF MODULI FOR MAXIMUM ECONOMY
It is evident that some combinations of moduli require a minimum of elements, and that two types of relative minimums can be distinguished:
One type is produced when the number of moduli in the set drops by one,
because as larger moduli are considered suddenly the range can be obtained
with one less modulus,
The second type occurs even when the number of moduli remains constant,
and is produced when the nth-l modulus takes the largest value not exceeding
one of the following magnitudes: 2k-1. That is when the nth-l modulus takes
the maximum value less than or equal to: 3, 7, 15, 31,....
This can be explained in the following way: The nth modulus does not
influence the number of elements because it gives directly the last coefficient in the mixed radix system. When the nth-l modulus takes for example
the value 15, it is possible to encode it using four bits to full capacity.
If the modulus were 16, it would be necessary to use 5 bits and therefore
five levels of switching elements.
The rest of the moduli are also encoded in the same number of bits or
in less, because they are all smaller than the nth-i.
In the graph for a range of 227, the first type of minimum occurs for
the sets having the following first moduli: 6, 11, 26, 96. In those cases,
the number of moduli is reduced by one.
The second type is evident in the set having prime number 28 as the first
modulus. This set is composed of the following primes: 109, 113, 127, and
131. We see that the nth-i modulus is 127, which is the maximum value representable by 7 binary bits,
ASD TR 61-438 148

9.5 THE APPLICATION OF BINARY CODING TO CONVERSION PROCEDURES USING STORED
TABLES
One of the procedures used to obtain the mixed radix coefficients corresponding to a given residue representation consists of the addition of the
1 x
corresponding values of the quantities 71 in mixed basis notation.
This procedure requires the storage of n tables, n being the number of
moduli in the system. Each table contains the values of Ix for all posmi mi mi
sible values of 1Ximi, expressed in mixed basis notation.
From these tables one obtains the mixed basis coefficients corresponding
to each of the residues. They are added in a modular adder, taking into account the carries that may occur.
The main disadvantage of this method is that it reintroduces the problem
of carries. But when the problem is sign determination rather than change of
representation, the method can be modified to perform the determination of
sign in only one pulse time, assuming that the corresponding quantities have
already been obtained from the tables.
This modification is based on the fact that when a number x is represented
as:
1 x
x = M - Z -j-I
mi mi mi
where M is the range of the system, the summation takes values less than 1/2
for the first half of the range, and values greater or equal to 1/2 for the
second half. Now if the quantities stored in the tables are represented in
binary form, it is not necessary to perform the actual addition of all the
quantities, but only the determination of the first binary bit after the decASD TR 61-438 149

imal point. If this is a zero, the summation is less than 1/2 no matter what
the other bits are. If the first bit is a 1, the sum is always equal to or
greater than 1/2o
When all the quantities have been obtained from the tables, the carries
are determined for all the columns except the first one, and the resulting
carry is added to the digits of the first column.
For example, if the (2,3,5) modular system is used, the corresponding
tables, expressed in binary notation, are as follows:!'l2xl 3 3 1 13 xl 515 5
0 00000 0 O00000 0.00000
1 10000 1.01011 1.00110
2.10101 2.01101
3. 10011
4.11010
For x = 16, residue representation is (0,1,1), and from the tables we obtain:
For 0.O 0 0 0 0
For 1.0 1 0 1 1
For.0 0 1 1 0
1 O 0 0 1
As only the first digit after the decimal point is to be inspected, the
complete sum is not needed, It suffices to determine the carries up to the
first column, and then to add the last carry to the first column.
This simplification makes it possible to perform sign determination in a
single pulse-time using a current steering network, because the necessary setting signals for all the levels are available at the same time, and there is
no carry propagation problem,
ASD TR 61-438 150

9.6 GENERAL STRUCTLURE OF mTHE:NEWORK
The switching network fur carry deternination is very simnple because it
does not have to handle largce numbers since te l largest carry for a sum of N
binary numbers is N-i, which happens only after several columns have been
added.
For the first columns' the network has to handle carries of increasing
magnitude. This necessitates an increasing number of wires to represent the
carries, but after the maxnimum value of the carry has been reached, the complexity remains stationaryo Thnen the same type of circuitry is repeated for
the following columns,
Three well defined regions can be distinguished in the network. This
begins with a single wire representing the original "zero" carry into the
first column from the right. In the first region where the number of values
that the carry can assume keeps growing, the individual networks representing
the columns are all different, because the possibility of carries of larger
magnitude demands more wires for their representation. This region ends with
the network corresponding to the columnn where the carry first assumes its
maximum value: N-I.
The second region is foDrmed by a number of networks' all alike, corresponding to the solhumns up to and including the next to the last, for which
the same number of values are possible for the carries'
The third region comprises only one network in which the resulting carry
from the previous columns is added to the binary digits of the last column0
The result is interpreted as (+) if it is a zero, and as (-) if it is a one.
ASD TR 61-438 151

Note that the networks in regions 1 and 2 perform binary carry determination, while the network of region 3 performs binary addition.
The configuration of the sign determining network for the example of Section 9.5 is shown in Figure 14.
A simplified network for the case where 4 moduli are used is shown in
Figure 15.
9 7 DETERMINATION OF THE NUMBER OF ELEMENTS OF THE NETWORK
The three sections of the network, as described in 9<6, contain four different types of individual networks:
Region 1: The first network is of the type (1-M), indicating that
it is of the type having only one input and M outputs.
From the second network on, only the type (M-M+W) occurs,
indicating a network having more output wires than input
ones o
Region 2: All networks are of the type (M+M), that is all have
equal number of input and output wires,
Region 3: The network is always of the type (M+2)
Each of these types of networks requires a separate calculation to determine the number of elements necessary for its implementation.
Networks of the first type (11+M) are the most difficult to evaluate because they are asymmetric and include many cases of "don't care" conditions,
which tend to simplify the network but introduce difficulties for the systematic determination of the number of elements,
ASD TR 61-438 152

O carry
last bit
1st row
2nd row
slt column
3rd row
0 1 Carry from 1st column
3 similar
networks
o 1 2
bin, addition
l /
Figure 14. Switching network for sign determination for a residue system
with 3 moduli.
153

Carry Wires e of
Network Regions
0 1
35
0,1,2 3
34*4
/ \ 3
0,1,2,3 I 4
4
444
A \
01,2,1 4
~~44with 4 moduli.
4
4
0,1,2,3 4
4+2 3
2
0 1
Figure 15. Block diagram of sign determination network for a system
with 4 moduli.
15k

The following is an explanation of a procedure by which the number of
elements can be determined for any number of variables (levels) without actually
drawing the complete network.
Figure 16 shows the carry matrix and the corresponding network for the
case n = 3, while Figure 17 shows the case n = 4,
It can be seen that the carry matrix for the case of four variables can
be thought of as being formed in the following manners
11 1 1 1. 0 0 0 0 0
0 0 l- Carry.
Carry.lo'C1 Co matrix
n=-2* Ln=2i for n=3
The asterisk (*) in the carry matrix of 2* is just a symbol to indicate
that the matrix is derived from the matrix for n = 2 by interchanging l's and
O's in the first row.
The corresponding diagram in network form, for the previous diagram can
be indicated as; ~
{Cox*1&ys1
n=2* n.L2
The procedure can be extended for a larger number of variables, and the
general structure of the network for the first column is indicated in Figure
180
ASD TR 61-438 155

n00111
110100
1 0 EE 10
1 0 0 1 1 0 I
0
E = either 0 or 1
Figure 16. Carry matrix for three addends and
corresponding network.
n= 4
000000 1 111 1
000111 000111
110100 100110
1 0 E E 1 0 E 1 0 1 0 E
100110 110211
Figure 17. Carry matrix for four addends and
corresponding network.
ASD TR 61-438 156

K-1
K-2
I K-3
(K-3) Branches
I s
2
2*
Figure 18. General structure of the carry determining network
for the first column of K binary bits.
The number of elements in this network can be obtained from the following table:
TABLE 7
NUMBER OF ELEMENTS FOR NETWORKS OF THE TYPE (l+M)
Output wires, No. of levels = Number of
M No. of moduli, N elements
2 3 4
3 4 10
4 5 21
5 6 43
6 7 87
7 8 175
8 9 351
ASD TR 61-438 157

For values of N = 6, the following formula can be used:
Number of elements = 17 x 2(-5) + 4 x 2(N-6) + (N-i) + 5 x (N-6) (9-9)
Second type: Networks of the form (M-M+W) o
These networks implement the carry determination procedure from the second
column up to and including the column in which the carry assumes its maximum
value.
The number and type of networks that are needed in each case can be determined from the following table, which gives the maximum carry from every column
and at which column the carry stabilizes at its maximum value of N-1.
TABLE 8
MAXIMUM CARRY AND CARRY PROPAGATION LENGTH
No. of binary bits Max carry from column Max carry at
in a column to column column No.
2 1 1 1 1 1 1 1
3 1 2 2 2 2 2 2
4 2 3 3 3 3 3 2
5 2 3 4 4 4 4 3
6 3 4 5 5 5 5 3
7 3 5 6 6 6 3
8 4 6 7 7 7 7 3
9 4 6 7 8 8 8 4
10 5 7 8 9 9 9 4
It must be remembered that the table gives the maximum carry, not the
number of wires, which is one greater.
Figure 19 shows the corresponding network for the case (2-+3) for 3
levels,
Figure 20 shows the network for the case (3+4) for 4 levels. The
ASD TR 61-438 158

0 01
2+3 type for
levels
00 1 2
Figure 19. Carry determining network
for the (2 to 3) case.
O0 1 02
0 ~1 2 13
Figure 20. Carry determining network
for the (3 to 4) case.
ASD TR 61-438 159

preceding table indicates that for 4 levels, that is four binary bits per
colu mn, the carry from the first column into the second is a 2. Therefore the
network for the second. coiJmmn musst have 3 input wires (for the values 0,1,2)
and 4 output wires (for the values C0 1,2,53). Therefore the network of Figure
20 represents +the second network for the case n = 4,
Number of elements:
The n-urer of eoments ef a network of the type (MI+N+W) for N levels depends only on M a aNrd is calculatfed by means of the following formula:
Number of elements:
M+(+l) + (M-2) +....+ - (9-10)
Third type: Networks of the form: (-MM).
For this type of network, the same formula (9-10) applies.
Fourth typeF Networks of the form: (M*2)o
This network performs binary addition, but no carry read our wires are
needed, because only the resulting digit is inspected,
The number of elements is determined by applying:
Number of elements:
M + (iH+l) + (M+2) +.o..+ (M+P-l) (9-11)
9.8 THE N:ECESSARY lTi MER OF BINKARY BITS
In order to attain the required discrimination between the positive and
negative regions, it is necessary to determine the number of binary bits of
the m-alx quantitieso At the samle time, it is convenient to use the minimum
D mi43
ASD TF 61-438 160

possible number of bits in order to save space in the tables, and to economize
in equipmenrbt
The necessary discrimination is 1/M. In the worst case, two representations may differ by only one bit in the last place. The weight of this bit
is 1/2, where k is the numfber of bits in use.
Therefore k is the number of bits that produces a suitable discrimination, and must satisfy the relation: 2k M.
This number of bits insures an adequate discrimination in all cases, but
when maximum simplification is desired, it is possible to obtain accurate sign
determination even when several of the final bits are dropped. In that case
the magnitudes are represented only approximately, but the sign is still correctly determined. The following considerations apply:
In a RNS, using 2 as one of the moduli, the representation for the first
number of the second half of the range is always:
(1; 0; 0;....o0)
Therefore, the summation of the quantities from the tables is always
equal to 1/2 for this number, no matter how many digits there are in use. If
the following numbers are also represented with less than k bits, their magnitude will be represented only as an approximation. But as long as the summation results in values of 1/2 or greater, the sign determination procedure
will continue to operate correctly.
As an example, let us suppose k is being determined for the system (2; 3;
5), Here M = 30, therefore k must be 5, because 25 = 32 which is greater
than 30.
ASD TR 61-438 161

But it is possble to use.nly four Mits in the table and still obtain
correct s:ign determinat' 5io The foll.owing approximate representations are
ia'uiaa...ed using the ta.l. on page 150,'but considering only four bits:
AA 5/16
5/16
First half 12 6/i6 < /
cf "-,he range 13 6/i6
84 7/16
16- 8/16
Seco rd half 17 8/16 > 1 /2
of,thAe range 18 9/16
19 10/16
20 o1/16
9.9 SYSYTEAT IC PROE4i RE FOR I 5E DEVELOP MENT OF TIE NETWORK AND 1FR THE DETERMINATIEO"N OF IHE tiER OF ELIIO ENT'S
The onl.y data availabl are tehe set of moduli in the system. The following steps should be follow^ed, as illustrated in the next exampleo
I.: Draw the schematic of thte network, as in Figure 21, with as many \
(indicating individal networks) as thee numnber K of binary bits used in the
tables of the ~-~ i quantities~
"ni mi
2, Determine te iequence of maximum carries from Table 8 for the number of moduli used in the systemo
3o Write eor the left- side of the network the sequence of carries and on
the right side the samre rzmbers increased by one, indicating the number of
wires
4o Identify and separate the three regions in the general network,
50o For the first network, o. tain the nrumber of elements from Table 7,
or apply equation (9-9) O
ASD TR 6 i-48 162

Number of
Network Carries Wires elements
Number 0 1
1 43
4 5
1st region
2 62
6 7
3 77
_.. _ _, _ _ - _ _
7 8
7 1 8
4 84
2nd region
(18 levels)
21 84
7 8
22 92 13rd region
0 1
Total number of elements: 1786
Figure 21. Determination of the number of elements in the carry network.
163

6, Calculate the number of elements for the networks in the rest of
region I and 2, using equation (9-1C)o
7 Det eriine the number of elements for the network in the 3rd region
using equation (9-11) o
8o Add the partial results obtained in steps 5, 6, and 7, The number
of terms to be added is equal to the number of individual networks,
Example~ Given the system: 2, 3, 5, 7,, 1 11 1 17 23, draw a diagram of the
general network and determine the number of elements.
The nYumbers on the left side refer to the steps of the preceding procedure,
1i Number of bits in the l- quantities K = 22o
2. Sequence of carries for n = 8: from the Table 7, we obtain: 4, 6,
7, 7, 7, 7 oooo
3o This sequence is written on the left side of the network, and on the
right side the same quantities appear increased by one,
4I The three regions are separated by broken lines,
5~ From the Table 7, for M = 5, the number of elements is found to be
435
6, Applying equation (9-10), we obtains
For the 2nd net4work: 5+6+7+8+9+10+11.+[12/6] = 62
For the 3rd networks 7+8+9+10+11+12+13+[14/2] = 77
For the 4th u.p to
the 21st network: 8+9+10+l+12+1 3+1+4+[15/2] = 84
7o For the 22nd network~ 8+9+10+11+12+13+14+15 = 92~
8o Adding the partial results of 5, 6, and 7~
43 + 62 + 77 + (18 x 84) + 92 = 1786
ASD TR 61-438 164

APPENDIX I
THEOREMS ON THE GENERATIO:N OF SEQUENCES OF RELATIVELY PRIME NUMBERS
Theorem Io Given an ordered monotone sequence of positive and negative
integers for which the difference between successive numbers is +~. If there
exists one number in the sequence divisible by Pm then the maximum length L
or a subsequence of numbers not divisible by Pm is L = (p,) - 1; note
(Pm,5) = 1 or P
Proof: Given pmlea then the next number divisible by Pm is,
3 = Kipm + aS = K2Pm
(kl-k2)Pm + ab = 0
(klk2) -P + a = 0
(k1 (Pm ) (Pm,)
Hence a = and there exists m numbers between a and 5,
(Pm,6) (Pm, )
Corollary: If one element of an ordered sequence of constant difference 6 is
divisible by Pm then the length of the maximum subsequence containing only
2Pm
one number divisible by pm is 1: = m) - i.
Theorem II. Given a subsequence of length 2pm-1 of the form a-(pm-1),.o.,,... o, +5(pm-l) There is at least one number divisible Pm.
Proof: l~aSKpm assumes all values between C and pm-l as k goes from zero
to Pm-1.
Corollary: If Pm65 in the subsequence of length 2pm-l then two numbers of
the subsequence are divisible by Pm.
ASD TR 61-438 165

Theorem IIIo A necessary condition for a relatively prime sequence of
numbers of length Lm = P = = 1; (pm, ) = 1 is that no number of the sequence
(Pm,'6)
is divisible by a prime less than Pm'
Proof: Assume PnKl pn < pm; then it follows from Theorem I that the length
of the subsequence including two numbers divisible by p is Ln= 1.
= (Pn,)
The length of the subsequence including 3 numbers divisible by Pn is Ln3=
2Pn + 1o Both Ln2 and L3 Lm
(Pn, 6)
Lemma I: Let P? > Pm divide one number of the subsequence of length L = 2pm-l.
pi never divides 3 numbers of the subsequence if (p~;6) = l1
Proof.
2p~ + 1 > 2pm - 1
Lemma 2: Let p > pm divide one number of the subsequence of length L = 2pm-l.
The subsequence is partitioned into two parts a-6(pm-l),.o. a and aea-6,...
a+6(p-1l), where pm{ca. Neither part has two numbers divisible by pi if
(PI,6) = I"
Proof:
p~8 > (Pm-1)8.
Theorem IV. If pI > p divides one number of the subsequence of length
L-2pm-1 then the necessary condition for the division of two numbers in the
sequence by p is
P~- + 2 4 2Pm
(Pl5) Nm
The sufficient condition is either
PA
+i < Pm
ASD TR 61-438 166

or if (P,5) = 1 then integers k1 and k2 must exist such that
lk2 = ipp k2 <p <Pm -
kl5,p _ P= llp kL7 P-1
Corollary 1: If p~ > p divides one number of the subsequence of length
L-2pm-1 then a sufficient condition that only one number of the subsequence
is divisible by pf is
~ 4+ 2 > 2p
Corollary 2; A sufficient condition that only one number of the subsequence
of length L = 2pm-1 is divisible by pj > pm for the case pQ+2 < 2Pm; (6,p2) =
(8;Pm) = 1; is
i1 0, 181,o0.I(PQ - Pm)FIp
or! - 1(PQ 1)5 1p2,~*D9lp IPm6 lpI
Theorem V. The necessary and sufficient conditions for a relatively
prime sequence of length L = pm-l cf the form a-6(pm-l),OoO,.,ooa+(pm-1)
are
lo (p5,6) = I
2. Pm I
3. for all Pi < Pm PiX a and (pi,5) =Pi
4o for all p~ > Pm satisfying p9 + 2 < 2Pm
ASD TR 61-438 167

185p = 0, 151 o (P- Pm)51 p
or
MiP = (P 1)5 p l, Pi
Proof:
i Ooroll ary, heorem I
2o Corollary, -Theorem II
35 Pi/yx follows from Theorem IIT
(Pi,5) = Pi follows from the fact that
ISKIp for k = C0, 1, 00, Pm-1
assumes all values of Pi is 6 is not restricted and hence for
some k,, cx~kl61 = I o Theorem III states that if one k exists
satisfying aL~k6l = 0 than a second k also exists.
40 Corollary 2, Theorem IVo
Corollary: A relatively prime sequence meeting the conditions of Theorem V
may be modified by the multiplication of one and only one number in the
sequence by each of the pi, i < n, without destroying the relatively prime
relationship between the numbers in the sequence
Example: Pm = 5, a = k5, 5 = 2o3 = 6, 2pm-2 = 8 so p~ = 7 and 1a17 = 0, 6,
5, 1, 2o Thus, suitable a's are 25, 55, 5, 85, 65, and the resulting sequences of relatively prime numbers are:
II, 17, 23, 29, 35^ 41, 47, 53, 59
31, 37, 43, 49, 55, 61, 67, 73, 79
-19,,13 - i 53 11 17, 23, 29, etc.
A choice of a such that ja17 = 3 or 4 or a such that Pi Ol, i < n results in
a sequence of relatively prime numbers shorter than 9, consider cx = 25,
-5 i 7, 13, 19, 235 31 37 4 49, 55
ASD TR 61-438 168

FAPENDIX -.I
A MIXED BASE AND MODULAR COMPARISON
The following theorem specifies the conditions that, must be satisfied
for a number S to have identical mixed base and modular representations,
Theorem Io Let p!, P2o.o pSP bee the bases of a modular number system
of total modulus p =- p1pp3. p aird Lep^ the nmodular representation of a number S be given byo
S (aia2a3~ *.a) a9 - S mod pK 0 a ak PK -
Let the mixed base representationx of S be given by:
S = hbo2, obN
where
S = b1 PN1 bP2 +.bN N b1p +
and
PTNK P= PN-.1P- 2' ^ P K+ ~
S has identical mixed base and modular representations if:
ak = bk, K 1, 29,.. \T
Then S has identical mixed base and modular representations if, and only if,
S —-_ —- is an integer
P K 1, 2,...- ~
ASD TR 61-438 169

Define the quantity tNK:
S
s PNK=
NK = PK K = 1, 2,...,N-1
Now since aK = bK only when tNK is an integer, the following theorem relates
to the number of integer tNK's which appear as S goes through the integers
1, 2,,.,p and K is fixed.
Theorem II. As S goes through the integers 1, 2,,,,,p, the number tNK,
given by:
S PNK
tNK -
PK
assumes the value of all integers l,2,...,(plp2p3...pKl)(pNK- ) at least once
and at most twice.
Proof: Examine the quantity
A = S -
For
0 S < PNK, A = S
For
PK S < 2PNK, A = S-1
and in general
aPNK S < (a+l)PNK, = S-a
It is easily seen from the above that as S goes through the integers 1, 2,..,
bpNK, A goes through the integers i, 2,...,bpNK-b. Therefore, as S goes
through the integers 1, 2,...p and since p = (P1p2P3..PK)(PNK) A goes
ASD TR 61-438 170

through the integers 9 2o o o P o ~P ) P; o
Now N( =./p r henie. it, fol-.ws th.iat as S goes through. the integers
C- 9,0p0 tTJ( asstiem: i;nter values at least
_PP~PK- K< times
PK
or tNK assumes every'iteger.i ) ~o oo( poip..)(p-.) at least ornce as
S goes throukgh -ihe hintegers i. 20ooo po
Now examinre the case of two irtegers S1 and S2 vhere 1, S1 < 32. p
to see under -what conditions their respective tNK'S are the sameo
Let 1 < SI < S2 ( p where Si and S2 are integers If tK for S1 equals
tNK for S2 thetn
Si- S2 2
Si~ ~ S2PK PK
(2-1)
S - = S2 - J
Let
~| = and
and
PNl i = a2
Then
S1 = a1PNiK r, 0 < r1 P K - 1 (2-2)
S2 = aPNK "r2, O r2 < PN K (2-3)
ASD TR 61-438 171

Further more, since S1 < S2, this implies a1 -< a2. Substituting a1 and a2
into equation (2-1) gives
S1 - al = S2 - a2
S2 - S = a2 - al (2-4)
Using equations(2-2) and (2-3) to develop an expression for S2-S1 gives
S2 - Si = (a2-al)pNK + r2 - rl (2-5)
Equating equation (2-4) and equation (2-5)
a2 - a = (a2-al)PNK + r2 - ri
r2-r1
a2 - a1 =
1-PNK
Now a2 > al implies a2-al > 0. Furthermore, since a1 and a2 are integers,
a2-al is an integer. If all the bases are greater than one, pNK > 1 and
1-pNK < 0. Thus r2-r1 < O. Recalling the restriction on the range of r1
and r2 from equations (2-2) and (2-3) it is seen that in general 1-pNK r2rl pNK-1. In this case r2-r1 must satisfy the additional conditions:
(1) r2 - rl < 0
(2) 1 - PNK must divide r2-r1. This leaves only two allowable
choices of r2-r1:
Case (1) r2- rl = 0
Case (2) r2 - rl = 1 - pNK
Case (1): Let r2-r1 = O, then r2 = rl and a2-a1 = = 0 thus for Case
1-PNK
(1) r2 = rl and a2 = al.
ASD TR 61-438 172

Now since
S1 = alPNK + rl
~ > Si = S2
S2 = a2PNK + r2
But S1 = S2 contradicts the original hypothesis that S1 < S2. Therefore,
r2 - ri O.
Case (2): Let
r2 - r = NK
then
1-PNK
a2 - a1 = r = 1!-PNK
By equation (2-4)
2 - S1 = 1
Now if
r2 rl = - PNK
r - r2 = PNK -
Recalling the limits on r1 and r2 it is seen that
ri = p -l
"r- PNK
r2 = 0
Hence,
S1 = aPNK +PNK 1
S2 = (al+l)PNK
when tNK for S1 equals tNK for S20
ASD TR 61-438 173

It has been established that two integers S1 and S2 will have the same
tNK for some 1 ( K < N-1 when S2 is a multiple of PNK and S1 = S2-1. Now
assume that there is a third number, S3, which has the same tNK as S1 and S2.
Since S is always and integer, it is clear that if such a S3 exists it is
either less than S1 or greater than S2. If S3 is less than S1 it can only
be S1-l. If S3 = S1-1, then to satisfy the conditions already established
S1 must be a multiple of PNK. But S1 (pNK-l)mod PNK which is a contradiction. Furthermore, if S3 > S2, then S3 = S2+1 and S3 must also be a multiple
of PNK Now since S2 is a multiple of PNK, S3 = S2+1 can only be a multiple
of PNK if PNK = 1. This contradicts the hypothesis that pNK > 1. Hence, no
such S3 exists.
In summary, it has been shown that as S goes through the integers 1,
2,...,p, tNK assumes integer values at least (P1P2. PK-1)(PNK-1) times and
further that no more than two numbers have the same tNK. Hence, the theorem
is proved.
Define MNK as the number of integer tNK for some fixed K as S goes
through the integers 1, 2,..,p. On the basis of the previous theorem we
can say that
MNK = (P1P2~ PK-I)(PNK ) + mNK
where mNK is the number of integer tNK which appear twice as S goes through
1, 2,...,p
ASD TR 61-438 174

It has been shown that, tNK wli.l be the same for two numbers if they are
successive and if PNK divides the greater oneo Note that tNK in this case is
not necessarily an integero As S goes through 1, 2, ooop there will be P/PNK
integers which are multiples of pTK.
Now examine t wNK when S is some multiple o of PNKo
NNK
"PPW, 1; ( PNK-1)
NK PK PK
It is clear that if pK PNK1) all. NK for S = cPK will be integerso Since
there are P/PNK = PP2o ~ PK multiples of PNK' MN = PP2~ ~oPK and K (lp
O.PKl1) (PNK1) +,pp o p-)1, NK = (PiP2 PKi) (PNK+PK-1), Pklj(PmNKl)
For the case pKX(p.-l), tNK will be an integer only for those values of c
For he cse K (_P\PN1) - K. ~\K
which are divisible by PK and there will be PIP2 ~PK of theseo
PK
-.K = (P1P2 - PKA-l) PK X (PNK 1)'\NK = (PiP2.PK-9i)NK 1) (P1P2 00PK lK
- (pi2o - PKLI) (PNK) PX K(K 1P )
Given some set of bases PP2P3pso.PN, +the set M.N1, M27 M 11N3,~...T can be
calculated. The number of identical mixed base and modular representations
of integers S such that I < S < p cannot exceed the minimum MNK
Example:
P1 = 3, P2 = 5, P3 = P4 = 11
P = 11, P = 711 77, 775 = 385
7 Xl l -i M4s = 355o1 = 165
5X77-1i M42 = 3o77 = 231
3 1 385-1= i = 385+3-1 = 387
ASD TR 61-438 175

min MNK = 165. The actual number of identical elements = 27. Although the
minimum MNK does provide an upper bound for the maximum number of identical
mixed base and modular representations, it is a poor estimate of the actual
number. Furthermore, to determine the maximum number of identical elements
for all the N: mixed base systems associated with N bases requires (N-l):
computations. The MNK function does give some insight into the problem of
choosing the bases to achieve the maximum number of identical elements, Comparing the two expressions for MNK seems to indicate that choosing the bases
and their order so that pKIPNK-l will lead to the greatest probability of
attaining a high degree of correspondance between mixed base and modular
representations in a system.
ASD TR 61-438 176

APPEN2BIX III
SIGN DEPTERNAITION BY A WWO-DIGIT REDCTZICON PROCESS
INTRODUCTORY REFARKS
This report presexnt-ms a method for determining the magnitude of a number
from the decimal system whbich has been transformed into a residue number systemo The residue representation does not pernit a trivial recognition of
magnitude, otherwise there wTould be no need of such a method.
This method determines which half of the system the number is in,
TERMINOLOGY
The bases are taken as primes, where p1 is taken to be the number 2 while
Pi(i A 1) represents any arbitrary prime.'ihe primes are to be arranged in
increasing order, after arbitrary selection, such that
PI < P2 <. < Pi < P1i6 < O..'... < Pn (3-1)
The letter n will be taken to mean th-e total number of prime bases, and N will
mean any number representable in the system. The letter ai shall represent
the residue of N with respet to p1i and the range of N to be considered shall
be
< N < M (3-2)
where
M = 7Pi
i=l
ASD TR 61-438 177

In symbolic form, the number shall be represented by
Bases: P1P2P3.......... Pn (3-3)
N = = a1a2a3.....oooo. a
Use will also be made of further terminology. The letter m shall indicate the product of two base primes, and to be orderly let
ml = pnPnnm2 = Pn-2Pn-3
o (3-4)
mk = P4P3
The case under consideration is seen to be n an even number, with k thus
being equal to (n/2)-l.
This orderly pairing of primes and assignment of subscripts to the m's
is not essential and does not effect the generality of the result, It is
merely an aid to simplification of symbolism,
The letter bi shall represent the residue of N with respect to mi, and
si, ti and dj represent integers.
OPERATIONAL REMARKS
From the terminology section, ai is the residue of N with respect to pi.
This may be written as:
N = sipi + a (3-5)
and, from the interpretation of bi;
N = timi + bi (3-6)
ASD TR 61-438 178

By the nature of the residue system, certain operations are easily performedo If the representation has a zero in the ith digit position, division
by Pi is simnple and guarantees an integer resulit Thus
= - si (3-7)
Pi
is easily performed, because N-ai does indeed have a zero in the ith positiono
Similarly, tlhe operation
t= i t~ (3-8)
mi
is easily performed, since mi is the product of two base primes and N-bi has
zero digits corresponding to these primeso
However, bi is not as readily available as was aio But bi may be found
by equations (3-12) and (3-13)o in the development of these equations, the
subscripts on b, t and m have been changed to avoid confusion with p, d and
a,
Let
mo = PifP
where
2 i < j n
and
0 d j Pi - 1
By the definition of a and b
bo - aimod Pi
b0 m ajmod pj (3-9)
ASD TR 61-438 179

These equations (3-9) may also be interpreted as follows
bo = diPi + a
bo = djpj aj (3-10)
Combining equations (3-10) yields
i aj = djPj - diPi
which may be also interpreted as
ai aj - djpjmod Pi (3-11)
and thus the procedure for the determination of bo, from equations (3-10) and
(3-11) is:
d = ai- (3-12)'' Pj P
i
o = djpj + a (3-13)
ADDITIONAL REMARKS
If care is taken in selection of the primes for mi, a savings will resulto For if, in equation (3-12), pj - +1 mod pi the congruence relation
is solved merely by subtracting aj from ai in the mod pi portion of the system, a fast and simple step~
In connection with the forthcoming expansion, note that the machine
step of equation (3-7) destroys the ith digit position0 If the system is
assumed capable of re-expanding si to reclaim the lost digit position, then
a reduction to a uniformly-based number system can be made~ The following
ASD TR 61-438 180

reduction to a no.nur..iformiy-'based nuniber system does not require such an.
as sumpt i on o
REDUCT.ION TO NON-UII\TiP3R)LT 23AS5 SYSTEM
The nurmber N will r..ow'be d-eve-soped from its residue representation into
a non-uniformly-based numbnero, The e starting point is the use of equations
(3-6) and (3-8), an.d te fol owing iterative procedure:
N _ t,,m, + b1 t1 N bm
N =
~,~1 + bitl
mi
tl - b2
-i2..i im k
Ml o
-bkl
tkl = Iknk bk (1k =4)
m'kk
Equation (3-14) +t.r.us -hows the final result of the iterative process.
By combining thlis equ.ation -i:t can. be seen that
k —1.
tk =e (3-15)
k Rk~.
k l
N =tk t m tN-bk l-nb~o o. o o o o o + +
JT~ mi =
Then by solving (3-15) for N, the result is seen to be a non-uniformly-based
number
k k-i
N = tk "- bi + bk7(C i ~...oooo.oo.o bsm2ml + btmi + 13 (3-16)
ASD TR 61-438 181

in which
0 O<bi mi - o
DEVELOPMENT OF THE FINAL STEP
There are exactly (plp2) -1 occurrences of the case bi = mi-l for 0 < N < M,
two of which will be helpful in establishing certain limits. The two cases
are now to be examined, and they are:
(a) N = - 1,
and
(b) N = M- l
In each case, add unity to the representation of (3-16), resulting in:
M (a+ )~7mi (5-17)
(a) = (1 + t ) m (3-17)
i=l
(b) M = (l+t ()) 7 mi (3-18)
i=l
In the equations (3-17) and (3-18) the letters t() and t() refer to speM
cific constants, respectively the most significant digit of 7 - 1 and M-l in
the non-uniformly-based system.
By equations (3-2) and (3-4)
k n
Trmi = 7 Pi (3-19)
i=l i=3
M = Pi
i=l
ASD TR 61-438 182

And, since Pi = 2 by definition
M -
7( = TL(3-20)
i=2
By combining equations (3-17-3-20)
(a) M: P2- L(t = 2 1)
(b)
tk = P1P2- l(N - M-1) (3-21)
It now follows from equations (3-21) and as a direct result of the carry
properties of the non-uniformly-based number system of equation (3-16) that
for
0 N < ~, O tk < P2
M<2 N < M, P2 < tk < PP (3-22)
Since the orderly use of the primes in the formation of the mi's was
not essential to any of the steps involved up to now, as long as each prime
is used once and only once in that formation except for p, and one other
prime Pr, the equations become in the more general case
M
0 N' < 2 0 < tk < Pr
2 ^ < M, Pr < Ntk < PiPr (3-23)
The only difference resulting from a given selection of Pr will be in the
weights assigned to the digit positions of the non-uniformly-based number
system~
Each step of this procedure eliminates two digit positions from further
ASD TR 61-438 185

consideration. After k steps, upon the derivation of tk, there are two digits
remaining for its representation, a1 and ar. The primes on these letters
merely serve to underline the fact that they are not the a, and ar of the
number N.
A brief study of equations (3-23), bearing in mind the cyclic nature of
a residue representation, shows that for
f 4. even, a even
< tk < Pr; a is odd when ar is odd
while
Pr < tk < PiPr; al is even when ar is odd
odd even
And therefore when
a + ar - Nomod 2 (3-24)
it is seen that when
O, O N N<
No
1, 2< N<M (3-25)
And it is for this reason that pI = 2 was saved for the last (k+l) step,
EXAMPLE
An example is now given to illustrate pairing the prime bases to satisfy
the criteria of the additional remarks section,
For the bases (2, 3, 5, 7, 11, 13, 17, 19, 23, 29), pairs ml = 29x7;
m2 = 23x11; m3 = 13x3; m4 = 19x5; while P = 2 and pr = P7 = 17.
ASD TR 61-438 184

The assignmente of sutsc-ripts to the mns in this examnple is arbtitraryo
Each definite assigrn.me:nt leads to a separate number systemo
CO,,LLUDING RERkiRKS
An. answer to -t his particular magnitude question is guaranteed in K4.
steps3, where for
n
n evern K I =
nr odd K = 2 (3-26)
In the latter case, the final step becomes merely an inspection of the
al digit with th.e conditions of equation (3-25) becoming
(0L-r M
(9, 2 < N <.
If aI =
But,'w'hile Ktl.' steps are required in general, the procedure may terminate
earlier, depending upon the size of No For when any
M
i 0i < K) 9 0 N<
since
ti = G if 0I f N < 3 mj
D.=I
Now a.tinme estimate for the somp'lete operation gives, for equation (3-8)
1 add time; while for equations (3-12) and (3-13); 2 add times; for a total
of 3 add times per ith step 1 i < Ko The final step for n even takes i add
time, while for n odd does not, requiare an addition, but an inspection. iThese
ASD TR 61-438 185

facts coupled with equations (3-26) give
n even: - 1)3 +1 add times
n odd: (n) 3 add times (3-27)
to guarantee an answer.
However, if only one digit is removed at once, by the use of equation
(3-7) alone, only two add times per step are required for n-2 steps, and one
add time for the final step (n both even and odd) and equations (3-27) become,
for this case
every n: (n - 1) add times.
ASD TR 61-438 186

APPENDIX IV
C! MMENIS ON PARITY C HECKITG N THEN RNS
A first thought is to apply normal checking procedures to the Residue
Number System. Any conventional method may be applied to the transmission of
digits from one point to another,o hat is, simple parity, multiple parity,
and Hamming checks may be applied by considering the binary coding to be a
message, with no consideration given its semantic character, Nothing new or
special is added merely because the message is a residue coding.
This discussion will be on arithmetic checkingo The problem is essentially to find a function F(a) having the property
F(a) + F(b) = F(a + b)
The most obvious example of such a function is F(a) = a, This is interpreted
as duplication of the addition circuitry, A second and more significant example is F(a) a mod mo If the moduli of the RNS are mi, m2,, omn and m = mj
for some j, then this function is not particularly useful. It is a duplication of one of the component sums and suffers from the same type of limitation
as the identity functiono Attention will be focused on the case where m ~ mj
(for all. j). Here if m mj (for all j), then F(a) is a function of all n
components and, therefore, requires a conversion to the mixed base system,
The carries involved make this system very unattractive. A "useful" check
will either involve a conversion to the mixed base system or will require a
separate check on each of the digits. This latter case will be discussed in
considerable detailo
ASD TR 61-438 187

In Garner'sl4 paper on Generalized Parity Checking, the dimished-base
check is discussed, in which:
ibj - oimod (b-l)
Also the augmented-base check, in which:
cibj - cimod (b+l)
or
a- imod (b+l)
Neither of these can be used when
bj = mj
for then k = 0 and these relations are trivial, However, were the components
to be binary-coded, it would be possible to use the augmented-base checko
It is more intriging to consider a binary-coded base-3 system of components with the dimished-base check, Moduli up to 81 could then be employed
with a maximum of 4 such binary groups, and up to 27 with 3 base-3 digits,
Only the least significant bit of each group would be involved in the checkingo Three or four digits could conveniently be handled with "carry-lookahead," if not by purely combinational circuits. Consider the RNS with moduli
mlj m2J,2 mnn
If
ji
x - imod mi
then
x = ai + kmi
and
x = 0i + (kmi )mi~, where ~ < ji
ASD TR 61-438 188

yielding
x =- imod mi'
Thus, the residue of x mod mi may be obtained from the residue of
x mod miJi. From this it follows that such a RNS could be used to obtain the
residue of x mod mi as a function of the individual components. This derived
residue could be used to implement a che;ck It, will now be shown that the
only moduli which would work in the above scheme are those which divide mi
If
x = aimod m
and
y - b mod m
then
x - y - al m bmod m
and the retained residue is
Fa,1 +b11
L m
Now
a1 - a2mod m'
bl b2mod ml
and
al + bi = a2 + bt2od m'o
The residue of a2gT2mod m' equals the residue of a+blmod m'. The residue
produced in the check procedure is
ASD TR 61-438 189

ma
Choose for consideration an a, and a b1 such that
al + b1 = m
Such a selection is possible because allb will span the integers I
0 < I < 2(m-1)
If m' Im then
La - k,+ bi
and
i a+bi b, = a+ ab
However, if m'/ m
ml m
and
al+ b, 0.
mL'
The hypothesis has been demonstrated.
ASD TR 61-438 190

REFERENCES
1. Valach, MN Vznik Kodu A Ciselne Soustavy Zbytkovych Trid, Stroje Na
Zpracovani Informaci, Sbornik III; 1955.
2. Svoboda, Ao Rational Number Systems of Residual Classes, Stroje Na
Zpracovani Informaci, Sbornik, 1957.
3. Svoboda, A. and Valach, M. Operatorove Obvody. Stroje Na Zpracovani
Informaci, Sbornik III, 1955o
4. Garner, Ho Lo "The Residue Number System." IRE Transo PGEC, Volo EC-8,
June 1959, Po 140-47,
5. Cheney, Po W. A Digital Correlator Based on the Residue Number System.
Technical Document LMSD-702670, Lockheed Aircraft Corporation, Palo Alto,
Califo, 1960,
6. McCoy, N, H. Rings and Ideals Buffalo, New York: The Mathematical
Association of America, 1948.
7. van der Waerden, B. Lo Modern Algebra, New York: Frederick Ugar Publishing Company, Volo I and II, 1950.
8. Hildebrand, F, Bo Introduction to Numerical Analysis, McGraw-Hill Book
Co.; 1956.
9. Cheney, P. Wo Scaling by Deletion of Bases. Modular Arithmetic Note 10,
Lockheed Aircraft Corporation, Palo Alto, Calif.; August 1960.
10o Herwitz, P. So and Pomerene, J. Ho The Harvest System, Proc, WJCC, pp.
23-32; May 19600
11. Report BL-25, Harvard University Communications Laboratory.
12. Valach, M. and Svoboda, A. Operational Circuits, Institute of Mathematical
Machines; Oct, 1954; p. 330.
13o WADC TR-59-472 Project 7062; July 1959.
14, Garner, Ho L. Generalized Parity Checking. IRE Trans, PGEC, Vol. EC-7,
Sept, 1958, pp. 209-13o
ASD TR 61-438 191

UNIVERSITY OF MICHIGAN
I 1 1 11111111ill il l11111111
3 9015 03127 1979