Date: Thu, 7 Mar 1996 02:59:19 -0500 (EST) From: [Permission pending] To: Dave Rusin Subject: Re: Q: "Skipping" continued fraction convergents? On Wed, 6 Mar 1996, Dave Rusin wrote: > Of course for certain continued fractions there is a pattern to > the convergents (p_n/q_n); for example in 1/1+1/1+1/1+ ..., the convergents > are of the form p_n= a r^n + b/r^n for some easy constants a and b, > where r is the golden ratio; in particular, p_n is the nearest integer > to [a r^n ]. > > dave > > (If you do hear of something speedier I'd like to hear about it.) > The reason I was curious is that I just found out that you can calculate the nth Chebyshev polynomial w/o going through all of th preceding ones (should have saved the message...something like T(m+n)(x) = T(m)(x) T(n)(x) - T(|m-n|)(x), but don't quote me), and since they satisfy 2-term recurrence relations the same as continued fractions do, perhaps the technique carries over. Thanks for the input. [Permission pending] ============================================================================== (The TChebyschev polynomials satisfy T_(n+1)(x) = 2x T_n(x) - T_(n-1)(x), which is to say they satisfy a linear recurrence relation whose coefficients are _constants_, that is, _independent of n_. In this way they are more similar to the Fibonnacci numbers, and yes indeed they can be easily calculated for large n. Note we need only apply high powers of the matrix [ 2x -1 ] [ 1 0 ] to the column matrix [T_1, T_0]. High powers of a matrix can be computed in logarithmic time by repeated squarings.) -- djr ==============================================================================