Hi I 
 
 ISM UN laBfaai 
 
 lH iHHBhhk 
 
 HraH 
 
 mxm WSBM 
 
 ■■■■ap 
 
 BHlBltSHD91 
 
 
 ■OBlul^MliMilliiiltnllrliiili 
 fflujfil HMm mMB 
 
 ml m 
 
 Us S« Si Si 
 
 ■ raw! BHtntiar 
 
 Rfl aM IHMUfllflQ 
 
 HBbBHBh! SS8BKral 
 
 m w&mffl 
 
 BBS BH BBmHtfi 
 
 H Hi 
 
 Wmni InR Villi 
 
 TnByWnTfflflnyWinflnlfil 
 * * i dim kkh bhh 
 
 HJDUU 
 
 KK&Ii! 
 
 ill! 1811 
 m mm 
 
 HHHHH 
 
LIBRARY OF THE 
 
 UNIVERSITY OF ILLINOIS 
 
 AT URBANA-CHAMPAIGN 
 
 
Digitized by the Internet Archive 
 in 2013 
 
 http://archive.org/details/algorithmforsolu525triv 
 
Vie. 5u5 
 
 
 TtftJd- 
 
 uiucDcs-R-72-525 
 
 AN ALGORITHM FOR THE SOLUTION OF A QUADRATIC 
 EQUATION USING CONTINUED FRACTIONS 
 
 by 
 
 Kishor Shridharbhai Trivedi 
 
 June. 1972 
 
 DEPARTMENT OF COMPUTER SCIENCE 
 UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 
 
 URBANA, ILLINOIS 
 
 THE LIBRARY OE IKE 
 
 UNIVD7SITY OF ILLINOIS 
 AT URBANA-CHAMPAIGN 
 
UIUCDCS-R-72-525 
 
 AN ALGORITHM FOR THE SOLUTION OF A QUADRATIC 
 EQUATION USING CONTINUED FRACTIONS 
 
 by 
 Kishor Shridharbhai Trivedi 
 
 June, 1972 
 
 Department of Computer Science 
 
 University of Illinois at Urb ana -Champaign 
 
 Urbana, Illinois 6l801 
 
 *This work was supported in part by the National Science Foundation under 
 Grant No. US NSF GJ-81J3 and was submitted in partial fulfillment for the 
 Master of Science degree in Computer Science, 1972. 
 
Ill 
 
 ACKNOWLEDGEMENT 
 
 The author wishes to express his sincerest gratitude to his 
 advisor, Professor James E. Robertson. Professor Robertson's patience, 
 guidance, invaluable aid and encouragement, timely suggestions, and 
 continuing interest in this research are most appreciated. 
 
 My thanks are also due to colleagues Milos Ercegovac and 
 Lakshmi Goyal for many helpful discussions. 
 
 I would also like to thank Mrs. June Wingler for an 
 excellent job of typing this thesis. 
 
IV 
 
 TABLE OF CONTENTS 
 
 Page 
 
 1. INTRODUCTION 1 
 
 2 . GENERAL EXPLANATION 3 
 
 3. BASIC RECURSIONS 13 
 
 k. INVESTIGATION FOR SELECTION RULES 22 
 
 5. PROOF OF CONVERGENCE lj-0 
 
 6 . CONCLUSIONS 5h 
 
 LIST OF REFERENCES 56 
 
 APPENDIX 
 
 I . A FORTRAN PROGRAM IMPLEMENTING THE ALGORITHM QD 57 
 
 II. COMPUTER PRINTOUTS OF A FEW PROBLEMS SOLVED USING 
 
 THE PROGRAM IN APPENDIX 1 59 
 
1. INTRODUCTION 
 
 Arithmetic methods used in digital systems require that some of 
 the prejudices, that all of us have acquired through our early arithmetic 
 training, shall be overcome. Early designs of arithmetic units of digital 
 computers were largely a mechnaization of the methods used by the human 
 computer. The experience of the last few years has taught us that such 
 efforts, though not always, are generally uneconomic and inefficient. We 
 now illustrate further, the point made here. 
 
 First of the human prejudices to be overcome was the use of the 
 decimal number system. An interesting discussion on this point can be 
 found in references [7] and [8], cited at the end of this paper. 
 
 The second prejudice was the requirement of uniqueness in the 
 representation of numbers. Over the years, the leaders in the field of 
 digital computer arithmetic have emphasized that the key to fast and 
 efficient arithmetic methods is redundancy in the representation of numbers. 
 Interested readers may see reference [8]. 
 
 The third prejudice is the use of the positional notation, i.e., a 
 number is thought to be a weighted sum of a series. Unfortunately, the 
 functions that can be easily implemented with this type of representation of 
 numbers are limited to addition (subtraction), multiplication, division and 
 square and higher roots. 
 
 DeLugish [3] has presented a continued product formulation that 
 extends the range of easily implemented functions to the logarithm, the 
 
exponential, and the trigonometric and inverse trigonometric functions as 
 well as multiplication, division and square root. He has developed 
 algorithms to evaluate these functions in from one to three "multiplication 
 cycle times." 
 
 The above research led us to consider what other representations 
 of numbers exist, and what class of computational procedures can easily be 
 formulated for each such representation. This explains our interest in 
 continued fractions. One must make the distinction that although the 
 computational procedure is based theoretically on a continued fraction 
 formulation, the continued fraction representation is ephemeral as explained 
 in this paper. 
 
 
2. GENERAL EXPLANATION 
 
 A finite continued fraction is represented as follows 
 
 P k P l P 2 P k 
 
 \ q i + % + ' + q : 
 
 k 
 
 where P, and & are determined from the recursions [ 1] : 
 
 P i " Vi-l + % P i-2 (2 ' 1} 
 
 Q. = 0^.1 + *iS.-2 1*2, 3, ..-., k 
 
 P Q = 0, ? ± = Vv Q Q - 1, Ql = q x 
 
 It is clear that P and QL can be separately and simultaneously 
 determined in two binary arithmetic units in (k-l) addition times, if p. and 
 q. are chosen to be "simple" in the binary sense. The assumption of p. =1 
 for all i has been made in this paper. It is possible to remove this 
 restriction [9] • 
 
 The choice of a digit set for q. is governed by the following 
 factors. 
 
 (a) It should be "simple" in the binary sense. This means that 
 elements of the set should be powers of 2 (both negative and positive powers 
 are allowed), since then each of the operations (2.1) reduces to a shift and 
 an addition. 
 
(b) The number of elements in the set should be a minimum 
 possible, so that shift hardware is simple. 
 
 (c) With the digit set chosen, we get a certain range of infinite 
 continued fractions that are represent able. This range should form a 
 continuum over the minimum and maximum limits. This requirement allows us 
 to represent any number in the range as an infinite continued fraction. 
 
 (d) Rules of selection of q. should be both feasible and simple. 
 The significance of this requirement will become clear later. 
 
 A two valued digit set [1, 2) was first tried. 
 
 If we let u and u . represent the largest and smallest values, 
 max mm e ° ' 
 
 respectively, of the infinite continued fractions representable; then 
 
 u = .r-^-r or u (sT3-l)~ 0.732 
 
 max 1+1 max 
 
 2 + u 
 
 max 
 
 and 
 
 u . = _ ; = or u . = | (nT3-1)~ 0.366 
 
 mm 2+1 min 2 - 
 
 1 + u . 
 mm 
 
 In other words, 
 
 limit P 
 0.366 < ^ < 0.732 
 
 — K -* 00 U — 
 
 Unfortunately, however, rr- does not form a continuum over the range [O.366, 
 
 00 
 0.732] . In other words, not all numbers in the range can be represented 
 
 with this digit set. 
 
 Proof of this fact is as follows. 
 
 Let O.366 < u < 0.732 
 
 1 
 
 and let u 
 
 ii + f i 
 
where 
 
 q.^11,2) 
 
 and 
 
 O.366 < f < 0.732 
 
 for 
 
 <!]_ = 1* 
 
 
 0.^7737 
 
 and 
 
 
 for 
 
 q x = 2, 
 
 O.366 < u < 0.^2266 
 Thus the rule of expansion is as follows. 
 For O.366 < u < 0.^2266 choose q = 2 
 and 
 
 0.^7737 < u < 0.732 choose q = 1 
 
 But for 0.^2266 < u < 0.57737* there is no way to choose q from the digit 
 
 set 11,2} with the restriction that f is within the allowable range. This 
 
 means that, if we do restrict q to the chosen digit set, f will no longer 
 
 be in the allowable range and therefore cannot be expanded further. 
 
 So next we try q.e|— , 1}. With this set u =1 and u . = — . 
 1 2' max man 2 
 
 P 
 00 2. 
 
 Furthermore q~~ does form a continuum over the range [— , 1]. 
 00 
 
 A proof of all these three facts follows. 
 
 It is known that with q. in a given digit set having a maximal 
 digit M and a minimal digit m, the largest infinite c.f. representable is 
 an infinite c.f. of period two, with q^. = m and q^. = M. 
 
 Similarly, the smallest infinite c.f. is an infinite c.f. of 
 
 period two, with q^ = M and q^. 
 
 = m. 
 
 With q. £[—,!}, we have m = — , M = 1. 
 
u 
 
 max 1 1 1 
 
 2 1 + 1 . 2 1+u 
 
 ;r +. max 
 
 c. • 
 
 Solving which, we get, u = 1. Similarly u . = — . Thus we have shown 
 ' max mm 2 
 
 that 
 
 i / P 1 
 
 2< *= H <1 
 
 \ 00 ' 
 
 Next we show the continuum property. Our strategy here is to 
 first show that with the digit set {—, 1}, any number in the range [— , 1] 
 can be expanded as a c.f. and then we prove that such a c.f. converges to 
 the given number as the number of terms in the c.f. increases. 
 
 Thus we start by giving a method of expansion. Let f be any 
 number such that — < f < 1. Now let us expand f_ as follows. 
 
 f . = 1 
 
 1 q x + f 2 
 
 such that q e{— , 1}. 
 
 We also require that the choice of q, be made such that 
 — < f < 1. Since f is also thought of as a c.f. in the range [— , 1] 
 and therefore we can expand f also in the same way and so also for any f . . 
 
 We have the following rules of selection which satisfy these 
 
 conditions. 
 
 1 2 
 
 If — < f < — choose q = 1 
 
 2 1 
 If — < f < 1 choose q = — . 
 
 As we said earlier f . can also be expanded as 
 
 f. = 1 
 
 1 h + f ± + i 
 
 using these rules of selection. When same rules of selection can be applied 
 for any i, we will call such a method of expansion, a consistent method. 
 
We call such a method of expansion, a consistent method. 
 
 Thus we can get an expansion of f,, f_, .... f., ... f to give 
 
 1 2 1 n 
 
 f . 1 
 
 l . i 
 
 q i + \ + i 
 
 + _2 (2-2) 
 
 \ + f n + l 
 
 Next we prove a Lemma to be used later. 
 Lemma- 1 
 
 n 
 
 a i 1 
 
 
 Vi 
 
 " \ ' + 1 
 
 • 
 • 
 
 1 
 
 Proof 
 
 become 
 
 With the restriction that p. = 1 for all i relations (2.1) 
 
 P i ■ h P i-1 + P i-2 
 
 \ • % Q i-1 + Q l-2 < 2 -3) 
 
 p o = °> p i =1 ' V 1 ' V q r 
 
 Using these relations, we have, 
 
 Q 
 n 
 
 •1 
 
 % 
 
 Vi + 
 
 n- 
 
 -2 
 
 \. 
 
 
 Vl 
 
 
 
 
 
 
 1 
 
 
 
 
 
 \ 
 
 n-1 
 H n-2 
 
 
 
Vi + qT 
 
 h-2 
 Si-5 
 
 q n + ^X. 
 
 Vl V 2 + 
 
 1_ 
 
 + q l 
 
 Q.E.D. 
 
 P 
 Let the given number be f = -r. 
 
 And the finite c.f. 
 
 
 
 1 
 
 • 
 
 P. 
 
 q l + ^ + 
 
 be denoted by rr- 
 
 
 • 1 
 
 
 
 *i 
 
 
 where 1 < i < n. 
 
 P P i 
 Let the error made in approximating -r with — be denoted by 5. . 
 
 For proving the theorem we deal with a general case. Let m be 
 
 the minimum value of a digit in the digit set of ck . Let b be the largest 
 
 number representable with this digit set. That is b = u . And 
 
 similarly let a = u . . Let a < f ., < b. Now we state and prove the 
 J mm — 1 — * 
 
 following theorem. 
 
 The or em- 1 For a number f in [a,b], if there is a consistent method of 
 expansion of f, in the form of a continued fraction, then such an expansion 
 converges to the value f as the number of terms in the expansion increases 
 provided that m > and that 6 and b are finite. 
 
 Let us assume that f is expanded to the nth term. That is, 
 
t-% 
 
 \ + 
 
 % \ 
 
 % 
 
 + f 
 
 n+1 
 
 where a < f < b, since our method of expansion is consistent, 
 Using relations (2.3) and noting that 
 
 9n + f n + l = VI 
 
 "n+1 
 
 we have, 
 
 p = 
 
 f n+l 
 
 P + P - 
 
 n n-1 
 
 Q = 
 
 1 
 f n+l 
 
 Q + Q , 
 n n-1 
 
 P 
 
 1 
 f n + l 
 
 P + P _ 
 n n-1 
 
 Q " 
 
 1 
 
 f n + l 
 
 Q + Q -, 
 
 n n-1 
 
 -a + 
 
 n 
 
 n-1 
 
 Q 
 
 n+1 j 
 
 n-1 
 
 T 
 
 n-1 
 
 n 
 
 1 + 
 
 f n+l Q n-1 
 
 Q. 
 
 n 
 
 let 
 
 P 
 
 5 
 
 31 + R 
 
 Q n 
 n 
 
 then 
 
 P 
 Q 
 
 P 
 Q 
 
 n 
 
 n- 
 
 f n+l Si-1 
 
 f n+l Q n-1 
 
 Q 
 
 n 
 
