Continued fraction objects

• Suppose we create a continued fraction object x to represent the rational number n/d

  • Internally, the object is simply a record that stores the values of n and d:

        struct st_cf_rat {
          int n, d;
        };

• If we ask it to produce its next term, what does it do?

• First it figures out the next term---that's

• Then, since x = p + 1/x', it wants to turn itself into x'

  • That way, next time we ask it for a term, it'll behave like x'

• Since we have x = n / d = p + 1/(n'/d'), we can solve for n' and d'

  • We get n' = d and d' = n - pd

        int next_term_from_rat(struct st_cf_rat *cf) 
        {
          int n = cf->n, d = cf->d;
          int p = n / d;             /* Integer division */

          cf->n = d;
          cf->d = n - p*d;

          return p;
        }

• For example, if x was 8/3 = [2; 1, 2], it emits 2 and becomes 3/(8-2·3) = 3/2 = [1; 2]

• Next time we ask for a term, it is 3/2 and emits 1 and beomes 2/(3-1·2) = 2/1 = [2]