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 | References | Similar Articles | Additional Information

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.

- William W. Adams,
*On a relationship between the convergents of the nearest integer and regular continued fractions*, Math. Comp.**33**(1979), no. 148, 1321–1331. MR**537978**, DOI https://doi.org/10.1090/S0025-5718-1979-0537978-9 - B. N. Delone and D. K. Faddeev,
*The theory of irrationalities of the third degree*, Translations of Mathematical Monographs, Vol. 10, American Mathematical Society, Providence, R.I., 1964. MR**0160744** - A. Hurwitz,
*Über eine besondere Art der Kettenbruch-Entwicklung reeller Grössen*, Acta Math.**12**(1889), no. 1, 367–405 (German). MR**1554778**, DOI https://doi.org/10.1007/BF02391885
B. Minnigerode, "Über eine neue Methode, die Pellsche Gleichung aufzulösen," - H. C. Williams and P. A. Buhr,
*Calculation of the regulator of ${\bf Q}(\surd D)$ by use of the nearest integer continued fraction algorithm*, Math. Comp.**33**(1979), no. 145, 369–381. MR**514833**, DOI https://doi.org/10.1090/S0025-5718-1979-0514833-1 - H. C. Williams,
*Some results concerning the nearest integer continued fraction expansion of $\surd D$*, J. Reine Angew. Math.**315**(1980), 1–15. MR**564520**, DOI https://doi.org/10.1515/crll.1980.315.1 - H. C. Williams, G. Cormack, and E. Seah,
*Calculation of the regulator of a pure cubic field*, Math. Comp.**34**(1980), no. 150, 567–611. MR**559205**, DOI https://doi.org/10.1090/S0025-5718-1980-0559205-7 - H. C. Williams,
*Improving the speed of calculating the regulator of certain pure cubic fields*, Math. Comp.**35**(1980), no. 152, 1423–1434. MR**583520**, DOI https://doi.org/10.1090/S0025-5718-1980-0583520-4 - H. C. Williams, G. W. Dueck, and B. K. Schmid,
*A rapid method of evaluating the regulator and class number of a pure cubic field*, Math. Comp.**41**(1983), no. 163, 235–286. MR**701638**, DOI https://doi.org/10.1090/S0025-5718-1983-0701638-2

*Gott. Nachr.*1873, 619-653. G. Voronoi,

*On a Generalization of the Algorithm of Continued Fractions*, Doctoral Dissertation, Warsaw, 1896. (Russian)

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

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

Additional Information

Article copyright:
© Copyright 1984
American Mathematical Society