10 
 
 p 
 
 5 
 
 + 
 
 Vl f n + l Vl 
 
 n 
 
 Si 
 
 1 
 
 + 
 
 n+1 n-1 
 
 ft 
 
 □ 
 
 Which gives 
 
 6 = -5 
 n 
 
 n+l n-1 
 
 n-1 G 
 
 Similarly 
 
 -e 
 
 f n V 2 
 
 n-1 n-2 ft 
 
 h-1 
 
 combining, 
 
 s f n Vl V 2 
 
 n n-2 Q, 
 
 n 
 
 = b 
 
 f f , 
 n n+l 
 
 n-2 q Q . + Q . 
 ti n-1 n-2 
 
 ft 
 
 h-2 
 
 = 6 
 
 f f . 
 n n+l 
 
 n-2 1 + q T 
 
 where Q 
 
 n-1 
 
 q T n n-1 Q 
 
 Ti n-1 : 
 
 h-2 
 
 Also 
 
 1 
 
 n 
 
 ^n + Vl 
 
 6 = o 
 n 
 
 f n-«n 
 
 n-2 1 + q T _ 
 n n-1 
 
 1 - f 
 
 = b 
 
 n Ti 
 
 n-2 1 + q T . 
 n n-1 
 
 let 
 
 1 - f 
 
 A 
 
 n ti 
 
 n 1 + a T 
 
 ^n Vl 
 
 We are interested in showing that A < 1 for all n or max (A ) < 1. 
 
 ** n n n 
 
11 
 
 1 - (fq ) . 
 fn \ n n man 
 
 l Vmax ~ 1 + (a). (T .) . 
 
 ti iin n-lmin 
 
 f > [since q. > V i} 
 n i 
 
 (q ) . = m> 
 
 n nan 
 
 By Lemma -1, 
 
 T = q + — = 
 
 n-1 V-l a + 
 
 (T _) . > (q .) . n > 2, 
 
 n-1 min Ti-1 nan — 
 
 (A ) > 1 - n > 2 
 
 n max n , 2 — 
 
 1 + m 
 
 > 1 {since m > 0} 
 
 5 < 5 
 n n-2 
 
 .*. To start with if we have 6, and 5 finite, then obviously as n -> ™, 
 
 P 
 n P 
 
 5 -» and hence s * — Q.E.D. 
 
 n Q, Q, 
 
 Now in the case when QL e {1/2,1}, m = — > and 1/2 < f = — < 1. 
 We have a consistent method of expansion as shown earlier. If we can show 
 that 5 and 6 are finite, then we can apply Theroem-1 and hence prove the 
 continuum property. 
 
 So let us get bounds on 5, first. 
 
 p 
 
 , ,~ . P . 2 . . 1 
 
 For 
 
 V 2 < 3 < 3 h- 1 "\ = 1 
 
 1 1 
 
12 
 
 P P l 
 
 for 2/3 < | < 1, q x = 1/2 .*• ~ = 2 
 
 1 
 
 . , i < 5, c f 
 
 - 1-3 
 
 for 1/2 < | < 1, j < 5 1 < \ 
 
 Next we get the bounds on 6 . 
 
 1 ^ p ^3. n -, n 1 • P 2 1 
 For 2^Q^? q i = lf Q 2 = 2 ' * Q^ = 3 
 
 " T5- b 2-~6 
 
 p 
 for I < | < |; c^ = 1, q 2 = 1 /. J. = | 
 
 for 
 
 "2 
 
 •"* "I - 6 2 ^ "10 
 
 2P6 1 1 . ^2 2 
 
 3 - Q S 7' 1 " 2' ^ " 2 ■" Q 2 ~ 5 
 
 16 . „ . l 
 •• "35- b 2-"5 
 
 6 P ^ .. 1 n . P 2 2 
 
 for 7<5<i;q 1 -2>%- 1 •• ^ = 3 
 
 • • -35 S ^ 2 S " 10 
 
 for |<|<i; -i<5 2 <-^ 
 
 Thus we see that 5- and 8 are finite and thus we have the required result. 
 
13 
 
 3. BASIC RECURSIONS 
 
 The particular problem chosen for investigation in this paper 
 was the solution of a limited class of quadratics 
 
 o 
 x + t>. x - c, = (x-u) (x+v) = 
 
 such that 1/2 < u < 1. The problem, specifically, is, given b, and c , 
 find u (and hence v = b, + u). This problem was selected because of the 
 following property of infinite periodic continued fractions of period k. 
 
 If the value of a finite continued fraction formed by truncating the 
 
 st P k-1 
 given fraction beyond the (k-l) — partial denominator is -x and 
 
 \-l 
 
 th 
 similarly, if the value of a fraction truncated after the k term be 
 
 P k 
 given by 77-, then the value of the infinite periodic continued fraction 
 
 \ 
 is given by u, the positive root of the above quadratic. The coefficients 
 
 b, and c are, b = (QL_ - P j)/\ and % = \/\ i* The P rot,lem then, 
 is resolved specifically, to the following one. Given (Q. - P, 1 )/ ( °L 1 
 and P /Q. (note that k is unknown), find the sequence of partial 
 
 denominators q, (i = 1, 2, ..., k), and from these by recursions (2.1) 
 
 1 P 
 
 form P and Q to a satisfactory precision. Finally the ratio -S gives 
 
 n 
 
 the value of u to machine accuracy. 
 
 Next we develop the basic recursion* relations for expanding 
 the root u of the quadratic in the form of a continued fraction. Together 
 with recursion relations (2.3), these form the basis of the present investigation. 
 
 *Due to J. E. Robertson[2] 
 
11+ 
 
 From the given quadratic 
 
 * 2 + v - c k = ° 
 
 and substituting u for x, we get 
 
 C k 
 
 u = 
 
 t> + u 
 k 
 
 b. + b. 
 k k 
 
 Thus in the present form u is an infinite continued fraction 
 
 of period one. However, the partial numerators (c, ) and partial 
 
 denominators (b, ) are full precision numbers. Therefore, if we attempt 
 
 to use the recursions (2.1) directly, it would seem that four full 
 
 precision multiplications and two full precision additions are required 
 
 at each iterative step. However, with p. = c , q. = b V i, Robertson[2] 
 
 has shown that P. = Q,'. _ V I and thus only one of the recursions (2.1) 
 l l-l 
 
 is required. Even after this reduction of computation, this procedure 
 is clearly not practical. 
 
 The strategy now used is that we extend the period of the 
 infinite c.f. for u by one at each iterative step in the following way. 
 
 p 
 
 : U = 
 
 P l 
 
 Q ' 
 
 C k-1 
 
 q i + K n + * 
 
 k-l 
 
 where p. and q. are simple in the binary sense, and hence will reduce 
 the full precision multiplication of the direct method to a conditional 
 shift. (Single or may be multiple - right or left.) 
 
15 
 
 From the last equation, 
 
 V 2 + (c kAiV p i ] u " Vi p i = °- 
 
 after dividing throughout by q and then equating coefficients with the 
 
 2 
 u + b, u - a, = we have, 
 k k 
 
 P l q l 
 
 c. = b, . — or b. _ = — c. 
 
 k k-1 q, k-1 p k 
 
 2 
 q l c k 
 and C k-1 = q i b k + P l " -J- 
 
 C k-1 = q l ( V b k-l } + P l 
 
 q ! C k 
 and Vl " ~ 
 
 (3.h) 
 
 Let us now take a case when u is already expanded into a periodic fraction 
 of period n. Then 
 
 P p i 
 
 ■*■ = u = 
 
 Q " q 2 + p 2 p. 
 
 + + n 
 
 ^2 q + °k-n 
 
 b, + u 
 k-n 
 
 P n P n-1 
 With the usual notation for rr- , r and applying recursions (2.1) to 
 
 n n-1 
 
 the above equation, 
 
 (b. +u) P + (c, ) P n 
 
 k-n n k-n n-1 
 
 £ = u = Tb. +u) Q + (c. ) Q " 
 Q k-n n k-n n-1 
 
 from which we obtain the equation, 
 
