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 be any irrational and define to be that integer such that . Put , , , . Then the *r*'s here are the partial quotients of the nearest integer continued fraction (NICF) expansion of . When *D* is a positive nonsquare integer, and , this expansion is periodic. It can be used to find the regulator of 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 with negative discriminant . This new algorithm (NIVCF) is periodic and can be used to find the regulator of .

If , the NIVCF algorithm can be used to find any algebraic integer of such that . Numerical results suggest that the NIVCF algorithm finds the regulator of in about 80 percent of the time needed by Voronoi's algorithm.

**[1]**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**, 10.1090/S0025-5718-1979-0537978-9**[2]**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****[3]**A. Hurwitz,*Über eine besondere Art der Kettenbruch-Entwicklung reeller Grössen*, Acta Math.**12**(1889), no. 1, 367–405 (German). MR**1554778**, 10.1007/BF02391885**[4]**B. Minnigerode, "Über eine neue Methode, die Pellsche Gleichung aufzulösen,"*Gott. Nachr.*1873, 619-653.**[5]**G. Voronoi,*On a Generalization of the Algorithm of Continued Fractions*, Doctoral Dissertation, Warsaw, 1896. (Russian)**[6]**H. C. Williams and P. A. Buhr,*Calculation of the regulator of 𝑄(√𝐷) by use of the nearest integer continued fraction algorithm*, Math. Comp.**33**(1979), no. 145, 369–381. MR**514833**, 10.1090/S0025-5718-1979-0514833-1**[7]**H. C. Williams,*Some results concerning the nearest integer continued fraction expansion of √𝐷*, J. Reine Angew. Math.**315**(1980), 1–15. MR**564520**, 10.1515/crll.1980.315.1**[8]**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**, 10.1090/S0025-5718-1980-0559205-7**[9]**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**, 10.1090/S0025-5718-1980-0583520-4**[10]**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**, 10.1090/S0025-5718-1983-0701638-2

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

Article copyright:
© Copyright 1984
American Mathematical Society