The fast continued fraction algorithm is a modified version of the zeroed Farey

process in which some information calculated as part of the latter is discarded in

exchange for asymptotic speed. In particular, note that for a given x (generally

irrational), the zeroed Farey algorithm performs a "zeroing in" process by way of

creating a series of shrinking Farey intervals containing x, each of whose

endpoints are recorded as best left and right rational approximations to x. The fast

continued fraction algorithm gains computational speed by recording only the last

such "zeroing in" when successive shrinkings occur on one side of x or the other.

To be more precise: Start with an irrational number x in some Farey interval

[a/b, c/d]. In the zeroed Farey process, it may happen that a succession

01/b1, 02/b2, ..., Qx/bx of iterations occur to zero in on x from (without loss of

generality) the left; in the slow algorithm, all 2 k of these integers would be

recorded whereas in th fast algorithm, computational methods are applied to

determine only the kth values ax, by so as to eliminate computational overhead. As

part of the fast algorithm, a "stopping index" s is computed and maintained to

provide a guaranteed stopping point to the otherwise-infinite algorithm.

Here are the tools needed to implement the fast algorithm. Again, x is assumed

throughout to be an irrational number lying in the Farey interval [a/b, c/dJ.

(i) For each k, ax+1 /bx+1 is the mediant of the in