16 
 
 2 ( VnV C k-A-l- P J 
 u +u 5 
 
 n 
 
 c. P ,+b, P 
 k-n n-1 k-n n 
 
 Q 
 n 
 
 = 0. 
 
 Equating coefficients with the given equation 
 
 u + b, u - c, =0, 
 
 k k ' 
 
 we get 
 
 P b. + P„ . c, = Q c. 
 
 n k-n n-1 k-n n k 
 
 and 
 
 Q b. + Q , c. = P + Q b, 
 n k-n n-1 k-n n n k 
 
 Solving for b. and c. , 
 ^ k-n k-n' 
 
 k-n 
 
 P ^b. +PP ,-QQ , c, 
 n-1 n k n n-1 n n-1 k 
 
 P -Q - Q _P 
 n-1 n n-1 n 
 
 f - Q 2 c, 
 
 and 
 
 'k-n 
 
 P Q b. + . 
 
 n n k n n k 
 
 P Q , - Q P - 
 n n-1 n n-1 
 
 Now if we put the restriction that p. = 1 for all i then we can use a 
 theorem from the theory of continued fractions[l] which says 
 
 P Q _ - P _Q = (-1) 
 n n-1 n-1 n 
 
 n-1 
 
 if p. = 1 V i. 
 
 i 
 
 Then the last two equations result in 
 
 *n-l 
 
 b. = (-1) [Q (Q -c. - P -b. ) - P P -] (3-5) 
 
 k-n L n n-1 k n-1 k n n-1 
 
 c. = (-l) n_1 [Q (Pb, - Q c. ) + P 2 ] . (3-6) 
 
 k-n L n n k n k n ^ 
 
IT 
 
 Replacing n by n-1, we have 
 ,n-l 
 
 k-n+1 
 
 k n-l 
 
 c 
 k-n+1 
 
 • ( - ir tVl (P n-2 b k " \-2^ + P n- 2 P n-ll ^ 
 
 - (-I)"" 1 tVl ( \-l C k - P n-lV " P n-1 ] • (3 - 8) 
 
 Similarly, 
 
 b. ^ = (-1) 11 " 1 [Q o (Q ,c. - P ,b. ) - P ,P _] (3-9) 
 
 k-n+2 L n-2 n-3 k n-3 k n-3 n-2 J K v/ 
 
 C, ^o = ("I) 11 " 1 [^ o ( P o b T - Q o c -, ) + p2 o] • (3.10) 
 
 k-n+2 L Ti-2 n-2 k n-2 k n-2 J ' 
 
 From these equations, surprisingly enough, we are able to 
 
 eliminate all P's and 0,'s and get the relations between b's and c's 
 
 involving only q's as follows. 
 
 Substituting f or Q = q Q . + Q _ and P = qP _ + P n 
 n ti n-1 n-2 n ti n-1 n-2 
 
 in (3-5) (and for Q, _ , P - and the relations 3-7 to 3»10) and 
 
 rearranging, we have 
 
 b. = (-1) 11 " 1 (a Q -, (Q .c. - P _b. ) - a P 2 n 
 
 k-n ^n n-1 n-1 k n-1 k ti n-1 
 
 + Q _ (Q .a - P ,b, ) - P P _) 
 
 n-2 n-1 k n-1 k n-2 n-1 
 
 ^n k-n+1 L n-2 n-1 n-2 k ti-1 n-2 k 
 
 - q _P 2 + Q (Q c. - P _b. ) - P X P _] 
 
 Ti-l n-2 n-2 n-3 k n-3 k y n-3 n-2 J 
 
 fy = <1 c. - a -c. ,_ + b. ,_ . (3-H) 
 
 k-n n k-n+1 ti-1 k-n+2 k-n+2 
 
18 
 
 Similarly, 
 
 c k-n ■ \ (b k-n + l " W + c k-n + 2 ' &^ 
 
 Thus all in all, we have, given b and c, , 
 
 \-l = Vk 
 
 c k-l = X + q l (b k " b k-l } 
 and for n = 2, 3, .... (3.13) 
 
 b k-n = q n C k-n+l " q n-l°k-n+2 + b k-n+2 
 
 C k-n = % (b k-n+l ~ b k-n } + C k-n+2 
 
 These recursion relations together with relations (2.3) form 
 the core of the algorithm discussed in this paper. We will repeat (2.3) 
 
 p o " °> % = x 
 
 \ = 1, % - 0, 
 
 for n = 2, 3, ... (2.3) 
 
 P = q P . + P _ 
 n ti n-1 n-2 
 
 n Ti n-1 n-2 
 
19 
 
 The algorithm, at this stage, is as follows. 
 
 Step 1 Read in values of b and c . (Assume they are in 
 
 range. ) 
 Step 2 Initialize P Q =0, ft = 1, P = 1 
 
 Step 3 From the selection circuit and values of b and c 
 
 find q_. 
 Step k Find h^_ ± = q. ± (c fc ) 
 
 C k -i = 1 + \\- Vl ] 
 
 and Q = q 
 
 set i = 2 
 Step 5 Input b, . _, c, to the selection circuit and 
 
 get q. as the output. 
 Ste£_6 Find b k _. = q^.^ - O^.^ + t> k _i+2 
 
 c k-i ' % ( \-i + l " W + °k-i+2 
 
 P i I «i P i-l + P i-2 
 
 Q i ' h\-l + Q i-2 
 Step 7 Is i > i ? If no then go to step 5, else go 
 
 DlciX 
 
 to step 8. 
 P. 
 Step 8 Get u = ~ 
 i 
 
 The value of i is determined by the desired precision of 
 
 ULcLX 
 
 the result. We need four binary arithmetic units to compute b ., c ., 
 P., Q. at each iterative step. Each iterative step consists of pure 
 
20 
 
 shifts and addition (subtraction) operations only. A division must be 
 carried out at the end of the iterative process. We need seven storage 
 registers to store previous values namely, q. ,, b, _ . ,, b , c, , 
 
 k-i+2' i-1 l-l 
 
 To complete the algorithm, we have to provide for a selection 
 
 process as required in steps 3 and 5« We develop a selection procedure 
 
 in the next chapter. 
 
 We have placed two restrictions on the set of quadratics, namely, 
 
 b, > and — < u < 1. The first restriction is unavoidable, however, the 
 
 K. 2 
 
 second restriction is really no restriction in the following sense. 
 
 Let us assume that for a given quadratic, the above restriction 
 is not satisfied, but — x 2 J < u < 2 is satisfied, where j is an integer. 
 Robertson[2] has suggested a scaling procedure to reduce this problem to 
 
 the rangeof u required by the algorithm presented in this paper. 
 
 2 
 The given equation x + b, x - c = is multiplied throughout 
 
 -21 
 
 by 2 u , giving, 
 
 (2-^x) 2 + (2"\) (2^x) - (2" 2;j c k ) . 
 
 Substituting x' - 2 -:i x, b' = 2"«H>. , c^ = 2 ~^\> we S et ^ x ' 2 + ^ x ' " 
 
 c,' = = (x 1 + v') (x' - u')« And now, clearly, — < u' < 1 is satisfied. 
 
 K. 2 
 
 Therefore, we can solve for u' starting with b' and c' . Note that b ' and 
 ' k k k 
 
 c ' are easily obtained from b and c by -j and -2j bit shifts respectively. 
 Similarly, the root u is obtained from u' by a j-bit shift. 
 
 Secondly, if the algorithm of this paper is to be used for the 
 case b =0 (i.e., the square rooting problem) and if we are dealing with 
 floating point numbers, the mantissa of the given c, will be in the range 
 
21 
 
 [— , 1]. But since the exponent can be odd or even, a conditional 
 
 unnormalizing by one bit shift may be required. Thus, if we can find 
 
 the square roots of all numbers in the range [— , 2] or in the range [r> 1] 
 
 we are satisfied. The range [r>l] was selected, resulting in the range 
 
 of u given by [g>l]. 
 
 Henceforth, we assume that — < u < 1 which imples l/2b + l/k- 
 
 < c, < b +1, since all the other values of c, and b, may be scaled to 
 - k - k k k 
 
 lie in this range. 
 
 A proof that the algorithm presented in this paper converges 
 for the specified conditions will be presented in chapter 5* 
 
22 
 
 k. INVESTIGATION FOR SELECTION RULES 
 
 Firstly, let us find the range of c, and b that we can possibly 
 consider with the restriction — < u < 1 (imposed by the choice q. e {—,!}). 
 We have, c = uv and b = v - u. .*. c = b u + u . 
 
 K K. K k 
 
 For a given value of u, this is a straight line in the (c , b ) 
 
 Y. K 
 
 plane. Using the maximum and the minimum values of u in turn, we will get 
 
 two straight lines, namely, c = b + 1 (labelled A in figure l) and 
 
 c, = — b n + r (labelled B in figure l). The area of the (c n , b, ) plane 
 k 2 k 4 k'k 
 
 enclosed by these two lines represents a set of quadratics, for which 
 — < u < 1. This area is a double triangular wedge with the vertex P at 
 point (- — , - — ) in the plane. This is shown in figure 1. 
 
 For the sake of simplicity, let us restrict ourselves to the 
 triangular wedge above and to the right of the vertex. 
 
 C k 
 We have, u = - — - — , which is expanded at the first step, to 
 
 k 
 
 °k 1 1 1 °k-l 
 
 u = r ; — = r—z- q, € {.— , 1} and where — < f . p ■ — < 1. 
 
 b, + u q, + f., ^1 l 2' 2 — 1 b. , + u — 
 
 k 11 k-1 
 
 The above restriction comes from the fact that f is also an infinite 
 continued fraction and hence must lie within permitted range in our system. 
 
 Thus, with q - 1/2 and 1/2 < f < 1 
 
 2/3 < u < 1 
 
23 
 
 
2k 
 
 and with q. = 1 and l/2 < f . < 1 
 
 1/2 < u < 1 
 
 or q 1 = 1/2 for 
 
 | \ + | < c k < b k + 1 
 and qu = 1 for 
 
 2 \ + J < e k < J b k + - 
 
 Thus given c and b in the permitted range, we have a procedure to 
 
 uniquely find q . The various areas are shown in figure 2 in which the 
 
 11 2 k 
 
 lines c, = b, + 1, c. = — b. + r- and c. = 7 b. + — are labelled A, B and 
 k k ' k 2 k 4 k ;> k 9 
 
 C respectively. 
 
 For the general case of choice of q (i / 0), the procedure 
 
 C k-i 1 
 
 is slightly different. Since we have f. = 
 
 i b. . + U q.^ n + f 
 
 k-i ^i+l l+l 
 
 Note that except for the case of i = 0, f. is not directly related to u. 
 
 For the case i = 0, we have seen earlier that f. = u. This fact calls 
 
 ' 1 
 
 for a slightly different approach. 
 
 We have J < f . n < 1 
 
 2 — l+l — 
 
 1/2 < u < 1 
 
 1 c, . 
 
 then q__ = ~ for 2/3 < f. = r — ]_ < 1 
 
 T.+1 2 ' — i b,^ _. + u - 
 
 k-i 
 c, 
 
 and 
 
 0.^=1 for 1/2 < f . = ^~. < 2/3 
 
 ^L+l ' - 1 b, . + VL — '"' 
 
 k-i 
 
25 
 
 OJ 
 
 •H 
 
26 
 
 which gives 
 
 2 2 1 
 for rb. . + — u < c, . < b n . + u: choose q . , = — 
 
 3 k-i 3 ~ k-i - k-i ' *i+l 2 
 
 and 
 
 1 , , 1 . 2 , .2 
 
 for 
 
 - b. . + - u < c . " - b. . + - u; choose q. _ = 1. 
 2 k-i 2 — k-i - 3 k-i 3 T.+1 
 
 2 2 
 The dividing line a. . = — b, . + — u decides between q. = 1 or 
 to k-i 3 k-i 3 T.+1 
 
 q. = — . But unfortunately this line is u-dependent, and u is the 
 
 solution sought; thus, we can never find q unless the solution is 
 
 known! 
 
 Thus we conclude that we must have redundancy in the digit set 
 of cl, so as to have a greater latitude of choice. 
 
 The first choice, naturally enough, was q. e [r-, — , 1}. 
 
 Firstly, this set is simple in the "binary sense." 
 
 In a manner very similar to the case of q. e [— , 1}, it can be 
 
 shown that 
 
 a = u . 
 man 
 
 . = J (>fl7-l) ~ 0.390388 and 
 
 m o — 
 
 b = u = i (/l7-l) ~ 1.561553. 
 
 max 2 — 
 
 max 
 
 It can also be shown that a consistent method of expansion into 
 a c.f. for a given number in the above range exists. 
 
 It is also clear that b and b are finite. Since m = 7- > 0, 
 theorem 1 is applicable, and therefore, we have the continuum property. 
 
 Also, note that the range of u we are interested in, namely 
 [1/2, 1], is completely covered by the range of u allowed by the three- 
 valued digit set. 
 
27 
 
 So let us see if we can find a method of selection of partial 
 denominators. 
 
 As "before at ith step, we have, 
 
 f i = a,,, TT7Z where Vi ' $' 2> 1} * 
 
 T.+1 1+1 
 
 We have a constraint on f. , because of the requirement of consistency of 
 
 our method. This requirement is that a=u. < f. ,_ < u = b. Also 
 
 mm — l+l — max 
 
 note that to start with, f . = u € [a, b] . It follows then, that the 
 method of selection that we develop will be applicable for any i > 0. 
 We should also be aware of the fact that u is the solution 
 that we seek and hence it is unknown, so we should require that our rules 
 of selection of q. -, be u-independent. 
 
 Thus f. 
 
 k-i T.+1 i+I 
 
 0.39 - a < f. ,, < b ~ I.56 
 
 — — 1+1 — — 
 
 with q. , n = 1 
 
 i+I 
 
 c, . 
 
 O.39 < f . = r — ~= — < 0.72 
 
 — 1 b. . + u — 
 
 k-i 
 
 means 
 for 
 
 0.39 b. . + 0.39 u < c, . < 0.72 t>. . + O.72 u; choose q. , = 1. 
 k-i — k-i — k-i T.+1 
 
 Similarly 
 
 for 0.485 b, . + OA85 u < c, . < 1.12+ b, . + 1.12k u; choose q. _ = ^ 
 
 K—2. K— 1 iC— 1 l+l 2 
 
 and 
 
 for 0. 
 
 553 b + O.553 u < c C 1.56 b. . +I.56 u; choose q., . = h. 
 
 K~l K.""l K— 1 T.+1 + 
 
28 
 
 The regions, where two choices for q. , are allowed, are as 
 follows. If 
 
 0.485 b, . + 0.485 u < c . ■: O.72 b, . + 0.72 u, then 
 
 ] 
 
 choose q. + , = — 
 
 or 
 
 and if 
 
 0.553 b, . + 0.553 u < c . . < 1.124 b. . + 1.124 u, then 
 
 1 1 
 
 choose q i+1 = £ or -. 
 
 Let us call the former overlap region the (— & l) region, and 
 
 the latter, the (r- & — ) region. Notice that except for these two regions, 
 
 the value of q. ,, is unique, 
 l+l 
 
 A selection line which decides between the choice of q. , = — 
 
 l+l 2 
 
 or 1 should completely lie within the (— & l) region. Similarly there is 
 a (r- & — ) selection line. We also require that the selection lines be 
 u-independent, and that the slope as well as the intercept on the c . 
 axis be "simple" binary numberso To do this, we take the intersection 
 of all (— & l) regions as u varies over [a, b], and we require that our 
 selection line be completely within this intersection. Similar constraints 
 are necessary for the (y- & — ) selection line. These two intersection 
 regions are shown in figure 3' The upper bound and the lower bound of 
 the (r- & — ) are labelled A and B respectively, and the corresponding 
 bounds of the (— & l) region are labelled C and D respectively. The 
 
 max 
 
 largest upper bound on c, ., namely c, . = I.56 b. . + I.56 u 
 to ** k-n/ k-i k-i n 
 
 (labelled H) and the least lower bound, namely c. . = 0.39 b n . + 0.39 u . 
 
 ' * k-i k-i mm 
 
 (labelled L) are also shown in figure 3« 
 
29 
 
 
 
30 
 
 It is apparent from figure 3> that the choice of q. cannot 
 be made (independent of u) for a good part of the (c, . , b .) plane. 
 
 ■K — 1 K— i 
 
 In particular for i = and the case of the square rooting problem, we 
 do not have a choice. 
 
 It is conceivable to break up the range of u [i.e., [a, b]} 
 into several parts and then obtain the selection lines, since in that 
 case the intersection of all (— &l) regions, when u varies over a smaller 
 range, "will be clearly larger. 
 
 As we started out to solve the problem for 1/2 < u < 1, it 
 
 seems natural to restrict the range of u to [1/2, 1] . But even then, as 
 
 it turns out, satisfactory overlap regions cannot be formed. 
 
 Dividing the range of u into 2 parts, namely [— , — ) and 
 
 \T2 
 
 [— , 1], was chosen first; but this had two disadvantages. Firstly, since 
 
 the selection procedure for the two ranges will be different, we must 
 know, at the outset, which u-range we are in. This means given c , b , 
 
 K. K. 
 
 we should compare c - — b, with — . Except for b. = (i.e., the 
 square -rooting problem), this is not convenient and is inexact in any 
 finite precision machine. Secondly it was very difficult to show that 
 the resulting algorithm is convergent. 
 
 It was then decided to break up the u-range into 3 sections, 
 namely I = [1/2, 5/8), and I = [5/8, 3/k), and I [3/k, 1] . Given the 
 values of c, and b, , the following rules are used to decide the range of u. 
 
 and 
 
 \ => U € I 
 
 c n - tr b. < yf- 
 
 k 8 k bk 
 
