sr-murthy / continuedfractions

Object-oriented continued fractions with Python.

continuedfractions

A simple extension of the Python fractions standard library for working with (finite, simple) continued fractions as Python objects.

The PyPI package is updated as necessary with improvements, features and fixes. Only standard libraries are used, and the package can be installed on any Linux, Mac OS or Windows platform supporting Python 3.10, 3.11, or 3.12.

pip install -U continuedfractions

See the project docs for more details, which includes the API reference.

Continued fractions are beautiful and interesting mathematical objects, with many connections in number theory and also very useful practical applications, including the rational approximation of real numbers.

The continuedfractions package is designed for users interested in:

• learning about and working with (finite, simple) continued fractions as Python objects, in an intuitive object-oriented way
• exploring their key properties, such as elements/coefficients, convergents, semiconvergents, remainders, and others
• operating on them as rationals and instances of the standard library fractions.Fraction class
• making approximations of and experimental computations for irrational numbers
• exploring other related objects, such as mediants, and special sequences of rational numbers such as Farey sequences

Currently, it does not support the following features:

• infinite and generalised continued fractions
• symbolic representations of or operations with continued fractions

Some - but not necessarily all - of these features may be considered for future release.

The project is licensed under the Mozilla Public License 2.0.

continuedfractions's Issues

docs: documentation of rational operations for `ContinuedFraction`

Sphinx docs need updating to add content on rational operations for ContinuedFraction objects, with examples.

fix: changes in `decimal` contextual precision <-> and caching of numeric properties of `ContinuedFraction`

Changes in decimal contextual precision might cause incorrect values to be returned for the cached, numerical properties of ContinuedFraction (excluding order). Investigate further.

feat: immutable elements for `ContinuedFraction` objects

ContinuedFraction instances to have an immutable elements attribute (_elements).

Docstrings and documentation to be updated as appropriate.

fix: validation of element sequences with negative integers

Additional validation required for ContinuedFraction objects constructed from sequences of elements with negative integers - this should only be possible if the first element (a_0 = first quotient) is negative, and negative values for a_1, a_2,... etc should be considered invalid.

# Is valid
>>> ContinuedFraction.from_elements(-1, 2, 3)
ContinuedFraction(-4, 7)

# Should be invalid
>>> ContinuedFraction.from_elements(1, -2, 3)
ContinuedFraction(2, 5)

Changes required in

• continuedfraction.ContinuedFraction.from_elements

Test cases should be updated and/or added.

Docstrings and documentation should be updated as appropriate.

ci: improve CI testing strategy for Python 3.10 vs Python 3.11 & 3.12

• Move Python 3.10 jobs for MacOS to use custom MacOS 13 runner - this is mainly because, as described here, Python 3.10 is no longer compatible with GitHub Actions Arm 64 runners using the latest MacOS (>= Mac OS 14).
• Use MacOS latest OS with Arm 64 runners in the default OS matrix for Python versions >= 3.11

refactor: custom equality checking and hashing for `ContinuedFraction`

Currently, the equality check (__eq__) for ContinuedFraction instances implicitly uses the superclass Fraction.__eq__ check. This means that equality checks such as:

>>> ContinuedFraction(3, 2) == ContinuedFraction(6, 4)

involve a comparison of the numerators and denominators of the rational numbers represented by these instances, rather than the direct comparison of the elements of the (unique, finite) simple continued fractions represented by the instances.

>>> ContinuedFraction(3, 2).elements
(1, 2)
>>> ContinuedFraction(6, 4).elements
(1, 2)
>>> assert ContinuedFraction(6, 4) == ContinuedFraction(3, 2)
# True

A simple continued fraction where the last element > 1 is uniquely determined by a valid (ordered) sequence of elements.

A custom __eq__ should be implemented to check equality with other where other is an object which can be either a ContinuedFraction instance, or something else comparable to fractions.Fraction:

