Next | Continued Fraction Arithmetic | 26 |

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 |