31 
 
 < 2) \-8 b ^ll 
 
 and ) => u € I, 
 
 \-i\<t J 
 
 ( j ) C k -K^lf 
 
 and ) => u e I 
 
 c k - \ $ 1 
 
 We now develop the rules of selection for all three u-ranges. 
 
 For the first range, I.. = [1/2, 5/8), the (— & l) region is given by 
 
 0.485 (b, . + u) < c. . ■ 0.72 ("b. . + u). Taking the intersection of 
 k-i — k-i — k-i 
 
 all these regions as u varies over the range I-,, we obtain; for 0.485 
 
 (b k-i + 5 / 8) - c k-i - °* 72 (b k-i + l ); q i+i = 2 or lm Similarl y the 
 
 intersection of all (r- & — ) regions, is; for 0.553 (b, . + 5/8) < 
 
 1 11 
 c, . < 1.12 (b . + — ); q = r or -. These overlap regions are shown 
 
 in figure h. This figure needs some explanation. 
 
 We know that for any i, c. . < I.56 (b, . + u). Therefore the 
 
 k-i — k-i 
 
 largest upper bound on c . is given by c = I.56 (b, . + 5/8) for this 
 range. We call this line H. Similarly the least lower bound on c . is 
 
 given by c . =0.39 (b, . + — ); we call this line L. We call the upper 
 
 1 1 
 bound of (r- & — ) overlap region, A; and its lower bound B. We call the 
 
 upper bound of (l/2 & l) overlap region, C and its lower bound D. 
 
 Note that the region below line A and above line B is the (y- & — ) 
 
 region, or in other words, q. ,, can be chosen as r or - in this area for 
 
 any value of u e I_ • But the area above line A and below line B is a 
 
32 
 
 I 
 
33 
 
 forbidden region, since a choice of q. independent of the value of u 
 
 cannot be made. A similar observation can be made about the (— & l) 
 
 region and thus we also have the (— & l) forbidden region. We should 
 
 now find two selection lines corresponding to these two overlap regions 
 
 so as to make the choice of q. , unique. Clearly, each selection line 
 
 must lie within the respective overlap region, its slope and its intercept 
 
 on the c, . axis must both be "simple" binary numbers and it should pass 
 
 through the vertex of the overlap triangular region as closely as possible. 
 
 We chose line SI in the (r- & r-) region to be c. . = b. . + — 
 
 k 2 k-i k-i 2 
 
 and line S2 in the (— & l) region to be c. . = — h. . + -rf-. 
 
 2 k-i 2 k-i 16 
 
 Thus the following tests need to be made to determine q. n for 
 
 l+l 
 
 any u e I 
 
 (1) "= k _i<iVi + li thenq. +1 =l 
 
 (2) If c k _. > t k _. + | then q. +1 = i 
 
 (3) Otherwise q. ,_ = — . 
 
 l+l 2 
 
 Notice that with the selection lines SI and S2 the forbidden 
 regions are slightly enlarged since the selection lines do not exactly 
 
 pass through the vertex of the respective overlap triangle. 
 
 1 1 
 Thus the (y- & — ) forbidden region, is, the area enclosed by 
 
 lines H, B, SI, L. That is, to the left of the intersection point of 
 
 lines B and SI. Similarly, the (— & l) forbidden region is enclosed 
 
 by lines H, S2, C, L. 
 
 Thus we now have a selection procedure for choosing ^ when 
 
 c, . and b . are within lines H and L, provided that they do not fall 
 
 in the forbidden region. Starting from the first step, if we can make 
 
3U 
 
 sure that at every subsequent step, (c, . , b, . ) stay within this permitted 
 region, the requirement of consistency of the selection procedure will 
 then be satisfied. 
 
 From the range restriction imposed on f. +1 , at the beginning of 
 this chapter it is easily verified that (c, , b, ) are kept between 
 lines H and L. In the next chapter we also show that we never go into 
 the forbidden region. This we do for all the three u-ranges. 
 
 For the second range I = [ 5/8, ~5/K), the intersection of all 
 (- & 1) regions is given by O.I4-85 (b, . + 3A) < c. . < 0.72 (b. . + 5/8). 
 
 c. .K~*l K.—X j£""l 
 
 Similarly the intersection of all (r- & r-) regions, is, O.553 (b . + 3/k) 
 
 < c n . < 1.12 (b. . + 5/8). 
 — k-i — k-i ' 
 
 These overlap regions are shown in figure 5« Labelling of lines 
 is similar to the range I- . Thus, line H is, c . = I.56 (b . + 3/k)* 
 
 Line L is, c, . = 0.39 (\._- + 5/8). We choose selection line SI as 
 
 1 3 
 c, . = b, . + 5/8 and selection line S2 as c, . = — b, . + s> 
 k-i k-i ' k-i 2 k-i 8 
 
 As before, the (r- & — ) forbidden region is to the left of the 
 point of intersection of lines SI and B, and is enclosed by lines H, B, 
 SI and L. The (— & l) forbidden region is to the left of the point of 
 intersection of lines S2 and C, and is enclosed by lines H, S2, C and L. 
 
 For the third range I = [3/^, 1], the intersection of all 
 
 (| & 1) regions is given by, 0A85 (b^ + l) < c^_ ± < O.72 (b^ + 3/k). 
 
 1 1 
 Similarly the intersection of all (j- & — ) regions, is, 0.553 (b, . + l) 
 
 These overlap regions are shown in figure 6. Labelling of lines 
 
 is similar to the previous ranges. Thus line H is, a, . = I.56 (b. . + l). 
 
 ' k-i k-i 
 
 Line L is, c . = 0.39 (b, • + 3A)» We choose the selection line SI as 
 
35 
 
 i 
 
36 
 
 
37 
 
 3 11 
 
 c, . = b, . + i and selection line S2 as c, . = — b. . + — . Forbidden 
 k-i k-i 4 k-i 2 k-i 2 
 
 regions are as in previous ranges. 
 
 Although this general selection procedure is applicable for all 
 
 i > 0, we want to use a special procedure for the case i = 0. This is 
 
 because initial tests are necessary to decide the range of u. We want 
 
 to use these same tests for deciding q . 
 
 We have observed earlier that for i = 0, f . = u. Then from 
 
 l 
 
 our previous analysis, 
 for q = 1/2 
 
 0.485 < f = u < 1.124 
 and for q = 1 
 
 0.39 < f = u < 0.72. 
 
 ~ 
 
 Then for u e I we choose q = 1 and for u e I or I we choose q = l/2. 
 
 Notice that for all three u-ranges the selection line SI is of the form 
 
 c, . = b, . + kl. Thus the slope of SI does not change with the range, 
 k-i k-i ' 
 
 only the intercept on the c. . axis changes. Similarly line S2 is of the 
 
 form c. . = — b, . + k2. We take advantage of this fact in writing the 
 k-i 2 k-i 
 
 complete algorithm that follows. In the first step of the algorithm, 
 while deciding the range of u, we set two switching variables J and J 
 as appropriate. These two switching variables later decide kl and k2. 
 
 We now give the complete algorithm, which solves a quadratic 
 
 2 11 
 
 equation x + b, x - c, = with b, > and (a. - b, < 1, c_ - — b n > 7-) 
 * k k k- kk-'k2k-4 
 
 and gives us the positive root, u, of the above equation. 
 
 ALGORITHM QD: 
 
 QD-0: [check] If b < then exit, no solution. 
 
 If (c. - J b. ) < f or if 
 k 2 k 4 
 
38 
 
 (c - t>, ) > 1 then exit, no solution. 
 K K. 
 
 QD-1: [range ] Now set J. «- J «- 0; 
 If c, - *• t>, < rr then set q *- 1 
 
 iC O K. 0*t -L 
 
 and go to step QD-2; 
 
 1 
 set q ± «- -; 
 
 If c. - rb. < rr then set J, «- 1 and 
 k 4 k 16 1 
 
 go to step QD-2; 
 
 otherwise set J *- 1; 
 
 QD-2: [ Init] Set P Q - 0, Q Q - 1, V ± «- 1, G^ «- q^ 
 
 QD-2: [ ] Set b^ - q^ 
 
 C k-1 - 1 + *L<VW 
 i ^ 2 
 
 QD-4: [select] If c k _ i+1 > (b k _ i+1 + f + -f + -jf) then 
 set q. *- r and go to step QD-5; 
 
 If c k-i + i ^ ( l Vw + if + il + ir } then 
 
 set q. «- 1 and go step QD-5; 
 otherwise set q. «- — ; 
 
 QD-5: [advance] 
 
 Vi - Vk-i+i ■ Vi c k-i +2 + Vi 
 
 C k-i <" q i (b k-i + l - Vi } + C k-i + 2 
 
 +2 
 
39 
 
 ■ Vi-1 -i-2 
 i *- i + 1 
 
 QP-6: [loop test] If i < i then go to step Qtf)-k; 
 
 QD-7: [final] u (=ROOT) «- P./Q. • 
 
 The value of i will be determined by the desired precision 
 
 max * 
 
 of the result in case this algorithm is implemented in hardware. If this 
 
 algorithm is implemented in software, however, the value of i will be 
 
 max 
 
 determined by the allowable error. 
 