• if other is a ContinuedFraction compare the elements
• if not compare using Fractions.__eq__

As part of this, a custom __hash__ is also required that hashes the tuple of elements/coefficients of a ContinuedFraction instance.

Both __eq__ and __hash__ should have docstrings, and be exposed in the API reference documentation.

refactor: tweak `ContinuedFraction.convergent` method to pass in the full sequence of elements

ATM the continuedfraction.ContinuedFraction.convergent method calls the lib.convergent method with the k-th segment (CF with the first k + 1 elements of the original).

As the k-th convergent is uniquely determined by the k-th segment this works fine, but by design lib.convergent should be given the full sequence of elements of the original.

refactor: self-referential type annotations for self-referential `ContinuedFraction` methods

ATM the type annotations for ContinuedFraction class or instance methods that actually return ContinuedFraction objects are incorrect - the current return type for these is fractions.Fraction, whereas in fact they should be ContinuedFraction. To enable this a future statement is required for type annotations:

from __future__ import annotations

This is also a problem for the ContinuedFraction.validate class method and the ContinuedFraction.__init__ method, which need to be amended to accept valid input combinations involving ContinuedFraction objects.

The methods that need to be fixed are:

• ContinuedFraction.validate
• ContinuedFraction.__new__
• ContinuedFraction.from_elements
• ContinuedFraction.__init__
• All the rational operational methods, e.g. __add__, __radd__, __sub__, __rsub__, etc.

Examples in docstrings and the documentation should be updated.

feat: `ContinuedFraction` instance method for computing semi-convergents

A ContinuedFraction instance method for computing semiconvergents would be useful: if $\frac{p_{k - 1}}{ q_{k - 1}}$ and $\frac{p_k}{q_k}$ are consecutive convergents of a (possibly infinite) continued fraction $[a_0;a_1,a_2,\ldots,a_k,a_{k + 1},\ldots]$, and $m$ is any positive integer, then the fraction:

$$\frac{p_{k - 1} + mp_k}{q_{k - 1} + mq_k}$$

is called a semiconvergent of $\frac{p_{k - 1}}{ q_{k - 1}}$ and $\frac{p_k}{q_k}$. This is also the right-mediant of order $m$ of the two (consecutive) convergents, and is an intermediate fraction between them.

Sometimes, more restrictive definitions are used, especially in the context of infinite continued fractions: one such definition is the same as above, except that $m$ is required to be an integer in the range $0..a_{k + 1}$, i.e. $0 \leq m \leq a_{k + 1}$. Another is also the same as above except that $m$ is required to be an integer in the range $1..a_{k + 1} - 1$, i.e. $0 &lt; m &lt; a_{k + 1}$.

The looser definition is preferable as it would allow the user to determine what $m$ should be. The method should be an instance method of ContinuedFraction and take two arguments:

1. A positive integer $k$ determining the convergent $p_{k - 1}$, and its successor $p_k$, for which a semiconvergent is sought.
2. Any positive integer $m$ determining the "index" of that semi-convergent.

feat: cached properties for convergents and remainders of `ContinuedFraction` objects

Implement cached properties for convergents and remainders to avoid manual recomputation on each new call. The cached properties would need the (integer) order of the convergent or remainder as its (sole) argument.

In its simplest implementation, this would just involve decorating the existing convergent and remainder methods with functools.cached_property.

Documentation should be updated with an explanation of the caching mechanism and examples.

feat: immutable Numpy arrays for `ContinuedFraction` elements [?]

If static / immutable Numpy arrays are
possible / practical, it may be useful to replace the current tuple implementation of the elements array (in ContinuedFraction.__init__, with the corresponding property) with an immutable Numpy array.

This is minimally refactoring, but really an enhancement.

The documentation should be updated.

feat: cached properties for even- and odd-order convergents of `ContinuedFraction` objects

Cached properties for even- and odd-order convergents would be useful for approximations - as they have the property that they both converge monotonically to the same number but from opposite directions.

