170 Chapter 5.Evaluation of Functions a general rule.Blanch [1]gives a good review of the most useful convergence tests for continued fractions. There are standard techniques,including the important quotient-difference algo- rithm,for going back and forth between continued fraction approximations,power series approximations,and rational function approximations.Consult Acton [2]for an introduction to this subject,and Fike [3]for further details and references. How do you tell how far to go when evaluating a continued fraction?Unlike a series,you can't just evaluate equation(5.2.1)from left to right,stopping when the change is small.Written in the form of(5.2.1),the only way to evaluate the continued fraction is from right to left,first (blindly!)guessing how far out to start.This is not the right way. The right way is to use a result that relates continued fractions to rational 菲 approximations,and that gives a means of evaluating(5.2.1)or(5.2.2)from left 超日支 to right.Let fn denote the result of evaluating (5.2.2)with coefficients through ICAL an and bn.Then fnBn An (5.2.4) RECIPES 9 where A,and B,are given by the following recurrence: A-1=1B-1≡0 A0≡b0B0≡1 Aj=bjAj-1+ajAj-2 Bj=bj Bj-1+ajBj-2 j=1,2,,n s9&公 (5.2.5) This method was invented by J.Wallis in 1655(!),and is discussed in his Arithmetica Infinitorum [41.You can easily prove it by induction. In practice,this algorithm has some unattractive features:The recurrence(5.2.5) frequently generates very large or very small values for the partial numerators and denominators A;and B;.There is thus the danger of overflow or underflow of the floating-point representation.However,the recurrence(5.2.5)is linear in the A's and 多名a Numerica 10621 B's.At any point you can rescale the currently saved two levels of the recurrence, e.g.,divide Aj,Bj,Aj-1,and Bj-1 all by Bj.This incidentally makes Aj=fj and is convenient for testing whether you have gone far enough:See if fi and fj-1 from the last iteration are as close as you would like them to be.(If B;happens to %9N be zero,which can happen,just skip the renormalization for this cycle.A fancier level of optimization is to renormalize only when an overflow is imminent,saving the unnecessary divides.All this complicates the program logic.) Two newer algorithms have been proposed for evaluating continued fractions. Steed's method does not use Ai and Bj explicitly,but only the ratio Dj=Bj-1/Bj One calculates Dj and Afi=fi-fj-1 recursively using D1=1/(b+aD5-1) (5.2.6) △f1=(b5D3-1)△f5-1 (5.2.7) Steed's method(see,e.g.,[51)avoids the need for rescaling of intermediate results. However,for certain continued fractions you can occasionally run into a situation170 Chapter 5. Evaluation of Functions Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). a general rule. Blanch [1] gives a good review of the most useful convergence tests for continued fractions. There are standard techniques, including the important quotient-difference algo￾rithm, for going back and forth between continued fraction approximations, power series approximations, and rational function approximations. Consult Acton [2] for an introduction to this subject, and Fike [3] for further details and references. How do you tell how far to go when evaluating a continued fraction? Unlike a series, you can’t just evaluate equation (5.2.1) from left to right, stopping when the change is small. Written in the form of (5.2.1), the only way to evaluate the continued fraction is from right to left, first (blindly!) guessing how far out to start. This is not the right way. The right way is to use a result that relates continued fractions to rational approximations, and that gives a means of evaluating (5.2.1) or (5.2.2) from left to right. Let fn denote the result of evaluating (5.2.2) with coefficients through an and bn. Then fn = An Bn (5.2.4) where An and Bn are given by the following recurrence: A−1 ≡ 1 B−1 ≡ 0 A0 ≡ b0 B0 ≡ 1 Aj = bjAj−1 + ajAj−2 Bj = bjBj−1 + ajBj−2 j = 1, 2,...,n (5.2.5) This method was invented by J. Wallis in 1655 (!), and is discussed in his Arithmetica Infinitorum [4]. You can easily prove it by induction. In practice, this algorithm has some unattractive features: The recurrence (5.2.5) frequently generates very large or very small values for the partial numerators and denominators Aj and Bj . There is thus the danger of overflow or underflow of the floating-point representation. However, the recurrence (5.2.5) is linear in the A’s and B’s. At any point you can rescale the currently saved two levels of the recurrence, e.g., divide Aj , Bj , Aj−1, and Bj−1 all by Bj . This incidentally makes Aj = fj and is convenient for testing whether you have gone far enough: See if f j and fj−1 from the last iteration are as close as you would like them to be. (If Bj happens to be zero, which can happen, just skip the renormalization for this cycle. A fancier level of optimization is to renormalize only when an overflow is imminent, saving the unnecessary divides. All this complicates the program logic.) Two newer algorithms have been proposed for evaluating continued fractions. Steed’s method does not use Aj and Bj explicitly, but only the ratio Dj = Bj−1/Bj . One calculates Dj and ∆fj = fj − fj−1 recursively using Dj = 1/(bj + ajDj−1) (5.2.6) ∆fj = (bjDj − 1)∆fj−1 (5.2.7) Steed’s method (see, e.g., [5]) avoids the need for rescaling of intermediate results. However, for certain continued fractions you can occasionally run into a situation