ko 
 
 5. PROOF OF CONVERGENCE 
 
 We have given algorithm QD in the previous chapter. In this 
 chapter we prove that algorithm QX> is convergent. (For the conditions 
 specified in that algorithm, i.e., b. > 0, and c - — b, > r- and 
 
 Our strategy will be, first to prove that the rules of selection 
 given in algorithm OJ) are consistent. Then using theorem-1 (chapter 2) 
 we show convergence. We also show that the residual approaches zero as 
 the number of iterations increases. 
 
 We first prove a lemma to be used later. 
 
 Lemma 2 The following re suits [2] hold for n > 0. 
 
 n-1 
 
 Q 
 
 n-1' 
 
 n 
 
 Q. 
 
 n 
 
 /P A 
 n-1 
 
 Q. 
 
 h-l' 
 
 b k - c k = (-1) 
 
 r: b k-n 
 
 n n-1 
 
 (5.D 
 
 'P \ 2 /P 
 n| .In 
 
 Q 
 
 n 
 
 + 
 
 Qu. 
 
 n 
 
 n 
 
 \~\= ( " 1} 
 
 Q. 
 
 n+l k-n 
 
 Q. 
 
 n 
 
 'k-n Q 
 
 h-l 
 
 ZL_ ( b _ v ) 
 Q n k-n k 
 n-1 
 
 (5.2) 
 
 (5.3) 
 
 Proof Consider the expansion of u up to q. 
 
 u = 
 
 1-, + 
 
 1 *2 + , 
 
 "k-n 
 
 ^ + b v + u 
 k-n 
 
+1 
 
 Consider c, to be (n + l) J partial numerator and (t>, + u) 
 k-n k-n 
 
 st 
 to be (n + l) partial denominator and use standard recursions (2.1) 
 
 to get 
 
 and 
 
 also 
 
 P» . = (b. + U )P + cl P , 
 n+1 k-n n k-n n-1 
 
 Q 1 ,, = (b. + u)Q + c. Q . 
 n+1 k-n n k-n n-1 
 
 u 
 
 P'_ (b. + u)P + c. P . 
 
 n+1 k-n n k-n n-1 
 
 Q' = T^ + u)Q + c. Q " 
 
 n+1 k-n n k-n n-1 
 
 which gives the equation 
 
 b. Q + c. Q . - P b, P + c P . 
 2 , k-n n k-n n-1 n k-n n k-n n-1 = 0. 
 
 U +U Q Q 
 
 n n 
 
 2 
 Recall that u is the root of the quadratic x + xb - c = 0. 
 
 Therefore comparing coefficients, we get 
 
 b. Q + c. a , - P 
 , k-n n k-n n-1 n /_ . \ 
 
 b k = q (5A) 
 
 n 
 
 and 
 
 k-n n k-n n-1 
 
 C k " Q 
 n 
 
 (5-5) 
 
 By rearranging (5»+) w © get equation (5*3) • By eliminating 
 c between equations (5*3) and (5«+) and then using the identity 
 
 i£.""Tl 
 
 P Q - Q P _ = (-1) we get equation (5.1). Similarly by eliminating 
 n n-1 n n-1 
 
 b, between equations (5«3) and (5«+) and again using the above identity, 
 we get equation (5*2). Q.E.D. 
 
 Now we prove that the rules of selection of partial denominators 
 are consistent. For this, we first prove that for all i > 0, the points 
 
k2 
 
 (c, . , b, . ) remain within the area enclosed by lines H and L in figures k, 
 k-i' k-i ' 
 
 5 or 6 as the case may be, depending the u-range under consideration. For 
 i = 0, this is quite clearly true. For all i > 0, we had put a 
 restriction on f. +1 > namely, 
 
 c k-i -1 
 
 0.39 < f.^, = ^ j. — < 1-56, 
 
 - l+l b. . . + u - ' * 
 k-i-1 
 
 which may be written as, 
 
 °- 39 Vi-i + u) * = k .i-i * *-* (b k-i-i + u) > 
 
 which clearly shows that we are always within the limits of lines H and 
 
 L. Next, we have to show that we never get inside the forbidden regions. 
 
 In Lemma 2, we have shown that for all i > 0: c, . and b, . 
 ' J k-i k-i 
 
 satisfy the equation 
 
 P i \ 
 
 a. . = ~ -s (b, . - b. ). 
 
 k-i Q. _ Q. , k-i k' 
 
 l-l i-I 
 
 The line of closest approach to the forbidden regions, or alternatively, 
 the leftmost line is given by 
 
 Vi = oM . " qT7 . ( Vi - V 
 
 I i-l' mm v i-I ' mm 
 
 Since we have b > 0, the worst case is then b = 0. Thus leftmost line 
 
 K. K. 
 
 is given by 
 
 lQ i-l> 
 
 P. 
 l 
 
 ,Q. J . \-i. 
 mm ' i-l' mm 
 
+3 
 
 It is necessary to discuss each one of the three ranges 
 separately. It is also necessary to discuss the cases of even and odd 
 values of i, separately. 
 
 Consider the range I . As we noted earlier, we will consider 
 the case b. = 0, since this is the worst case. 
 
 Now for 
 
 \=° 
 
 ib c k < § 
 
 q i = 1 
 
 p Q 
 
 P = 1, Q = 1, r = 1, ^ = 1, 
 
 C k-1 = X " \-l 
 
 1 25 
 
 k - k-1 64 
 
 We call this segment P. This segment is clearly within the overlap 
 
 regions, as shown in figure 7» 
 
 Case (l) i is odd - range I 
 
 For i = 1, we have seen that we don't go into the forbidden 
 
 P. 
 regions. For i > 3> we first get a lower bound on •=—. We use a theorem[ll 
 
 l 
 which states that odd ordered convergents approach the value of an 
 
 infinite continued fraction from above (and even ordered convergents 
 
 approach from below). Thus 
 
 /P. 
 
 l 
 
 mm 
 — u e I. 
 
 (u) = 
 
 1 
 
 2 
 
 i odd 
 
 It is also clear that 
 
 'Q. 
 l 
 
 >%-! 
 
 . 1 . 1 
 
 ? 
 
 - k ' 1 +1 ' 
 
 i > 3 1 
 odd k 
 
 20 
 
kk 
 
 a> 
 
 bO 
 
 El 
 
45 
 
 Thus 
 
 P. \ 
 
 1 
 
 Wi-i 
 
 >-d. 
 
 i odd > 3 
 
 Therefore the leftmost line for odd i is given by 
 
 c =r-2- ^ b .We call this line OLM, and is shown in figure 7. 
 
 k-i kO 20 k-i 
 
 We can see that this line is well within the overlap regions. 
 
 Case (2) i even - range I 
 
 From figure 7* it is clear that cu = — for the whole region I . 
 
 Then P g 1 
 
 Now again using the theorem quoted in the previous case, 
 
 2tl > i 
 
 i even > 2 
 
 Next notice that 
 
 Q. 
 
 > — + > — + - 
 
 Q J - k 1-i X k 1 + 1 
 
 i even 
 
 • 
 
 "1 
 
 l 
 
 The fraction on the right is an infinite continued fraction 
 and is easily evaluated to be 0.640388. Thus, we have 
 
 P. i , 
 
 > 0.640388* ~ 
 
 i even > 2 
 
k6 
 
 Thus the leftmost line for even values of i, is given by 
 
 c, . = 0.2135 - 0.64 b, . 
 k-i k-i 
 
 We call this line ELM. From figure 7, it is clear that this line is 
 
 well within the overlap regions. 
 
 Now consider the second range I . For b, = and £T < c < •?••?■, 
 
 1 P l Q l 1 
 
 q = 1/2. Therefore ^ = 1, ^ = -, ^- = 1, ^- = -. Thus c^ = 
 
 1 25 9 
 
 1 - — b and — § < "h, _ < r*-. This line segment is shown in figure 8 
 
 d k-1 120 ~ K-J. .Jd 
 
 and is seen to be well within the overlap regions. We call this line 
 
 segment P. It is also clear from figure 8 that only possible values of 
 
 p 
 11 2 2 2 
 
 cu are j- and — . Corresponding values of pr— are — and — respectively. 
 
 Case (3) 
 
 i odd - range I, 
 
 We have 
 
 fP. 1 
 
 l 
 
 IV 
 
 i odd > 3 
 
 min (u) = 
 - u e Ig y/ 
 
 As before, 
 
 Q. 
 
 l 
 
 Vl< 
 
 > J. 
 
 - 20* 
 
 i odd > 3 
 
 Q 
 
 1-1 
 
 > jf - 0.281 
 
 i odd > 3 
 
 Thus OLM is given by c, . = 0.281 - 0A5 b n .. This line is clearly 
 
 k-i k-i 
 
 within limits as shown in figure 8. 
 
 Case (k-) i even - range I, 
 
 We have 
 
 /P. \ 
 
 1 
 
 \% 
 
 >-!> 
 
 i even > 2 
 
1*7 
 
 
 CO 
 
 0) 
 
 no 
 
 •H 
 
k8 
 
 \ \ 
 
 
 1 
 
 even > 2 
 
 ?i 1 
 
 
 KJ t 
 
 even > 2 
 
 0. 6^0388, 
 
 > o.ite. 
 
 Thus ELM is given by 
 
 c, . = 0.3^2 - 0.6^ b n . 
 k-i k-i 
 
 which is also within limits as shown in figure 8. 
 Now consider the third range, I_. For 
 
 b k = and ^ < c k < 1, ^ - | 
 
 P l Q l 
 /. P . 1, Q = 1/2, ^ = 1, f- = 1/2 
 
 T> 
 
 Vl - X " I Vl 32 S \-i 2 1 
 
 is the line segment which is the reflection of the initial line segment. 
 It is clear that this segment (called P) is within limits and also that 
 cu = 1/2. Then 
 
 P 2 Q 2 
 P 2 = 1/z, Q 2 = yk, £•»!, ^ = 5/2. 
 
 Thus the second reflection is given by c, = 1 - 5/2 b, . With the 
 endpoints (c, ) = 0.595 and (a. c % = 1.32. 
 
 This line segment is once again well within limits and q, = — 
 
 1 
 or jj.. 
 
Case (5) i odd - range I 
 
 ^9 
 
 fP. 
 
 1 
 
 A,, 
 
 1 i odd > 3 
 
 > 3A , 
 
 \ \ 
 
 \-l> 
 
 > -1 
 
 - 20 * 
 
 i odd > 3 
 
 Thus OLM is given by c = 0.3375 - 0.^5 b .. This line is well 
 within limits as shown in figure 9« 
 
 Case (6) i even - range I, 
 
 We have 
 
 q-L = 1/2, qg = 1/2, q ? = - or jj- 
 
 1 1 , 
 q l = h ° r 2 ° r 1 
 
 Minimum rr- - 
 
 1 
 
 \ i + i 
 
 2 11 
 
 2 1,1 
 2 1 
 
 26 
 
 ^9 
 
 0.53. 
 
 Therefore 
 
 TP. 
 
 IT 
 > 0.53 
 
 1 even 
 
 > k 
 
 Q. 
 
 Q 
 
 > 0.64. 
 
 i-l' . 
 
 1 even 
 
 Therefore ELM is given by c, . = 0.34 - 0.64 b, . . This line is within 
 
 limits as shown in figure 9» 
 
CD 
 
 CM 
 
 50 
 
 l 
 
 
 
 
 Q./ > 
 
 
 -I 
 
 
 
 
 •-4 
 
 
 
 
 
 7 
 
 
 
 
 
 
 
 
 
 ^0^^'-* 
 
 
 
 
 
 
 o^^ 
 
 
 
 
 
 
 
 iV 
 
 
 
 2 
 -l 
 LJ 
 
 / 2 
 
 o 
 
 \ N \ 
 
 %\ 
 
 \\ \ \ \ 
 w \\\ 
 
 ON 
 
 bO 
 
 S 
 
 \ 
 \ 
 \ 
 \ 
 
 ^ \ 
 «4 \ 
 
 \ 
 
51 
 
 Thus we have shown that our selection procedure is consistent. 
 We can now use theorem-1. We have a consistent method of expansion of u 
 into a continued fraction (though u is unknown here, but it does not 
 matter), m = r > 0. Clearly initial errors 6 and 5 are finite. Thus 
 all conditions of theorem-1 are met and thus we conclude that algorithm 
 QD is convergent. 
 
 We now prove an auxilliary result. This is that c . and b, . 
 are bounded above (we have just shown that they are bounded below). This 
 fact can be used in hardware implementation of the algorithm in that a 
 fixed point register can be used to store the quantities c, . and b, . . 
 
 l£ — 1 i£— 1 
 
 It will also be helpful in showing that the residual (to be defined 
 
 shortly) approaches zero as i increases. 
 
 P. Q. 
 
 We know that for any i > 0, we have, c, . = -r - t (b, . - b, ) 
 
 ' ' k-i Q. , 0.. n k-i k' 
 
 l-l l-l 
 
 We also know that c . < 1. 56 b, . + I.56. The largest positive c . will 
 
 K." 1 K — 1 K— 1 
 
 then be given by the intersection of these two lines with appropriate 
 extremal values of the quantities involved. The intersection is 
 
 given by, p 
 
 c 
 
 cj 
 
 k-i 1 Q. , 
 
 1 l-l 
 
 1755" Q, 
 
 n^ ^ /P. 
 
 Therefore 1 
 
 (c, .) 
 
 Q. I + 1 + b. 
 v 1' max k 
 
 'k-i max 1 1 
 
 "T" 
 
 I.56 
 
 1 
 
 max 
 
52 
 
 For all three u-ranges, we have, (q n ) . = 1/2 and since odd 
 
 l mm ' 
 
 ordered convergents approach the root from above and also since all 
 even convergents are smaller than all odd convergents, we have 
 
 max 2 
 
 We also have, 
 
 - 1+i- 5 
 
 Q. - " 1 
 
 1-1' r- 
 
 max 4 
 
 2 + 1 + b n 
 k 
 
 C k-i - 5755 + 0.2 
 max 
 
 = 3-57 + 1.2 b k 
 
 Thus for any given b, , c . is bounded above. Similarly 
 
 K. K."2. 
 
 taking the intersection of line (5«3) with line L. We can get a bound 
 
 on b, 
 k-i 
 
 Now define residual at step i by 
 
 /P. \ 2 T 
 r. = ~ + b. 
 
 i 
 
 \\i 
 
 - \ ■ 
 
 Using equation (5.1), we have 
 
 r. = (-l) i+1 3fct 
 
 i 
 
53 
 
 From the recursion Q,. = q.Q. . + Q. it is clear that 
 
 1 T. l-l i-2 7 
 
 Q. > Q. . Therefore Qu . and CL form two increasing sequences as 
 
 ,i increases. Since c, .is hounded, we must have r. -» as i -» oo. 
 k-i ' l 
 
54 
 
 6. CONCLUSIONS 
 
 To make practical use of the continued fraction representation 
 of numbers, we need to develop algorithms for many more functions. This 
 is an open area of research. What has been shown in this paper is just 
 a beginning. 
 
 We now compare the algorithm QD of this paper with standard 
 methods of solving for the root u of the quadratic 
 
 o 
 x + "b, x - c. = = (x-u) (x+v) . 
 
 Then r 
 
 u- g 
 
 Neglecting operations like shift and add, we thus need a sqaure root and 
 a multiplication to he carried out by standard methods. 
 
 In the IBM-360[1] square root subroutine, use is made of the 
 Newt on -Ralph son iterative technique. For a single precision result two 
 iterative steps need be carried out. Each of these steps essentially 
 amounts to one division. Finding a suitable initial approximation also 
 amounts to a division to be carried out. Thus all in all the solving 
 for u essentially amounts to one multiplication and three division 
 operations. Each of these operations is about ten times slower than one 
 addition in the IBM 36o/75» Thus approximately forty additions yield 
 the root u of the quadratic. Our algorithm QD compares favorably with 
 
55 
 
 this "because on the average it requires less than forty iterations to 
 get a single precision result. Further, the author believes that it is 
 possible to improve the selection procedure of algorithm QD, so as to 
 improve the rate of convergence of that algorithm. 
 
 A detailed study of the convergence behavior of this algorithm 
 is desired. Such a study may have to be experimental. A mathematical 
 analysis of the algorithm is made difficult by the fact that b, ., c, . 
 at step i + 1 depend not only on the present b . , c . values, but also 
 on the immediately preceeding ones. In other words, the next state is 
 a function not only of the present state but also of the immediately 
 past state. 
 
56 
 
 LIST OF REFERENCES 
 
 [1] Wall, H., "Analytic Theory of Continued Fractions," Van Nostrand, 
 New York, 1950. 
 
 [2] Robertson, J. E., Private communication, 1971' 
 
 [3] DeLugish, B. G., "A Class of Algorithms for Automatic Evaluation 
 of Certain Elementary Functions in a Binary Computer, " 
 Report 399, Department of Computer Science, University of 
 Illinois, Urbana, Illinois, 1970. 
 
 [4] IBM System/360 Operating System FORTRAN IV Library, Mathematical 
 and Service Subprograms, Form GC28-6818-0. 
 
 [5] Khinchine, A. Ya., "Continued Fractions," Moscow-Leningrad State 
 Publishing House, 19^9. 
 
 [6] Khovanskii, A. N., "The Application of Continued Fractions," 
 P. Noordhoff N. V. - Groningen - The Netherlands. 
 
 [7] Buchholz, W., "Choosing a Number Base," in "Planning a Computer 
 System," Ed. Buchholz, W., McGraw Hill, I962. 
 
 [8] Robertson, J. E., Class notes for C. S. 39^, University of Illinois 
 at Urbana -Champaign. 
 
 [9] Bracha, A., Private communication, 1971. 
 
APPENDIX I 57 
 
 A FORTRAN PROGRAM IMPLEMENTING THE ALGORITHM QD 
 
 FORTRAN IV G LEVEL 13 MAIN DATE = 721fO 
 
 C THIS IS A FORTRAN PRCGRAM THAT SOLVES FOR THE SMALLER 
 
 C POSITIVE *CCT CF THE QUADRATIC X'-"2*PKNPl •" X - CKNPUO; 
 
 C (USING ALGORITHM QC) TO TEN CIGIT ACCURACY. 
 
 0001 IMPLICIT REAL 8(A-h,Q-Z) 
 
 0002 REALMS K1.K2 
 
 C SETT ING U° TEST CATA 
 
 00C3 OIMtNSION CK(4),PK(A) 
 
 000* CK(1)=0.5 
 
 0005 BM1 ) = C.O 
 
 0006 CK(2)=.625 
 
 0007 e«(2)=0.0 
 
 0008 CK(3)=i.25 
 
 0009 BK(3»s.75 
 
 0010 CKK)=2.125 
 
 0011 BK<4)=1.5 
 
 0012 CO 200 J=l ,4 
 
 0013 CKNP1=CK(J) 
 
 0014 eKNPl=RK(J) 
 C STEP 0D_0 
 
 0015 IFICKNP1-.5-BKNP1.LT..25.0R.CKNP1-RKNP1.GT.1..0R. 
 - BKNP1.LT.0.) GC TO 200 
 
 C FIND THE "COT PY THE STANDARD PETHCO FOR COMPARISON 
 
 0016 Rl=.5D0(-HKNPl*CSCRT(»<NPl'«-2*4.-CKNPl)J 
 
 0017 WR1TE(6,75) CKNPl.GKNPL 
 
 0018 75 FORMATt'l* >' *-*■** '''*"* , ****■*******"**** a, ** ,c ''' : ■ : ' > '* : * [ '*' , *' 4 ' , '** 
 
 .• H *t *.,.**!/ it.-M a cK=«, 2 5. 16, ••• 8K= • ,0 15. 7, 
 -iM*M+^m*i/< STEP' ,T11 ,' C( K-M' , T25, '8<<-NI ' ,T*0, 
 -• (N )• ,T5e, 'RCCT ', T79, 'ERROR' ) 
 C STEP 0D_1 
 
 0019 250 1=1 
 
 0020 IF ( (CKNPl-.e25CO*8K\Pl ) .L T . 25. C0/6*t . CO ) GO TO 101 
 
 0021 SN=. 500 
 
 0022 IFKCKNP1-.75P0' PKNPD.LT. .562500) GO TO 102 
 
 0023 K1=.75D0 
 
 0024 K2=.5D0 
 
 0025 JO TC 2 
 
 0026 101 SN=1.D0 
 
 0027 K1=.5C0 
 C028 K2=. 3125DO 
 
 0029 GO TO 2 
 
 0030 102 Kl=. 62500 
 
 0031 K2=. 37500 
 
58 
 
 
 C 
 
 0032 
 
 2 
 
 0033 
 
 
 0024 
 
 
 0035 
 
 
 0036 
 
 
 0037 
 
 
 0038 
 
 
 0039 
 
 
 
 C 
 
 0040 
 
 100 
 
 00 41 
 
 
 004? 
 
 
 0043 
 
 500 
 
 0044 
 
 
 0045 
 
 i 
 
 0046 
 
 
 0047 
 
 2 5" 
 
 0048 
 
 100 
 
 0049 
 
 
 0050 
 
 
 0051 
 
 85 
 
 005? 
 
 
 0053 
 
 
 00 54 
 
 
 0055 
 
 
 0056 
 
 
 0057 
 
 
 0058 
 
 
 0059 
 
 
 
 C 
 
 0060 
 
 10 
 
 0061 
 
 
 0062 
 
 
 0063 
 
 
 0064 
 
 
 0065 
 
 
 0066 
 
 
 
 C 
 
 0067 
 
 
 0068 
 
 200 
 
 0069 
 
 
 STEP QD_? ANC STEP 0C_3 
 
 BKK=SKiCKNPl 
 
 CKN=1.C0-SN« (PKN-8KNP1 ) 
 
 SM=SN 
 
 PM.OC 
 
 C*SN 
 
 R = P/Q 
 
 PM1=0. 
 
 0^1=1.00 
 STEP QD_<- 
 
 TEPP = CKN-.5nO r BKN 
 
 IF (TEyP.LE.K2) GC 1C 1 
 
 IF(CKh>-RKN.GT.Kl ) GO TO 25 
 
 SN = . 5C0 
 
 GO TO 100 
 
 SN=1.D0 
 
 GO TO 100 
 
 SN=.25DO 
 
 RKNP2=BKNP1 
 
 FRR0P=R-P1 
 
 WRITE (6, 85 ) I ,CKN,BKN,SM ,R, ERROR 
 
 FORMATC «,I<., 3D14. 5, D25. 16,014.5) 
 
 BKNP1=BKN 
 
 CKNP2=CKNP1 
 
 CKNP1=CKN 
 
 PV2 = PM 
 
 PM1 = P ... __ 
 
 CM2=CM 
 
 QM1 = 
 
 1=1 + 1 
 STEP QD_5 
 
 BKN = SN*CKNPl-SM*CKNP2*«KiNP2 
 
 CKN=SN ; -(BKNPi-RKM*r:KNP2 
 
 paSN'PMl+PM2 
 Q = SN'-qyi+C^2 
 R=P/0 
 SN1=SN 
 
 T=CABS(R-P.l ) 
 STEP 0C_6 
 
 IFIT.GT. .50-10. AND. I. LT. 0501 GO TO 1000 
 
 CONT INUE 
 
 ENC 
 
APPENDIX II 
 
 COMPUTER PRINTOUTS OF A FEW PROBLEMS SOLVED 
 
 USING THE PROGRAM IN APPENDIX I 
 
 59 
 
 rep 
 1 
 
 2 
 3 
 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 
 ♦ **«■»**» 
 0.50C 
 C(K-N> 
 0.375000 
 0. 5M25D 
 0.929690 
 0.512210 
 0. 9*5930 
 0.50*360 
 0.°672 70 
 0.50016O 
 0.969540 
 0.500=50 
 0.963910 
 0.506140 
 0.94 75 00 
 0.519400 
 0.911H20 
 0. 544C50 
 0.833490 
 0. 5 = 6310 
 0. 69=690 
 0.721770 
 0.668060 
 0.6e62?n 
 0.696550 
 0.65 76 70 
 0.736340 
 0.597580 
 0.831730 
 0.572850 
 0. 841950 
 0.586720 
 0.772770 
 0.6C94C0 
 0.790940 
 0.627050 
 0.697730 
 0. 7C2590 
 0.620970 
 0. 7 = 9760 
 0.600030 
 0.791610 
 0.629*30 
 0.673950 
 0.7362C0 
 0.658900 
 0. 693o20 
 0.692800 
 0.659920 
 0.73472 n 
 0.599290 
 
 00000000 
 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 
 oc 
 
 00 
 00 
 00 
 
 oc 
 
 00 
 00 
 
 00 
 00 
 00 
 00 
 00 
 
 
 oc 
 
 00 
 
 oc 
 
 00 
 00 
 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 
 oc 
 
 00 
 
 oc 
 
 00 
 00 
 
 0. 
 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 
 c. 
 
 0. 
 
 c. 
 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 
 c. 
 
 0. 
 
 c. 
 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 
 c. 
 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 
 00 
 
 CO 
 00 
 CO 
 00 
 00 
 00 
 00 
 
 OOOOOn CO"" 
 R(K-M 
 260001 OC 
 H750O 00 
 79125n-01 
 164^00 00 
 10 1810 00 
 13 719 
 114*10 
 127-iin 
 
 122770 
 
 119610 
 
 130360 
 
 110120 
 
 142950 
 
 9392'D-C1 
 
 165230 00 
 
 626730-01 
 
 20=340 OC 
 
 27721D-C? 
 
 297«30 00 
 
 46=640-01 
 
 133480 OC 
 
 200650 
 
 143570 
 
 204710 
 
 12413 r < 
 
 244290 
 
 545000-01 
 
 15 34 30 OC 
 
 132 990 CO 
 
 774360-01 
 
 215870 OC 
 
 17052^ 00 
 
 134180 00 
 
 63554Q-01 
 
 24997n 00 
 
 988910-OL 
 
 25 2410 CC 
 
 580800-01 
 
 141 860 00 
 
 1 5 R 1 * n CO 
 
 307^.00-01 
 
 2>506Q 
 
 619'. 2 0-01 
 
 122140 OC 
 
 207310 
 
 13=600 
 
 206900 
 
 123G60 
 
 244310 
 
 CC 
 
 CO 
 
 oc 
 
 
 00 
 
 oc 
 
 00 
 
 oc 
 
 CO 
 
 
 *-BK = 0.0 ***♦*»**?»»* 
 
 <Nl ROOT 
 
 C. 500)01 00 0.2000000000000JOOO 01 
 
 0.5O03UO 00 0.40000000000000000 00 
 
 0.500JCD OC 0. lllillllll 1111 1 10 01 
 
 0.250000 00 0.5306122^489795920 00 
 
 C.5oO)CO 00 0.8760330573512397O 00 
 
 0.250300 00 0.61208576998050680 00 
 
 0.500301 00 0.734604996623=0230 00 
 
 0. 250300 OC 0.65733343254252460 OC 
 
 0.500)00 00 0. 7*309123090403260 00 
 
 0.2500CO OC 0.6820150371C97339O OC 
 
 0.500)00 00 0.72459^2091607b730 00 
 
 C.250)CO OC 0. 69438908275^43420 00 
 
 0.50C0CO 00 0.7156743^051471230 00 
 
 C. 250)00 00 0. 7006173609260t770 00 
 
 0.500)00 00 0. 71116751613373510 CC 
 
 C.25COCO 00 0.70372516162526470 00 
 
 0.50CCCO 00 C. 7C895028040160920 00 
 
 0.250000 00 0.7052695146*472500 CO 
 
 0.500)00 00 0.7079562916=026660 00 
 
 0.5O03CO 00 0.70645129039125050 00 
 
 C.250J0O OC C. 70755444632135710 00 
 
 0.500000 00 0.7063570c499652190 00 
 
 C.50OC0 00 0. 7072722570461130D 00 
 
 0.500)00 00 0.70701562197534710 00 
 
 0.5O0J0O 00 0.70717072206090220 00 
 
 0.500)CD 00 0.70707567373303410 OC 
 
 0.500)00 00 0.7O71334333797055O 00 
 
 C. 250000 OC 0.707089633^2392810 CO 
 
 0.500000 00 0.70711849989180260 00 
 
 C.25OC0 OC C. 70709737756716120 00 
 
 0.500000 00 0.7071U7362014359O 00 
 
 0.5C00CO 00 0. 7071037210922786D 00 
 
 0.500100 00 0.70710836515513350 00 
 
 0.250)00 OC 0.70710504JQ4073090 00 
 
 0.500)C0 00 0. 707107612 , 8-;02540 00 
 
 0.500000 00 0.70710615395251530 00 
 
 0.50CCCO 00 0. 707107C7642497440 00 
 
 0.500)0:) 00 0.70710652907065200 00 
 
 0. 250)00 OC 0. 7071 069490469053D 00 
 
 0.50COOO 00 0. 70710oc746P971 740 OC 
 
 0.250)00 00 0.70710637634742 190 00 
 
 0.500301 00 0.70710673=32672070 00 
 
 0.500)00 00 0.^0710^31630*27290 00 
 
 0.250)00 OC 0.70710675641231900 00 
 
 0.5COOOD 00 0.7071067=472752090 00 
 
 C.50CCC0 00 0.707106772107=9^00 00 
 
 0.500000 00 0.70710o79615'.9251D CO 
 
 0.500)C0 00 C. 7071067776 = 111720 00 
 
 0.500CCD 00 C. 707106732886o5360 00 
 
 «***»* *****«*»**4*X 
 
 ERROR 
 
 0.12929C 01 
 -0.30711D 00 
 
 0.404000 00 
 -0.17649D 00 
 
 0.163 93 00 
 -0.950210-01 
 
 0.77493C-01 
 -0.492 730-01 
 
 0.368340-01 
 -0.250=2C-Oi 
 
 0.17787D-01 
 -0.127170-01 
 
 0. 856810-02 
 -0.64394 0-02 
 
 0.406070-02 
 -0.338160-02 
 
 0.1 8435C-02 
 -0.183730-02 
 
 0.749500-03 
 -0.655490-03 
 
 0.44767C-03 
 -0.249720-03 
 
 0.16543C-03 
 -0.91 15 90- 04 
 
 0.63 Q 41C-04 
 -0.3 1102 0-04 
 
 0.266520-04 
 -0.171430-04 
 
 0.117190-0 4 
 -0.94036C-0S 
 
 0.500500-05 
 -0. 306010-05 
 
 0.208400-05 
 -0.174020-05 
 
 0.3312 00-06 
 -0.627230-06 
 
 0.297240-06 
 -0.252120-06 
 
 0.167860-06 
 -0. 106500-06 
 
 0.95161 0-07 
 -0. 413600-07 
 
 O.35120C-07 
 -0.24774C-07 
 
 0.135410-07 
 -0.90785C-0R 
 
 0.496 840-03 
 -0.349540-03 
 
 0. 170030-08 
 
