Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

An analogue of the nearest integer continued fraction for certain cubic irrationalities
HTML articles powered by AMS MathViewer

by H. C. Williams and G. W. Dueck PDF
Math. Comp. 42 (1984), 683-705 Request permission

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 [4]{{|\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 [3]{D})$ in about 80 percent of the time needed by Voronoi’s algorithm.
References
Similar Articles
Additional Information
  • © Copyright 1984 American Mathematical Society
  • 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