This is linked to #35, and can be implemented as part of the same PR.

The documentation should be updated with examples.

feat: `ContinuedFraction` instance methods for in-place (tail) extension and truncation

Will impact implementation of #35, as in-place modification of object state will need object caches to be updated and/or cleared.

It would be nice to have ContinuedFraction instance methods for:

• extending the sequence (from the tail) with new elements: extend(self, *new_elements: int) -> None)
• truncating the sequence (in the tail) with an existing segment of the tail (truncate(self, *elements: int) -> None)

with in-place modification of the object state. For truncate the given sequence must be a valid segment of the existing tail subsequence.

Hypothetical examples below for extend:

>>> cf = ContinuedFraction(649, 200)
>>> cf.elements
(3, 4, 12, 4)
>>> cf.extend(5, 2)
>>> cf
ContinuedFraction(7457, 2298)
>>> cf.elements
(3, 4, 12, 4, 5, 2)
>>> assert cf == ContinuedFraction.from_elements(3, 4, 12, 4, 5, 2)
# True

and extend:

>>> cf = ContinuedFraction(649, 200)
>>> cf.elements
(3, 4, 12, 4)
>>> cf.truncate(4)
>>> cf.elements
(3, 4, 12)
>>> assert cf == ContinuedFraction.from_elements(3, 4, 12)
>>> cf = ContinuedFraction(649, 200)
>>> cf.truncate(12, 4)
>>> cf
ContinuedFraction(3, 4)
>>> cf.elements
(3, 4)
>>> assert cf == ContinuedFraction.from_elements(3, 4)

docs: fix broken ReadTheDocs build

RTD build is broken as pyproject.toml was updated to add myst_parser to docs requirements, but the docs/requirements.txt file was not updated.

perf: benchmarked timing tests for "very large" and "very small" continued fractions

Benchmarked CI performance tests for generating continued fractions for "very large" and "very small" rationals.

The tests should be documented (in the project docs).

feat: support for infinite, generalised continued fractions

Add support for infinite, generalised continued fractions.

Implementation would probably require storing symbolic representations/expressions for the numerators and denominators, and generating the elements from those expressions.

ci: mypy type checking for ci

Add mypy type checking for CI as a GitHub Action + update TOML, lockfile.

ci: Sphinx docs CI pipeline, including RTD deployment on release PRs

A CI pipeline is required to build Sphinx docs on all non-main branch updates + a manually triggered job to deploy docs to RTD on release PRs.

feat: support for symbolic representations / computations

Support for symbolic representations / computations involving parameterised class methods for convergents, remainders, mediants via Sympy.

Add docs site - move docs out of README

Move docs out of README, and publish them separately, as part of a CI release pipeline.

docs: tidy up Sphinx docs

A general tidy up of the Sphinx docs source typesetting + HTML output is required. Details to be added later.

refactor: optimise computation of convergents and remainders properties in `ContinuedFraction`

The ContinuedFraction.convergents property requires refactoring - the current version returns a static / immutable dict of all convergents keyed by order, and this becomes very inefficient as the continued fraction gets large.

A generator of all convergents may be more efficient.

As part of this refactoring a new lib method to generate the sequence of all convergents of a continued fraction given as a sequence of its elements $[a_0; a_1, a_2, \ldots, a_n]$ is required. The sequence of convergents should be in the order:

$$ \begin{align} \frac{p_0}{q_0} &= a_0 \\ \frac{p_1}{q_1} &= a_0 + \cfrac{1}{a_1} \\ \frac{p_2}{q_2} &= a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2}} \\ \vdots \\ \frac{p_n}{q_n} &= a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots \cfrac{1}{a_{n - 1} + \cfrac{1}{a_n}}}} \end{align} $$

The same applies to the ContinuedFraction.remainders property.

All docstrings, unit tests, doctests and Sphinx docs to be updated.