6o 
 
 **»*CK = 
 
 t 0.^2 C 00000C 
 
 STEP 
 
 CIK-N) 
 
 1 
 
 0.843750 00 
 
 2 
 
 0.726560 00 
 
 3 
 
 0.7714PD 00 
 
 4 
 
 0.7P76C0 0C 
 
 5 
 
 0. 70**20 00 
 
 6 
 
 0.872960 00 
 
 7 
 
 0.697460 00 
 
 8 
 
 0.82558C 00 
 
 9 
 
 0.712840 00 
 
 10 
 
 0.338400 00 
 
 11 
 
 0.668630 00 
 
 12 
 
 0.925060 00 
 
 13 
 
 0.651060 00 
 
 14 
 
 0.913060 00 
 
 15 
 
 0.597560 00 
 
 16 
 
 0.879050 00 
 
 17 
 
 O.^935o0 00 
 
 .18 
 
 0. e29390 00 
 
 19 
 
 0.709280 00 
 
 20 
 
 0.843710 OC 
 
 21 
 
 0.661350 00 
 
 22 
 
 0.937230 00 
 
 23 
 
 0.638680 00 
 
 ..24 
 
 0.940050 00 
 
 25 
 
 0.658360 00 
 
 26 
 
 0.853630 00 
 
 27 
 
 C. 6^5970 00 
 
 28 
 
 0.855430 00 
 
 29 
 
 0.654290 00 
 
 . . 30 
 
 0.9*7390 00 
 
 31 
 
 0.6303 c 00 
 
 32 
 
 0. 954S C 00 
 
 33 
 
 0.646320 00 
 
 . 34 
 
 0.881820 00 
 
 35 
 
 0.660520 00 
 
 36 
 
 0.922950 OC 
 
 37 
 
 0.664830 00 
 
 38 
 
 0.86 34 80 OC 
 
 39 
 
 0.674640 00 
 
 40 
 
 0.900880 00 
 
 41 
 
 0.68^ Q 60 00 
 
 .. 42 
 
 0.82"* 85 
 
 43 
 
 0.726020 00 
 
 44 
 
 0.806250 00 
 
 45 
 
 0.723560 00 
 
 46 
 
 0.829380 00 
 
 47 
 
 0.673980 00 
 
 48 
 
 0.917810 00 
 
 49 
 
 0.65665D 00 
 
 CJCOOOOO 00--H 
 
 B( K-N) 
 0. 312500 00 
 0. 109"»6D 00 
 0.253910 00 
 0. 1318A L > 00 
 0.26l c 60 00 
 0.912400-01 
 0.12699H 00 
 0.221750 00 
 0. 1910*1) 00 
 0. 165380 00 
 C. 253820 00 
 0.80*97n-01 
 0.150770 00 
 0.174760 00 
 0.23 17 70 
 0. 315790 00 
 0. 123740 00 
 0. 223050 OC 
 0. 191640 00 
 0. 163C00 00 
 0.258860 OC 
 C. 718180-01 
 0.16249H 00 
 0. 156850 00 
 0. 781620-01 
 0.25102^ 00 
 0. 1758CC OC 
 0. 172190 00 
 0.25553D CC 
 0. 716180-01 
 0. 165230 00 
 0. 150220 CC 
 0.885070-01 
 0.234650 00 
 0.206260 CC 
 0.124CCO 00 
 C. 106740 00 
 0.225680 OC 
 0.206C6C 00 
 0.131260 00 
 0. 93962D-01 
 0.243020 OC 
 C. 163910 CO 
 0. 1^ Q 11D 00 
 0. 20*020 OC 
 0.157760 CC 
 0.256930 00 
 0. 600620-01 
 0.14939D 00 
 
 K= 0.0 
 (Nl 
 
 0.50CJC0 00 
 0.500)00 00 
 0.50OC0 00 
 0.5000CO 00 
 C. 50C3C0 00 
 0.500000 00 
 C.25OC0 OC 
 0.500)CO 00 
 0.500JCO 00 
 0.500)00 00 
 0.50 00 CO 
 C.50CCC0 00 
 0.250000 OC 
 0.50CJCO 00 
 0.5C0)00 00 
 0.100)00 01 
 0.5000CD 00 
 0.5CO00 00 
 0.500) CO 00 
 0.500000 00 
 0.50CCC0 00 
 0.500100 00 
 0. 2500CO OC 
 0.500X0 00 
 0.250J0O OC 
 0.500)C0 00 
 0.5003CO 00 
 C.5000CO OC 
 0.500000 00 
 C.50C0CO 00 
 0.250000 OC 
 C.50CJC0 00 
 O.2500CO OC 
 0.500JOO 00 
 0.500)CO 00 
 0. 5001)00 00 
 0.2501CO OC 
 0.50000D 00 
 0.50CCCO 00 
 0.50CJC0 00 
 C. 250JC0 OC 
 0.500X0 00 
 0.500X0 00 
 C.50CXD 00 
 C. 500300 00 
 C.5000CO OC 
 0. 500000 00 
 C.5000CO 00 
 0.250000 OC 
 
 
 ..**•».*.». 
 
 ROOT 
 0.20000000000000000 Oi 
 0.40000000000000000 00 
 O.iilillliiillllilD 01 
 0.62063965517241380 00 
 0.89230769230769230 00 
 0.71823204-19389500 00 
 0. 847360912981H550D 00 
 C. 76035365286179620 00 
 0.8096103371693923O 00 
 0.77836002657022660 00 
 0.796918557597194*0 00 
 C. 78543120^81514900 00 
 0.79403033702055320 00 
 0.783337*8380179750 00 
 0.7916306227^363980 00 
 C.7°01144423230H12D 00 
 C. 79090140530203840 OC 
 0.79038359737031420 00 
 C. 7906827428*602*20 00 
 0.790494839452466-0 00 
 C.7906072027206736D 00 
 0.7^053792248633200 00 
 C. 79059016971308910 00 
 0.790555532eC297C60 00 
 0.79053079941Q76470 00 
 0.79056351737112330 00 
 0.7905731666630916D 00 
 C.79C56700536508680 CO 
 0.79057064750263450 00 
 C. 79056838733195130 CO 
 0.79057003743160H30 00 
 0.7905639'57375o0230 00 
 C.79G569780551403 C »D CC 
 0.7905692168AR24460 00 
 0.790569 C 3121757720 OC 
 C.79G56933036<}*6i3D 00 
 C. 79056947957C56660 00 
 0.79056937917333720 00 
 0.79056943c073536^0 00 
 C.79C5693Q999639C40 00 
 0.79056942639125670 00 
 C. 79056940335221350 00 
 0.7905694191060335D 00 
 C. 79056941261331550 00 
 C. 79056941647444200 00 
 C. 79056941^-08631 C3D 00 
 0.79056941552 C 0124D 00 
 0.7^056941464472970 00 
 C. 790569^1531315040 00 
 
 ERROR 
 0.12094C 01 
 
 -0.390570 00 
 
 0.320540 00 
 -0.16 C 83D 00 
 
 0.1 01 74 C 00 
 -0. 723370-01 
 
 0.56791C-01 
 -0.30216C-01 
 
 0.19041D-01 
 -0.1 22090-01 
 
 0.634910-02 
 -O.51332C-02 
 
 C. 351150-02 
 -0.223190-0; 
 
 0. 106120-02 
 -0.45497D-0" 
 
 0.33199D-0 
 
 -0. 18582C-0 
 O.11333C-0 1 
 -0.7457oD-0 
 0.37738C-0 
 -0.314930-1 
 0.207550-0 
 -0. 13382C-0 
 0.113340-0 
 -0.58972C-C 
 0.375160-0 
 -C.24097C-0 
 0.123250-0 
 -0.10277C-0 
 0.67239C-C 
 -0.45767C-t 
 0.36551D-( 
 -0.19319C-C 
 0.116180-C 
 -0.846730-C 
 0.64523C-C 
 -0.35869C-0 
 O.21O3 6C-0 
 -0. 15046C-0 
 0.U849C-0 
 -C.61399C-C 
 0.4C640D-C 
 -0.24288C-C 
 0.143230-C 
 -0.95573C-C 
 0.4P6920-C 
 -0.3 C 737D-C 
 0.27106C-C 
 
61 
 
 2 
 3 
 
 4 
 5 
 
 _ 6 
 
 ~ 7 
 
 e 
 
 9 
 10 
 
 li 
 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 3* 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 4-5 
 
 ;k= 
 
 o. 
 o. 
 o. 
 o. 
 o. 
 o. 
 o. 
 o. 
 o. 
 o. 
 o. 
 o. 
 o. 
 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0, 
 0. 
 0, 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 0. 
 
 0.12500000 
 CIK-NI 
 
 106250 
 123440 
 103520 
 131150 
 104400 
 11 96 PC 
 11206n 
 113920 
 117340 
 107780 
 1258FD 
 Q472 7D 
 146720 
 869760 
 158620 
 818740 
 137050 
 9943C0 
 128900 
 1002 10 
 1353CO 
 101080 
 125190 
 105170 
 1261 10 
 990040 
 13905D 
 962i Q D 
 137950 
 1001P0 
 1 2 .? 2 3 n 
 110380 
 115000 
 1164 60 
 
 103550 
 
 124830 
 960<t0n 
 14460H 
 891470 
 1541 on 
 1=5 f 670 
 158540 
 645C C 
 1599 50 
 8^3720 
 159130 
 853350 
 155650 
 880710 
 
 01 
 
 01 
 01 
 01 
 01 
 01 
 01 
 01 
 01 
 01 
 01 
 
 oc 
 
 01 
 00 
 01 
 00 
 01 
 00 
 01 
 01 
 01 
 01 
 01 
 01 
 01 
 00 
 01 
 00 
 01 
 01 
 01 
 01 
 01 
 01 
 01 
 01 
 00 
 01 
 00 
 01 
 00 
 01 
 OG 
 01 
 OG 
 01 
 00 
 01 
 00 
 
 1 »*»K»»*». 
 
 000000000 
 B(K-N) 
 O.o25000 
 0. 656250 
 C. 710940 
 0. 55c64P 
 0.521240 
 0. 750760 
 0. 5 Q 762D 
 0.712670 
 0. 606950 
 0.729770 
 0. 55M^O 
 0.820240 
 ().<.032 C P 
 0. 713^10 
 0.471480 
 0. 67*560 
 0.89 3180 
 0. 542CEO 
 0.7O5C7O 
 0.689450 
 0.56 1600 
 0. 52 6f40 
 0. 728780 
 0,647160 
 0. 626670 
 0. 75 190D 
 0. 4931 2D 
 0.604510 
 0. 62 6 5PD 
 0.46*290 
 0.78 2590 
 0. 57 85 70 
 0, 723310 
 0. 601670 
 0. 730*20 
 0,562120 
 „ 8 1 2 3 CD 
 0.417900 
 0.693MP 
 0.502120 
 0. h3 312D 
 0.54 60 ID 
 0. 600350 
 0,57 22 00 
 0, 5776fcl) 
 0.594 170 
 0.55 3640 
 0, 62 32*0 
 0.515830 
 
 01*»B 
 
 00 
 00 
 00 
 
 00 
 00 
 00 
 
 oc 
 
 00 
 00 
 00 
 00 
 00 
 
 cc 
 
 OG 
 00 
 CO 
 00 
 00 
 
 oc 
 
 00 
 OG 
 00 
 00 
 00 
 CO 
 00 
 
 oc 
 
 00 
 00 
 OQ 
 00 
 00 
 CO 
 00 
 OG 
 GC 
 00 
 00 
 
 oc 
 
 00 
 00 
 00 
 
 oc 
 
 
 
 cc 
 oc 
 
 
 OG 
 00 
 
 » 4 
 
 K= 
 0. 
 
 c. 
 
 0. 
 0. 
 
 c. 
 
 0. 
 
 c. 
 
 0. 
 0. 
 
 0. 
 0, 
 
 c. 
 
 0. 
 0. 
 0. 
 
 c. 
 
 0. 
 0. 
 0. 
 0. 
 
 c. 
 
 0. 
 0. 
 0. 
 
 c. 
 
 0. 
 0. 
 
 c. 
 
 0. 
 0. 
 0. 
 0. 
 0. 
 G. 
 
 c. 
 c. 
 c. 
 
 0. 
 
 c. 
 
 0. 
 
 c. 
 
 0. 
 0. 
 
 c. 
 c. 
 
 0. 
 0. 
 
 c. 
 
 0. 
 
 0.750000 
 
 5000CO 
 500000 
 500GC0 
 500000 
 25C0CO 
 5C0J00 
 5003CD 
 5000CO 
 50 0') CO 
 500JC0 
 5000C0 
 50OC0 
 500000 
 25 C J CO 
 5000C0 
 250 JGO 
 100000 
 500 )00 
 500JCO 
 500000 
 500GCO 
 250000 
 5O00C0 
 50C0C0 
 5000CO 
 50CGCD 
 500000 
 25C3C0 
 500)00 
 2 5 00 CO 
 500JG0 
 500JC0 
 500JG0 
 5000C0 
 5OC0CO 
 5OO.)0D 
 5CCGC0 
 500JOO 
 250 300 
 50 J CO 
 25G3CD 
 500JC0 
 25 0000 
 500 J Cn 
 250J0D 
 5 C C CO 
 2500CD 
 500 OCO 
 250000 
 
 00 
 00 
 00 
 
 00 
 00 
 00 
 OC 
 00 
 00 
 00 
 00 
 
 oc 
 
 00 
 
 oc 
 
 00 
 00 
 01 
 00 
 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 00 
 
 
 oc 
 
 
 
 oc 
 
 00 
 00 
 00 
 00 
 
 oc 
 
 00 
 00 
 00 
 00 
 00 
 
 oc 
 
 
 00 
 00 
 00 
 
 
 oc 
 
 00 
 
 oc 
 
 00 00*** ******■*» 
 ROOT 
 
 0.2O0OOC0OCO0C0O0OD 
 0.40000000000000000 
 0. 11111111111111110 
 C.6206896551724138D 
 C.970297C297G297C3D 
 0.72672672672672670 
 C. 8602442333755617O 
 0.77428709521507970 
 0.82479569463823000 
 0.79334988339727670 
 0.81226581936^92290 
 C. 30C64252943963570 
 0.807693531596A851D 
 0. 802342tt0195h93900 
 0.80596679101531 140 
 0.8032872667310934O 
 0.80462187121412680 
 0. 80396637455^25040 
 0. 80440591933o 7 9690 
 0. 80415601408968180 
 0. 8043142372 74C333D 
 0. 30419622391482C80 
 0. 80427532837630420 
 0. 80423033836409590 
 0.80425831847929690 
 0. 60424187871664920 
 0.8042523549673442D 
 0. 80424446386940820 
 C.8042497016995117D 
 0. 80424588337996190 
 0.rt0424ri4°c45592410 
 0.8042470332844190D 
 0.80424796963797510 
 0.8042474191 9325R80 
 C. 8042477608075778D 
 0.30424755436244540 
 0. 30424768126511110 
 0.30424760454017390 
 0. 804247662 74 73913D 
 0.304247624^005e530 
 0. 604247 652<t 6*6 3 480 
 0.80424763332432370 
 0. 3 042 47 64 706^20 500 
 0. 30424763 754223120 
 0.30424764^3C q 894 7D 
 0. 30424763958^51440 
 C. 30424764292-50900 
 0.80424764058269190 
 0. 8042476^223422210 
 
 ERROR 
 
 01 0.119580 01 
 
 00 -0.40425D 00 
 
 01 0.3 06 86 00 
 00 -0.1835oD 00 
 00 0.166050 00 
 00 -0.775210-01 
 00 0.559970-01 
 00 -0.299610-01 
 00 0.205480-01 
 00 -0.1089SD-01 
 00 0. 801320-02 
 00 -0.36051C-02 
 00 0. 344590-02 
 00 -0.19048C-02 
 00 0.161910-02 
 00 -0.96037C-03 
 00 0.374230-03 
 00 -0.281270-03 
 00 0.158280-03 
 00 -0.916270-04 
 00 0.665960-04 
 00 -0.514180-04 
 00 0.27687C-04 
 00 -0.173030-04 
 00 0.1U77C-04 
 00 -0.576280-05 
 00 0.471350-05 
 00 -0.31776C-05 
 00 0.206020-05 
 00 -0. 175810-05 
 00 0.854950-06 
 00 -0.603220-06 
 CO 0.328130-06 
 00 -0. 222320-06 
 00 0.11930C-06 
 00 -0.866250-07 
 00 0.39758C-07 
 00 -0.369670-07 
 00 0.21240C-07 
 00 -0.17106C-07 
 00 0.109590-07 
 OC -0.818280-08 
 00 0.555710-03 
 00 -0.39648r-03 
 00 0.230180-03 
 OC -0. 192360-03 
 00 0.141740-C8 
 00 -0.924380-09 
 00 0. 727150-09 
 
