### Nearest integer Euclidean algorithm

If r is a real number, by [r] we mean the *nearest integer to r*. Thus
|r - [r]| ≤ 1/2 and if r = t + 1/2, where t is an integer, then [r] = t + 1.

Alternatively, [r] = r + 1/2 , the integer part of r + 1/2,

Hence [r] = r + θ, where -1/2 < θ &le 1/2.
Then if m and n are integers, n > 0 and q = [m/n], we have m/n = q + θ, where -1/2 < θ ≤ 1/2.

Hence m = nq + nθ, where -n/2 < nθ ≤ n/2.

Hence m = nq + es, where -n/2 < es ≤ n/2 and s is an integer, 0 ≤ s ≤ n/2 and e = 1 if θ ≥ 0, while e = -1 if θ < 0.

We write e = e(m,n).

Then with r_{0} = m and r_{1} = n > 0, we define r_{k} recursively for 2 ≤ k ≤ l+1, r_{k} > 0 and e_{k+1} = e(r_{k-1},r_{k}), where q_{k} = [r_{k-1} / r_{k}] for 1 ≤ k ≤ l:

r_{0} | = | r_{1}q_{1} + e_{2}r_{2} | (-r_{1} / 2 < e_{2} r_{2} ≤ r_{1} / 2) |

r_{1} | = | r_{2}q_{2} + e_{3}r_{3} | (-r_{2} / 2 < e_{3} r_{3} ≤ r_{ 2 }/2) |

| ··· | | |

r_{k-1} | = | r_{k}q_{k} + e_{k+1}r_{k+1} | (-r_{k} / 2 < e_{k+1} r_{k+1} ≤ r_{k} / 2) |

| ··· | | |

r_{l-1} | = | r_{l}q_{l} | |

Then r_{l} = gcd(m,n).
The s_{k} and t_{k} are also printed in tabular form, where it is convenient to define e_{0} = 1 = e_{1} and where

s_{0} = 1, | s_{1} = 0, | e_{k}s_{k} = s_{k-2} – q_{k-1}s_{k-1}, | |

t_{0} = 0, | t_{1} = 1, | e_{k}t_{k} = t_{k-2} – q_{k-1}t_{k-1}, | k = 2,..., l+1. |

Then r_{k} = s_{k}m + t_{k}n for 0 ≤ k ≤ l+1, where r_{l+1} = 0. The number of steps is no greater than the number in Euclid's algorithm.
(Based on Exercise 5, page 67, *Elementary Number theory and its applications*, by Ken Rosen.

Also see Chapter 39 (Kettenbrüche nach nächsten Ganzen), page 168, *Kettenbrüche*, by Oscar Perron, Chelsea 1950.

We print the nearest integer continued fraction expansion m/n = q_{1}+e_{2}/q_{2}+ ⋯ +e_{l}/q_{l}.

*Last modified 26th January 2009*

Return to main page