FiniteContinuedFractions.jl - a number type for rational numbers

Package Announcements
, , , ,
1

A package that provides the FiniteContinuedFraction type, an alternative to Rational. Both subtype Real.

I don’t know if FiniteContinuedFraction is ever a good replacement for Rational in package code, seeing as it’s not isbits so constructing an instance is expensive. However perhaps it could be fun for interactive play with continued fractions in the REPL.

Relevant Wikipedia pages:

Example usage:

julia> using FiniteContinuedFractions

julia> FiniteContinuedFraction(8 // 5)
1 + 1//(1 + 1//(1 + 1//2))

julia> inv(ans)
1//(1 + 1//(1 + 1//(1 + 1//2)))

julia> 1 / ans
8//5

A note on the implementation: while binary operations return Rational, the arithmetic is actually done without converting the input argumens to Rational. Rather, the Gosper/HAKMEM-inspired algorithm used produces the reduced numerator and denominator directly from the continued fractions.

It should also be possible to somewhat extend support to quadratic irrationals (the solutions of quadratic equations), in addition to the rationals, by allowing representation of (eventually) periodic (simple) continued fractions. Not sure how sensible would that be, though, considering that this class of numbers (union of the rationals and quadratic irrationals) isn’t closed for some common operations.

Looking forward to any thoughts. Also, I wonder if it’d be possible to move the package from my Gitlab to the JuliaMath Github to make it more discoverable, before registering it?

4 Likes
2

How does it compare with RealContinuedFractions.jl ?

1 Like
3

They’re quite different.

FiniteContinuedFraction.jl RealContinuedFractions.jl
The only exported name is the type FiniteContinuedFraction. The main exported name is the type ContinuedFraction.
FiniteContinuedFraction is a number, in fact it subtypes Real. ContinuedFraction isn’t a number, it seems to be somewhat of a container, though. Although it’s not an iterator and doesn’t support indexing, so its not a full featured collection, either.
Tries to play nice with the ecosystem, exposing its functionality by adding methods to pre-existing functions and constructors. RealContinuedFractions.jl exports several new functions.
Doesn’t provide any access to the convergents. It could be considered if there is desire though, I just didn’t see need for it. Provides convergent-related functions.
Supports most conversion, constructors, promotion, arithmetic and predicates that would be expected from such a (rational) number. Doesn’t seem to support any such operations.

EDIT:

Supports most conversion, constructors, promotion, arithmetic and predicates that would be expected from such a (rational) number.

TBH there’s currently no conversion from/to many relevant types. Perhaps I should add support for conversion with AbstractFloat, AbstractIrrational, etc. EDIT2: IMO this should be supported via a rationalize-like function. I can’t add relevant methods to rationalize as far as I understand the rationalize doc string, so I’ll add a rationalize_to_continued_fraction function.

2 Likes
4

Good for project Euler.

1 Like
5

The latest commit now supports signed infinities and signed zeros. Signed infinity brings FiniteContinuedFraction to feature parity with Rational, while allowing signed zero avoids the bug/loss of information in taking the inverse of negative infinity (as present with Rational).

Support for infinity allows simplifying the representation and implementation. In particular, the empty continued fraction is infinity, so zero can be simply the inverse of infinity. That said, getting the signs right in arithmetic requires some special casing :confused:.

Another change from the last post is that binary arithmetic operations between continued fractions return continued fractions, instead of Rational.

Roadmap

I’m looking into:

1 Like