periodicCF: Periodic continued fraction

In numbers: Number-Theoretic Functions

Periodic continued fraction

Description

Generates a periodic continued fraction.

Usage

periodicCF(d)

Arguments

d	positive integer that is not a square number

Details

The function computes the periodic continued fraction of the square root of an integer that itself shall not be a square (because otherwise the integer square root will be returned). Note that the continued fraction of an irrational quadratic number is always a periodic continued fraction.

The first term is the biggest integer below sqrt(d) and the rest is the period of the continued fraction. The period is always exact, there is no floating point inaccuracy involved (though integer overflow may happen for very long fractions).

The underlying algorithm is sometimes called "The Fundamental Algorithm for Quadratic Numbers". The function will be utilized especially when solving Pell's equation.

Value

Returns a list with components

cf	the continued fraction with integer part and first period.
plen	the length of the period.

Note

Integer overflow may happen for very long continued fractions.

Author(s)

Hans Werner Borchers

References

Mak Trifkovic. Algebraic Theory of Quadratic Numbers. Springer Verlag, Universitext, New York 2013.

See Also

solvePellsEq

Examples

  periodicCF(2)    # sqrt(2) = [1; 2,2,2,...] = [1; (2)]

  periodicCF(1003)
  ## $cf
  ## [1] 31  1  2 31  2  1 62
  ## $plen
  ## [1] 6

numbers documentation built on Dec. 29, 2022, 4:07 p.m.