62 
 
 ♦*»*CK 
 
 0.212500000UOOOOOOO 
 
 01* 
 
 T RK= 0.15000J0D 01 i » , »» ,, » : "»» 
 
 STEP 
 
 CU-N) 
 
 
 H( K-N) 
 
 
 (N) 
 
 
 RCOT 
 
 
 ERROR 
 
 1 
 
 0.121880 
 
 01 
 
 0. 10625P 
 
 01 
 
 0.5001CO 
 
 00 
 
 0.2 0000000 COCOOOOOD 
 
 01 
 
 0.111060 0) 
 
 2 
 
 0.2132 80 
 
 01 
 
 0. 1046=0 
 
 01 
 
 0. 5O03CO 
 
 00 
 
 0.4 000000000 0000 JO 
 
 00 
 
 -0.489360 OC 
 
 3 
 
 0.123390 
 
 01 
 
 G.9R633D 
 
 OC 
 
 C. 25CCC0 
 
 OC 
 
 C. 13846153846153840 
 
 01 
 
 0.49526C OC 
 
 4 
 
 0.2C607P 
 
 01 
 
 0. 113C60 
 
 01 
 
 0.5OOJ0O 
 
 00 
 
 0. 6-4 150943396226410 
 
 OC 
 
 -0.247850 Of 
 
 5 
 
 0. 12°540 
 
 01 
 
 0. 88455P 
 
 CO 
 
 0. 250JCO 
 
 00 
 
 0. 1133757^61 733^390 
 
 01 
 
 0.24440C 0( 
 
 6 
 
 0.167140 
 
 01 
 
 0. 126 310 
 
 01 
 
 0.5 00 00 
 
 00 
 
 0.77452667814113600 
 
 00 
 
 -0. 114830 0( 
 
 7 
 
 0. 134070 
 
 01 
 
 0. 1172 50 
 
 01 
 
 0.50CK0 
 
 00 
 
 0.96112^39660376 7t>0 
 
 00 
 
 0.71765T-0! 
 
 . 8 
 
 0.195870 
 
 01 
 
 0.997 4 20 
 
 00 
 
 C.500JC0 
 
 00 
 
 0. 8383809793376734D 
 
 CO 
 
 -0.50979C-0! 
 
 9 
 
 0. 134220 
 
 01 
 
 0. 991860 
 
 00 
 
 C.25000D 
 
 00 
 
 0.92326474062354980 
 
 00 
 
 0.389250-0' 
 
 10 
 
 0.1955CD 
 
 01 
 
 0. 11792P 
 
 01 
 
 O.5OOJ0O 
 
 00 
 
 C. 8670090^112^31270 
 
 CO 
 
 -O.22351C-0I 
 
 11 
 
 0. 130520 
 
 01 
 
 0. 125.330 
 
 01 
 
 0.500000 
 
 00 
 
 0.901335256498o3720 
 
 00 
 
 0.1197e>D-0! 
 
 12 
 
 0.204200 
 
 01 
 
 0. 899^00 
 
 00 
 
 C. 50C3CO 
 
 00 
 
 0.87944953007-1 8370 
 
 00 
 
 -0.99101C-0; 
 
 13 
 
 0. 125220 
 
 01 
 
 0. 11112P 
 
 01 
 
 C.25O0CO 
 
 00 
 
 0.89572262357945470 
 
 00 
 
 0.636300-0; 
 
 14 
 
 0.209020 
 
 01 
 
 0. 101490 
 
 01 
 
 0. 5000CD 
 
 OC 
 
 0. 3H4782 17402497640 
 
 00 
 
 -O.45775C-0, 
 
 15 
 
 0.12 54 00 
 
 01 
 
 0. 100770 
 
 01 
 
 0.2 50 3C0 
 
 OC 
 
 0. 99270170135193210 
 
 00 
 
 0.334210-Oi 
 
 16 
 
 0.203440 
 
 01 
 
 0. 111930 
 
 01 
 
 0.5000CO 
 
 00 
 
 0.88725009060400790 
 
 00 
 
 -0. 210950-0; 
 
 17 
 
 0.131150 
 
 01 
 
 0.899250 
 
 00 
 
 0.250000 
 
 OC 
 
 0.89114097406787740 
 
 00 
 
 0. 178130-0: 
 
 _ 18 
 
 0. 184570 
 
 01 
 
 0. 12o65D 
 
 01 
 
 0.500300 
 
 00 
 
 0.83843262250900590 
 
 00 
 
 -O.92701O-0 
 
 19 
 
 0.136660 
 
 01 
 
 0. 11 5630 
 
 01 
 
 C. 50CJC0 
 
 OC 
 
 C. 889=1862552'">84C4D 
 
 00 
 
 0.5 5 393 C-O'd 
 
 20 
 
 0. lSlO^D 
 
 01 
 
 0.102700 
 
 01 
 
 0.500300 
 
 00 
 
 0.88896233470931390 
 
 CO 
 
 -0.397300-0 
 
 21 
 
 0.138570 
 
 01 
 
 0.950640 
 
 OC 
 
 0.25C3CO 
 
 OC 
 
 C. 38967035065635840 
 
 00 
 
 0.31072C-0: 
 
 22 
 
 0.176460 
 
 01 
 
 0. 124220 
 
 01 
 
 0.500JCD 
 
 00 
 
 0.88919243547262530 
 
 00 
 
 -C.1672CD-0 
 
 23 
 
 0. 1436BD 
 
 01 
 
 0. 114010 
 
 01 
 
 C. 5000C0 
 
 00 
 
 0.88946255919030610 
 
 00 
 
 O.102 93C-0 
 
 24 
 
 0.179550 
 
 01 
 
 0. 107030 
 
 01 
 
 0.500JCO 
 
 
 
 C. 89929105138824720 
 
 CC 
 
 -G.685SOC-0' 
 
 25 
 
 0. 131620 
 
 01 
 
 C. 13 1S5D 
 
 01 
 
 0. 5003CO 
 
 00 
 
 0. 38939234928234540 
 
 00 
 
 0.3 32 180-0' 
 
 26 
 
 0.203600 
 
 01 
 
 0. 83B590 
 
 OC 
 
 0.5O0J0D 
 
 
 
 0.88932931952931230 
 
 00 
 
 -G.29312C-0' 
 
 27 
 
 0. 123320 
 
 01 
 
 0. 117C40 
 
 01 
 
 0.250000 
 
 00 
 
 0.88937727359430410 
 
 00 
 
 0.1764 30-0'; 
 
 28 
 
 0.214810 
 
 01 
 
 C.94 619D 
 
 00 
 
 0. 5C03CO 
 
 OC 
 
 C. 99934576012643370 
 
 00 
 
 -O.13871C-0' 
 
 29 
 
 0. 119700 
 
 01 
 
 0.109CR0 
 
 01 
 
 0.250000 
 
 
 
 0.88936872717715310 
 
 CC 
 
 C. 909610-0' 
 
 .30 
 
 0.218970 
 
 01 
 
 0. 100770 
 
 01 
 
 0.5000CO 
 
 00 
 
 0.3993530061876320D 
 
 00 
 
 -0.66249C-0 
 
 31 
 
 0.118900 
 
 01 
 
 0. 103=70 
 
 01 
 
 0.250OCO 
 
 OC 
 
 C. 33936426603734770 
 
 CO 
 
 0.46350D-0 1 
 
 32 
 
 0.219210 
 
 01 
 
 0. 10549D 
 
 01 
 
 0.5OO3CO 
 
 00 
 
 0.8893564494011H950 
 
 00 
 
 -O.31917C-0 
 
 33 
 
 0. 12 05 00 
 
 01 
 
 0.9Q0740 
 
 00 
 
 0.2503CO 
 
 OC 
 
 0. 39936199795635C60 
 
 CO 
 
 0.236690-01 
 
 34 
 
 0.212160 
 
 01 
 
 0. 1111 80 
 
 01 
 
 0.5000 CO 
 
 00 
 
 0.3393531200056426D 
 
 00 
 
 -0.151110-0 
 
 35 
 
 0.125330 
 
 01 
 
 C. 91 86 20 
 
 00 
 
 C.25C0CO 
 
 OC 
 
 0. 3893603602=554440 
 
 00 
 
 0.12292O0 
 
 36 
 
 0. 19769D 
 
 01 
 
 0. 120810 
 
 01 
 
 0.500.)00 
 
 00 
 
 0. 3893589337524639D 
 
 00 
 
 -0. 692320-0 
 
 37 
 
 0. 135BPO 
 
 01 
 
 0. 7=3 6170 
 
 cc 
 
 C.2500CO 
 
 OC 
 
 0. 88936029351026930 
 
 
 
 0.66243C-0 
 
 38 
 
 0.167330 
 
 01 
 
 0. 139320 
 
 01 
 
 C.50C00P 
 
 00 
 
 0.38935934198913^00 
 
 00 
 
 -0.25 = 090-0 
 
 39 
 
 0.15°370 
 
 01 
 
 0. 9434<-0 
 
 00 
 
 0. 5000C0 
 
 00 
 
 0. 88=3598591^064-40 
 
 00 
 
 0.223070-0 
 
 40 
 
 0.147090 
 
 01 
 
 0. 134840 
 
 01 
 
 0.5000CO 
 
 00 
 
 0. 38935952498677580 
 
 CO 
 
 -0. 10609D-C 
 
 41 
 
 0. 1RU40 
 
 01 
 
 0. 8P7C10 
 
 00 
 
 0.5003CD 
 
 00 
 
 0.88 = 35=720799l5nO 
 
 00 
 
 0.89724T-0 
 
 42 
 
 0. 1426CP 
 
 01 
 
 0. 106660 
 
 01 
 
 0.250)00 
 
 OC 
 
 0. 3893595703973533D 
 
 CO 
 
 -0.60673C-0 
 
 43 
 
 0. 17745D 
 
 01 
 
 0. 114640 
 
 01 
 
 0.500000 
 
 OJ 
 
 0. 839359h631239ri040 
 
 00 
 
 0.370430-0 
 
 44 
 
 0. 137H7D 
 
 01 
 
 0. 124C90 
 
 01 
 
 C. 50COCO 
 
 OC 
 
 C. 38935=61110120270 
 
 00 
 
 -0.19=740-0 
 
 45 
 
 0. 1°207D 
 
 01 
 
 C.94o^«D 
 
 00 
 
 0.500 )0D 
 
 00 
 
 0.98935964o7353234D 
 
 CO 
 
 0.156600-0 
 
 46 
 
 0.1357 c O 
 
 01 
 
 0.103170 
 
 01 
 
 C. 2 5 00 CO 
 
 OC 
 
 C. 38 = 35962000813-80 
 
 00 
 
 -0.1 10670-0 
 
 47 
 
 0.1°6290 
 
 01 
 
 0. 11473D 
 
 01 
 
 0.5000CO 
 
 00 
 
 0.38935=63732519490 
 
 CO 
 
 0.O74970-0 
 
 . .48 
 
 0. 12995D 
 
 01 
 
 0. 128420 
 
 01 
 
 0.5003CO 
 
 00 
 
 0.8893596 2764349 59 
 
 00 
 
 -0.343200-0 
 
 49 
 
 0.207470 
 
 01 
 
 0.86055D 
 
 00 
 
 0.500300 
 
 00 
 
 0.88935963407388C7D 
 
 00 
 
 0.299840-0 
 
 
