Continued Fraction Arithmetic in Haskell
I learned the algorithm to do arithmetic on continued fractions from the talk by Mark Jason Dominus. This algorithm can be generalized to handle many other kind of functions.
I wrote an module ContinuedFraction in Haskell. It is an instance of the type class RealFrac. So you can use the four arithmetic operations like it’s any other kind of real numbers.
A continued fraction is implemented as a list of
Integral. Infinite continued fraction is possible! Although
lazy evaluation make it easy to get only the first terms, some operation will not terminate.
Currently, the only one I know of is comparing two equal infinite
continued fractions. So make sure only compare a truncated version of
two infinite continued fractions.
It is possible to create formal continued fractions that doesn’t correspond to any real number. No one know what will the arithmetic outcomes be.
A continued fraction is canonical if the sign of all the numbers are
the same. One can create non-canonical continued fractions that does
converge to a real number. For example,
ContinuedFraction [1,1,-2] is actually
ContinuedFraction [3]. Conversion to canonical version is
easy, add it by ContinuedFraction [0].
Order operations does not work with non-canonical representations.
The code will stay in this page until one day I have the patience and motivation to make this into a package. This is why I need a internship in a company that actually use Haskell.
I hope people can catch possible bugs. I’m open to suggestions!