   ISSN 1088-6842(online) ISSN 0025-5718(print)

An analogue of the nearest integer continued fraction for certain cubic irrationalities

Authors: H. C. Williams and G. W. Dueck
Journal: Math. Comp. 42 (1984), 683-705
MSC: Primary 11J70; Secondary 11A55, 11Y65
DOI: https://doi.org/10.1090/S0025-5718-1984-0736461-7
MathSciNet review: 736461
Full-text PDF Free Access

Abstract: Let $\theta$ be any irrational and define $Ne(\theta )$ to be that integer such that $|\theta - Ne(\theta )|\; < \frac {1}{2}$. Put ${\rho _0} = \theta$, ${r_0} = Ne({\rho _0})$, ${\rho _{k + 1}} = 1/({r_k} - {\rho _k})$, ${r_{k + 1}} = Ne({\rho _{k + 1}})$. Then the r’s here are the partial quotients of the nearest integer continued fraction (NICF) expansion of $\theta$. When D is a positive nonsquare integer, and $\theta = \sqrt D$, this expansion is periodic. It can be used to find the regulator of $\mathcal {Q}(\sqrt D )$ in less than 75 percent of the time needed by the usual continued fraction algorithm. A geometric interpretation of this algorithm is given and this is used to extend the NICF to a nearest integer analogue of the Voronoi Continued Fraction, which is used to find the regulator of a cubic field $\mathcal {F}$ with negative discriminant $\Delta$. This new algorithm (NIVCF) is periodic and can be used to find the regulator of $\mathcal {F}$. If $I < \sqrt {{|\Delta |/148}}$, the NIVCF algorithm can be used to find any algebraic integer $\alpha$ of $\mathcal {F}$ such that $N(\alpha ) = I$. Numerical results suggest that the NIVCF algorithm finds the regulator of $\mathcal {F} = \mathcal {Q}(\sqrt {D})$ in about 80 percent of the time needed by Voronoi’s algorithm.

[Enhancements On Off] (What's this?)

Retrieve articles in Mathematics of Computation with MSC: 11J70, 11A55, 11Y65

Retrieve articles in all journals with MSC: 11J70, 11A55, 11Y65