Nearest Gaussian Integer Algorithm

The nearest Gaussian integer algorithm, also called the Hurwitz complex continued fraction algorithm, constructs a complex continued fraction by choosing the closest Gaussian integer at each step (Hurwitz 1887). For a complex number , set , and let denote a nearest Gaussian integer to , with a fixed rule used to break ties on the boundaries of the fundamental squares. Define and whenever . The resulting expansion is

The partial quotients are Gaussian integers, and the convergents are Gaussian rational approximations to , where a Gaussian rational is a ratio of Gaussian integers. The algorithm terminates for a Gaussian rational and otherwise gives an infinite expansion. It is the complex analogue of the nearest integer continued fraction algorithm and is simpler arithmetically than the Schmidt algorithm.