An Infinite Precision Implementation of Regular Periodic Infinite Continued Fractions

We give a detailed description of the process that is used to obtain the regular periodic continued fraction that represents D, where D is a non-square positive integer. We give a new combinatorial proof of Lagrange’s theorem, showing that this process eventually enters a loop. We provide an infinite precision implementation of this process with the GMP library. We consider two algorithms for identifying the initial states, before the process reaches a state in the loop, and both require storing a constant amount of integers. Our experimental results show that the algorithm based on Galois’s criteria is faster than using Floyd’s algorithm, especially when the number of initial states is small. We also give an implementation of the inverse process of determining a degree-two polynomial that yields a particular continued fraction.