A related issue which needs addressing is that the indexing of convergents should not be defined by order, as some convergents have sequences of elements which terminate with ones, which makes them non-unique e.g. in the continued fraction $[-5; 1, 1, 6, 7]$ of $-\frac{415}{93}$ the 1st convergent $-5 + \cfrac{1}{1} = -4$ is defined by the continued fraction $[-5; 1]$ of order $1$, which is also equivalent to the continued fraction $[-4;]$ of order $0$, while the 2nd convergent $-5 + \cfrac{1}{1 + \cfrac{1}{1}} = -5 + \frac{1}{2} = -\frac{9}{2} = -4.5$ is defined by the continued fraction $[-5; 1, 1]$ of order $2$, which is equivalent to the continued fraction $[-5; 2]$ of order $1$.

Convergents should be indexed and described without reference to order, e.g. $k$-th convergent rather than $k$-order convergent, and it should be noted that the order of a convergent may diverge from the index depending on whether the sequence of elements is unique. All references in tests, docstrings and Sphinx docs should be updated.

refactor: negation op (`__neg__`) for `ContinuedFraction`

ATM the rational operation __neg__ for negation of a given ContinuedFraction object relies on the following sequence of calls:

• fractions.Fractions.__neg__ -> ContinuedFraction.__init__ -> lib.continued_fraction_from_real -> lib.continued_fraction_from_rational.

This is unnecessary and inefficient - a direct, much faster approach can be used by using the division-free algorithm for calculating the "negative" of a positive continued fraction from the elements of the positive, as described in the documentation.

ci: move CodeQL to a separate CI workflow

• Move CodeQL to a separate CI workflow (YAML)

ci: PyPI release CI pipeline

Add a release CI pipeline to automatically build and push package artifacts to PyPI from a release PR.

For the moment, GitHub releases should still be created manually, just before the PyPI releases are published and the release PRs merged.

refactor: compose division ops for `ContinuedFraction`

All division operations in ContinuedFraction:

• continuedfraction.ContinuedFraction.__truediv__
• continuedfraction.ContinuedFraction.__rtruediv__
• continuedfraction.ContinuedFraction.__floordiv__
• continuedfraction.ContinuedFraction.__rfloordiv__

can be refactored by composing the division-free algorithms for the negation and inversion of simple continued fractions of positive rational numbers, which are described in the documentation.

feat: Farey sequences

Support for (efficiently) generating Farey sequences.

Ideally, this would be implemented by an O(n) implementation of a function for generating all pairs of coprime integers <= n for a given n.

refactor: optimise generation of coprime pairs + Farey sequences

• Optimise the sequences functions for generating coprime pairs and Farey sequences - requires improvements in the the ternary tree search method sequences.KSRMTree.search_root, and possibly also the top-level search wrapper sequences.KSRMTree.search.
• Update Sphinx docs (if necessary).

feat: `ContinuedFraction` input validation, object creation + initialisation of/from `ContinuedFraction` objects

Depends on #41.

ATM the ContinuedFraction methods for validation (the class method validate), object creation (the class magic method __new__), and object initialisation (__init__) do not permit inputs which are also of type ContinuedFraction.

This should be changed to allow ContinuedFraction to be created from any valid combination of ContinuedFraction objects, whcih are listed below:

• a single ContinuedFraction obj.
• a pair of ContinuedFraction objs.
• an int and a ContinuedFraction obj. (or in reverse order)
• a fractions.Fraction and a ContinuedFraction obj. (or in reverse order)

Where two valid inputs are given, as above, they represent the numerator and denominator of the new ContinuedFraction obj. that will be constructed.

Examples in docstrings and documentation should be updated as appropriate.

feat: class framework for continued fractions

A class framework for continued fractions, to support different types of continued fractions, including:

• infinite
• generalised
• periodic

refactor: further optimisation for remainders

• Add library functions for computing remainders of continued fractions
• Use these in further optimisation of the remainders property in ContinuedFraction
• Update Sphinx docs