Next Continued Fraction Arithmetic 26

# 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]

 Next Back