__all__ = [
'continued_fraction_real',
'continued_fraction_rational',
'convergent',
'convergents',
'fraction_from_coefficients',
'fraction_from_elements',
'left_mediant',
'mediant',
'remainder',
'remainders',
'right_mediant',
]
# -- IMPORTS --
# -- Standard libraries --
import decimal
import functools
import typing
import warnings
from decimal import Decimal
from fractions import Fraction
# -- 3rd party libraries --
# -- Internal libraries --
[docs]
def continued_fraction_rational(frac: Fraction, /) -> typing.Generator[int, None, None]: # pragma: no cover
"""Implementation of the core continued fraction algorithm which generates the (ordered) sequence of coefficients of the (finite) simple continued fraction of the given rational number.
The resulting sequence of coefficients :math:`a_0,a_1,\\ldots a_n`, defines
the simple continued fraction:
.. math::
a_0 + \\cfrac{1}{a_1 + \\cfrac{1}{a_2 + \\ddots\\cfrac{1}{a_{n - 1} + \\cfrac{1}{a_n}}}}
which is also written more compactly as:
.. math::
[a_0; a_1, a_2\\ldots, a_n]
The order of the continued fraction is said to be :math:`n`. If the last
coefficient :math:`a_n = 1` the sequence can be rewritten as
:math:`[a_0; a_1, a_2\\ldots, a_{n - 1} + 1]`, which is then unique for
the given rational.
Negative rational numbers can also be represented in this way, provided we
use the `Euclidean division lemma <https://en.wikipedia.org/wiki/Euclid%27s_lemma>`_.
Parameters
----------
frac : `fractions.Fraction`
The rational number to represented as a simple continued fraction.
Yields
------
int
Coefficients of the unique simple continued fraction of the given
rational number.
Examples
--------
A few examples are given below of how this function can be used.
>>> for e in continued_fraction_rational(Fraction(649, 200)):
... print(e)
...
3
4
12
4
>>> tuple(continued_fraction_rational(Fraction(415, 93)))
(4, 2, 6, 7)
>>> tuple(continued_fraction_rational(Fraction(-649, 200)))
(-4, 1, 3, 12, 4)
>>> tuple(continued_fraction_rational(Fraction(123235, 334505)))
(0, 2, 1, 2, 1, 1, 250, 1, 13)
Notes
-----
Every rational number has a unique simple continued fraction
:math:`[a_0;a_1,a_2,\\ldots, a_n]`, where :math:`a_n > 1`, and this
function will always produce this unique represention for any given
rational.
"""
x, y = frac.as_integer_ratio()
while y:
quo, rem = divmod(x, y)
yield quo
x, y = y, rem
[docs]
def continued_fraction_real(x: int | Fraction | float | str | Decimal, /) -> typing.Generator[int, None, None]:
"""Generates a (finite) sequence of elements of a (simple) continued fraction of the given real number.
The result may not always be exact, but an approximation depending on
whether the given number :math:`x` has an exact binary floating point
representation.
The simple continued fraction representation of :math:`x` is a number of
the form
.. math::
a_0 + \\cfrac{1}{a_1 + \\cfrac{1}{a_2 + \\ddots}}
where :math:`a_0 = [x]` is the integer part of :math:`x`, and the
:math:`a_1,a_2\\ldots` are the (non-negative) quotients obtained by a
repeated application of `Euclidean division <https://en.wikipedia.org/wiki/Euclidean_division>`_
to the fractional part :math:`x - [x]`, which is called the remainder.
If the last coefficient :math:`a_n = 1` the sequence can be rewritten as
:math:`[a_0; a_1, a_2\\ldots, a_{n - 1} + 1]`.
As Python :py:class:`float` values, like all floating point
implementations, are `finite precision representations <https://docs.python.org/3/tutorial/floatingpoint.html>`_
of real numbers, the resulting simple continued fraction of :math:`x`
generated by this function may be approximate, not exact, and also not
necessarily unique.
For non-rational real numbers it is best to pass :py:class:`decimal.Decimal`
values, with the `context precision <https://docs.python.org/3.12/library/decimal.html#context-objects>`_
set to the highest level possible.
The results for rational numbers are guaranteed to be exact however large
the number, subject to memory and hardware limitations of the running
environment.
Invalid values will generate an error in either the
:py:class:`fractions.Fraction` or :py:class:`decimal.Decimal` classes -
no errors are raised directly in the function itself.
Parameters
----------
x : int, fractions.Fraction, float, str, decimal.Decimal
The real number to represent as a simple continued fraction.
Yields
------
int
Elements of a simple continued fraction of the given real number.
Examples
--------
A few examples are given below of how this function can be used.
>>> list(continued_fraction_real(5000))
[5000]
>>> list(continued_fraction_real(Fraction(7, 4)))
[1, 1, 3]
>>> list(continued_fraction_real(-5000.0))
[-5000]
>>> list(continued_fraction_real(2/5))
[0, 2, 2, 1801439850948198]
>>> list(continued_fraction_real('2/5'))
[0, 2, 2]
>>> list(continued_fraction_real('-1/3'))
[-1, 1, 2]
>>> list(continued_fraction_real(1/1j))
Traceback (most recent call last):
...
TypeError: conversion from complex to Decimal is not supported
>>> list(continued_fraction_real("not a numeric string"))
Traceback (most recent call last):
...
decimal.InvalidOperation: [<class 'decimal.ConversionSyntax'>]
>>> list(continued_fraction_real(-649/200))
[-4, 1, 3, 12, 3, 1, 234562480591, 2, 5, 2]
>>> list(continued_fraction_real('-649/200'))
[-4, 1, 3, 12, 4]
>>> list(continued_fraction_real('-649/-200'))
Traceback (most recent call last):
...
ValueError: Invalid literal for Fraction: '-649/-200'
>>> list(continued_fraction_real(Decimal('0.3333')))
[0, 3, 3333]
"""
if isinstance(x, int):
yield x
elif isinstance(x, Fraction):
yield from continued_fraction_rational(x)
elif isinstance(x, float):
yield from continued_fraction_rational(Fraction(*Decimal.from_float(x).as_integer_ratio()))
elif isinstance(x, str) and '/' in x:
yield from continued_fraction_rational(Fraction(x))
else:
yield from continued_fraction_rational(Fraction(*(Decimal(x).as_integer_ratio())))
[docs]
def convergent(k: int, *coeffs: int) -> Fraction:
"""Returns the :math:`k`-th convergent of a (simple) continued fraction from a sequence of its coefficients.
Given a (simple) continued fraction :math:`[a_0;a_1,a_2,\\ldots]` the
:math:`k`-th convergent is defined as:
.. math::
C_k = a_0 + \\cfrac{1}{a_1 + \\cfrac{1}{a_2 \\ddots \\cfrac{1}{a_{k-1} + \\cfrac{1}{a_k}}}}
The result is a :py:class:`fractions.Fraction` instance.
The integer :math:`k` is called the order of the convergent, and if
:math:`[a_0;a_1,a_2,\\ldots]` is finite of order :math:`n` then it has
exactly :math:`n + 1` convergents :math:`C_0,C_1,C_2,\\ldots,C_n` where
the :math:`k`-th convergent :math:`C_k = \\frac{p_k}{q_k}` is given by
the recurrence relation:
.. math::
\\begin{align}
p_k &= a_kp_{k - 1} + p_{k - 2} \\\\
q_k &= a_kq_{k - 1} + q_{k - 2}, \\hskip{3em} k \\geq 3
\\end{align}
where :math:`p_0 = a_0`, :math:`q_0 = 1`, :math:`p_1 = p_1p_0 + 1`,
and :math:`q_1 = p_1`.
This function is a faithful implementation of this algorithm.
A :py:class:`ValueError` is raised if :math:`k` is not an integer or is an
integer greater than the number of coefficients, or if any of the
coefficient are not integers.
Parameters
----------
k : `int`
The order of the convergent. Must be a non-negative integer less than
the number of coefficients.
*coeffs : `int`
A variable-length sequence of integer coefficients of a continued
fraction.
Returns
-------
fractions.Fraction
A rational fraction constructed from the given sequence of coefficients
of
a continued fraction, representing the :math:`k`-order convergent of a
(finite) simple continued fraction as given by a sequence of coefficients.
Raises
------
ValueError
If :math:`k` is not a non-negative integer less than the number of
coefficients, or if any of the elements are not integers.
Examples
--------
>>> convergent(0, 3, 4, 12, 4)
Fraction(3, 1)
>>> convergent(1, 3, 4, 12, 4)
Fraction(13, 4)
>>> convergent(2, 3, 4, 12, 4)
Fraction(159, 49)
>>> convergent(3, 3, 4, 12, 4)
Fraction(649, 200)
>>> convergent(3)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> convergent(-1, 3, 4, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> convergent(4, 3, 4, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
"""
# Define the order of the continued fraction - may be ``-1`` if no elements
# are given.
n = len(coeffs) - 1
if n == -1 or not isinstance(k, int) or k < 0 or k > n or any(not isinstance(coeffs[i], int) or coeffs[i] < 1 for i in range(1, n + 1)):
raise ValueError(
"`k` must be a non-negative integer not exceeding the order of "
"the continued fraction (number of tail coefficients), and the tail "
"coefficients must all be positive integers."
)
a, b = coeffs[0], 1
if k == 0:
return Fraction(a, b)
c, d = (coeffs[1] * a) + b, coeffs[1]
if k == 1:
return Fraction(c, d)
for e in coeffs[2:k + 1]:
p, q = (e * c) + a, (e * d) + b
a, b = c, d
c, d = p, q
return Fraction(p, q)
[docs]
def convergents(*coeffs: int) -> typing.Generator[Fraction, None, None]:
"""Generates an (ordered) sequence of all convergents of a (simple) continued fraction from a sequence of its coefficients.
If :math:`n` is the order of the continued fraction represented by the
given sequence of its coefficients then there are :math:`n + 1` convergents
:math:`C_0, C_1, \\ldots, C_n`, and the function generates these in that
order.
Parameters
----------
*elements : `int`
A variable-length sequence of integer coefficients of a (simple)
continued fraction.
Yields
------
fractions.Fraction
Each convergent that is generated is a :py:class:`fractions.Fraction`
instance and a :math:`k`-th convergent of the given continued fraction.
Raises
------
ValueError
If there are any non-integer coefficients, or the tail coefficients
are not positive integers.
Examples
--------
>>> tuple(convergents(3))
(Fraction(3, 1),)
>>> tuple(convergents(3, 2))
(Fraction(3, 1), Fraction(7, 2))
>>> tuple(convergents(3, 4, 12, 4))
(Fraction(3, 1), Fraction(13, 4), Fraction(159, 49), Fraction(649, 200))
>>> tuple(convergents(-5, 1, 1, 6, 7))
(Fraction(-5, 1), Fraction(-4, 1), Fraction(-9, 2), Fraction(-58, 13), Fraction(-415, 93))
>>> tuple(convergents(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
(Fraction(1, 1), Fraction(3, 2), Fraction(10, 7), Fraction(43, 30), Fraction(225, 157), Fraction(1393, 972), Fraction(9976, 6961), Fraction(81201, 56660), Fraction(740785, 516901), Fraction(7489051, 5225670))
"""
# Define the order of the continued fraction - may be ``-1`` if no coefficients
# are given.
n = len(coeffs) - 1
if n == -1 or any(not isinstance(coeffs[i], int) or (coeffs[i] <= 0 and i > 0) for i in range(n + 1)):
raise ValueError(
"Continued fraction elements must be coefficients, and all \n"
"tail coefficients (from the 1st coefficient onwards) must be positive."
)
a, b = coeffs[0], 1
yield Fraction(a, b)
if n > 0:
c, d = (coeffs[1] * a) + b, coeffs[1]
yield Fraction(c, d)
if n > 1:
for e in coeffs[2:]:
p, q = (e * c) + a, (e * d) + b
yield Fraction(p, q)
a, b = c, d
c, d = p, q
def fraction_from_elements(*elements: int) -> Fraction:
"""Returns the rational number represented by a (simple) continued fraction from a sequence of its elements.
The elements must be given as positional arguments: if your elements
are contained in an iterable unpack them in the function call using the
unpacking operator ``*``, as described in the examples below.
Parameters
----------
*elements : `int`
A variable-length sequence of integer elements of a simple continued
fraction.
Returns
-------
fractions.Fraction
A rational number constructed from a sequence of elements of a simple
continued fraction which represents the number.
Raises
------
ValueError
If any of the elements are not integers.
Examples
--------
>>> fraction_from_elements(3, 4, 12, 4)
Fraction(649, 200)
>>> fraction_from_elements(-4, 1, 3, 12, 4)
Fraction(-649, 200)
>>> fraction_from_elements(4, 2, 6, 7)
Fraction(415, 93)
>>> fraction_from_elements(*[4, 2, 6, 7])
Fraction(415, 93)
>>> fraction_from_elements(4.5, 2, 6, 7)
Traceback (most recent call last):
...
ValueError: Continued fraction elements must be integers
"""
warnings.warn(
"The `from_elements` function is deprecated and will be removed "
"in future releases. Please use the `from_coefficients` instead."
)
if any(not isinstance(elem, int) for elem in elements):
raise ValueError("Continued fraction elements must be integers")
return convergent(len(elements) - 1, *elements)
[docs]
def fraction_from_coefficients(*coeffs: int) -> Fraction:
"""Returns the rational number represented by a (simple) continued fraction from a sequence of its coefficients.
The coefficient must be given as positional arguments: if your coefficients
are contained in an iterable unpack them in the function call using the
unpacking operator ``*``, as described in the examples below.
Parameters
----------
*coeffs : `int`
A variable-length sequence of integer coefficients of a simple
continued fraction.
Returns
-------
fractions.Fraction
A rational number constructed from a sequence of coefficients of a
simple continued fraction which represents the number.
Raises
------
ValueError
If any of the coefficients are not integers, or the tail coefficients
are not positive.
Examples
--------
>>> fraction_from_coefficients(3, 4, 12, 4)
Fraction(649, 200)
>>> fraction_from_coefficients(-4, 1, 3, 12, 4)
Fraction(-649, 200)
>>> fraction_from_coefficients(4, 2, 6, 7)
Fraction(415, 93)
>>> fraction_from_coefficients(*[4, 2, 6, 7])
Fraction(415, 93)
>>> fraction_from_coefficients(4.5, 2, 6, 7)
Traceback (most recent call last):
...
ValueError: Continued fraction coefficients must be integers, and all coefficients from the 1st onwards must be positive.
"""
n = len(coeffs)
if any(not isinstance(coeffs[i], int) or (i > 0 and coeffs[i] < 1) for i in range(n)):
raise ValueError(
"Continued fraction coefficients must be integers, and "
"all coefficients from the 1st onwards must be positive."
)
return convergent(len(coeffs) - 1, *coeffs)
[docs]
def remainder(k: int, *coeffs: int) -> Fraction:
"""Returns the :math:`k`-th remainder of a (simple) continued fraction from a sequence of its coefficients.
Given a (simple) continued fraction :math:`[a_0;a_1,a_2,\\ldots]` the
:math:`k`-th remainder :math:`R_k` is the (simple) continued fraction
:math:`[a_k; a_{k + 1}, a_{k + 2}, \\ldots]`:
.. math::
R_k = a_k + \\cfrac{1}{a_{k + 1} + \\cfrac{1}{a_{k + 2} \\ddots }}
where :math:`R_0` is just the original continued fraction, i.e.
:math:`R_0 = [a_0; a_1, a_2, \\ldots]`.
The remainders have the property that:
.. math::
R_{k - 1} = a_{k - 1} + \\frac{1}{R_k}, \\hskip{3em} k \\geq 1
If the continued fraction :math:`[a_0; a_1, a_2,\\ldots]` is finite of
order :math:`n` then all :math:`R_k` are rational. If we let
:math:`R_k = \\frac{s_k}{t_k}` then the property above can be written as:
.. math::
R_{k - 1} = \\frac{s_{k - 1}}{t_{k - 1}} = \\frac{a_{k - 1}s_k + t_k}{s_k}, \\hskip{3em} k \\geq 1
As this library can only represent finite continued fractions, this
function always produces remainders as instances of
:py:class:`~fractions.Fraction`.
The integer :math:`k` must be non-negative and cannot exceed the order
of the continued fraction, i.e. the number of tail coefficients.
Parameters
----------
k : `int`
The index of the remainder. Must be a non-negative integer not
exceeding the order of the continued fraction.
*elements : `int`
A variable-length sequence of integer coefficients of a (simple)
continued fraction.
Returns
-------
fractions.Fraction
A rational fraction constructed from the given sequence of
coefficients of a continued fraction, representing its :math:`k`-th
remainder, as defined above.
Raises
------
ValueError
If :math:`k` is not an integer, or is an integer greater than the
number of coefficients, or if any of the coefficients are not integers,
or if the tail coefficients are not positive integers.
Examples
--------
>>> remainder(0, 3, 4, 12, 4)
Fraction(649, 200)
>>> remainder(1, 3, 4, 12, 4)
Fraction(200, 49)
>>> remainder(2, 3, 4, 12, 4)
Fraction(49, 4)
>>> remainder(3, 3, 4, 12, 4)
Fraction(4, 1)
>>> remainder(0, -5, 1, 1, 6, 7)
Fraction(-415, 93)
>>> remainder(1, -5, 1, 1, 6, 7)
Fraction(93, 50)
>>> remainder(2, -5, 1, 1, 6, 7)
Fraction(50, 43)
>>> remainder(3, -5, 1, 1, 6, 7)
Fraction(43, 7)
>>> remainder(4, -5, 1, 1, 6, 7)
Fraction(7, 1)
>>> remainder(1)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> remainder(-1, 3, 4, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> remainder(4, 3, 4, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> remainder(1, 3, 0, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> remainder(1, 3, -1, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
"""
# Define the order of the continued fraction - may be ``-1`` if no
# coefficients are given.
n = len(coeffs) - 1
if n == -1 or not isinstance(k, int) or k < 0 or k > n or any(not isinstance(coeffs[i], int) or coeffs[i] < 1 for i in range(1, n + 1)):
raise ValueError(
"`k` must be a non-negative integer not exceeding the order of "
"the continued fraction (number of tail coefficients), and the tail "
"coefficients must all be positive integers."
)
if k == n:
return Fraction(coeffs[-1], 1)
return fraction_from_coefficients(*coeffs[k:])
[docs]
def remainders(*coeffs: int) -> typing.Generator[Fraction, None, None]:
"""Generates an (ordered) sequence of all remainders of a (simple) continued fraction from a sequence of its coefficients in descending order of index.
If :math:`n` is the order of the continued fraction represented by the
given sequence of its coefficients then there are :math:`n + 1` remainders
:math:`R_0, R_1, \\ldots, R_n`, and the function generates these in
reverse order :math:`R_0, R_1, \\ldots, R_n`.
Parameters
----------
*elements : `int`
A variable-length sequence of integer coefficients of a (simple)
continued fraction.
Yields
------
fractions.Fraction
Each remainder generated is a :py:class:`fractions.Fraction` instance and
a :math:`k`-th remainder of the given continued fraction.
Raises
------
ValueError
If no coefficients are given, or there are any non-integer elements, or
the tail coefficients are not positive integers.
Examples
--------
>>> tuple(remainders(3))
(Fraction(3, 1),)
>>> tuple(remainders(3, 2))
(Fraction(2, 1), Fraction(7, 2))
>>> tuple(remainders(3, 4, 12, 4))
(Fraction(4, 1), Fraction(49, 4), Fraction(200, 49), Fraction(649, 200))
>>> tuple(remainders(-5, 1, 1, 6, 7))
(Fraction(7, 1), Fraction(43, 7), Fraction(50, 43), Fraction(93, 50), Fraction(-415, 93))
>>> tuple(remainders(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
(Fraction(10, 1), Fraction(91, 10), Fraction(738, 91), Fraction(5257, 738), Fraction(32280, 5257), Fraction(166657, 32280), Fraction(698908, 166657), Fraction(2263381, 698908), Fraction(5225670, 2263381), Fraction(7489051, 5225670))
>>> tuple(remainders())
Traceback (most recent call last):
...
ValueError: Continued fraction elements must be integers, and all tail elements (from the 1st element onwards) must be positive.
>>> tuple(remainders(0, 0))
Traceback (most recent call last):
...
ValueError: Continued fraction elements must be integers, and all tail elements (from the 1st element onwards) must be positive.
>>> tuple(remainders(1, 0))
Traceback (most recent call last):
...
ValueError: Continued fraction elements must be integers, and all tail elements (from the 1st element onwards) must be positive.
>>> tuple(remainders(1, 2, -1))
Traceback (most recent call last):
...
ValueError: Continued fraction elements must be integers, and all tail elements (from the 1st element onwards) must be positive.
"""
# Define the order of the continued fraction - may be ``-1`` if no elements
# are given.
n = len(coeffs) - 1
if n == -1 or any(not isinstance(coeffs[i], int) or (coeffs[i] <= 0 and i > 0) for i in range(n + 1)):
raise ValueError(
"Continued fraction elements must be integers, and all "
"tail elements (from the 1st element onwards) must be positive."
)
a, b = coeffs[-1], 1
yield Fraction(a, b)
if n > 0:
i = n - 1
while i >= 0:
a, b = coeffs[i] * a + b, a
yield Fraction(a, b)
i -= 1
# A :py:func:`functools.partial` binding of :py:func:`mediant` for left-mediants.
left_mediant = functools.partial(mediant, dir="left")
# A :py:func:`functools.partial` binding of :py:func:`mediant` for right-mediants.
right_mediant = functools.partial(mediant, dir="right")
if __name__ == "__main__": # pragma: no cover
# Doctest the module from the project root using
#
# PYTHONPATH="src" python3 -m doctest -v src/continuedfractions/lib.py
#
# NOTE: the doctest examples using ``decimal.Decimal`` values are based on
# a context precision of 28 digits
decimal.getcontext().prec = 28
import doctest
doctest.testmod()
