Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
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
MathSciNet review: 736461
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ \theta $ be any irrational and define $ Ne(\theta )$ to be that integer such that $ \vert\theta - Ne(\theta )\vert\; < \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[4]{{\vert\Delta \vert/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[3]{D})$ in about 80 percent of the time needed by Voronoi's algorithm.


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


Similar Articles

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

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


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1984-0736461-7
PII: S 0025-5718(1984)0736461-7
Article copyright: © Copyright 1984 American Mathematical Society