IBLIOGRAPHIC DATA 
 HEET 
 
 1. Report No. 
 
 UIUCDCS-R-72-525 
 
 3. Recipient's Accession No. 
 
 5. Report Date 
 
 June, 1972 
 
 Title and Subtitle 
 
 An Algorithm for the Solution of a Quadratic 
 Equation using Continued Fractions 
 
 6. 
 
 Date of appr oval 
 
 Author(s) 
 
 Kishor Shridharbhai Tivedi 
 
 8. Performing Organization Rept. 
 No. 
 
 Performing Organization Name and Address 
 
 Department of Computer Science 
 University of Illinois 
 Urbana, Illinois 6l801 
 
 10. Project/Task/Work Unit No. 
 
 11. Contract /Grant No. 
 
 NSF GJ-813 
 
 2. Sponsoring Organization Name and Address 
 
 National Science Foundation 
 Washington, D. C. 
 
 13. Type of Report & Period 
 Covered 
 
 Research 
 
 14. 
 
 5. Supplementary Notes 
 
 6. Abstracts 
 
 This is an effort to investigate representations of numbers 
 other than positional notation for computer arithmetic. Using continued 
 fraction representation of numbers, an algorithm to solve a limited class 
 of quadratics has been developed. This algorithm is suitable for hardware 
 implementation and is reasonably efficient. Feasibility of constructing 
 an arithmetic unit with continued fraction representation depends on 
 discovery of many more such useful algorithms which can share the same 
 hardware. 
 
 7. Key Words and Document Analysis. 17o. Descriptors 
 
 Continued fraction, 
 Computer arithmetic, 
 Quadratic equation, 
 Square root algorithm, 
 Floating point, 
 
 7b. Identifiers/Open-Ended Terms 
 
 7c. COSATI Field/Group 
 
 8. Availability Statement 
 
 Unlimited Release 
 
 19. Security Class (This 
 Report) 
 
 UNCLASSIFIED 
 
 20. Security Class (This 
 Page 
 
 UNCLASSIFIED 
 
 21. No. of Pages 
 62 
 
 22. Price 
 
 ORM NTIS-3S ( 10-70) 
 
 USCOMM-DC 40329-P71 
 
' 
 
 
.OUNO, 
 

 
 mm 
 
 ■ , t^ossaoo^ 
 
 
 - , < 
 
 m 
 
 
 w 
 
 RK 
 
 
 
 IT 
 
 . * 
 
 ■ 
 
 ■ 
 
 I 
 
 HI 
 
 ■v-W: 
 
 ■ 
 
 ■