from __future__ import annotations
__all__ = [
'ContinuedFraction',
]
# -- IMPORTS --
# -- Standard libraries --
import collections
import decimal
import math
import statistics
import typing
from decimal import Decimal
from fractions import Fraction
# -- 3rd party libraries --
# -- Internal libraries --
from continuedfractions.lib import (
continued_fraction_rational,
convergent,
convergents,
fraction_from_coefficients,
left_mediant,
mediant,
remainder,
remainders,
right_mediant,
)
[docs]
class ContinuedFraction(Fraction):
"""An object-oriented representation of a (finite) simple continued fraction.
An implementation of simple continued fractions as Python objects and
instances of the standard library :py:class:`fractions.Fraction` class,
with various properties for the continued fraction, including its
coefficients, the order, convergents, and remainders.
The term "simple continued fraction" denotes a specific type of continued
fraction where the fractional terms only have numerators of :math:`1`.
Arguments can be any which are valid for creating objects of the
:py:class:`fractions.Fraction` superclass.
For clarification, valid arguments can be one of the following:
* a single instance of :py:class:`numbers.Rational`, including
:py:class:`int`, :py:class:`fractions.Fraction` or
:py:class:`ContinuedFraction`, named or unnamed
* a pair of :py:class:`numbers.Rational` instances, including
:py:class:`int`, :py:class:`fractions.Fraction` and
:py:class:`ContinuedFraction`, named or unnamed
* a single :py:class:`float` or :py:class:`decimal.Decimal` value
that is not a special value such as :py:data:`math.nan`,
``float('inf')``, or ``Decimal('infinity')``
* a single numeric valid string (:py:class:`str`) - validity is
determined in the superclass by the
:py:data:`fractions._RATIONAL_FORMAT` test
"""
@property
def coefficients(self) -> typing.Generator[int, None, None]:
""":py:class:`typing.Generator`: A generator of the (ordered) sequence of coefficients of the continued fraction.
Examples
--------
>>> cf = ContinuedFraction('.12345')
>>> cf
ContinuedFraction(2469, 20000)
>>> tuple(cf.coefficients)
(0, 8, 9, 1, 21, 1, 1, 5)
"""
yield from continued_fraction_rational(self)
@property
def order(self) -> int:
""":py:class:`int`: The order of the continued fraction, which is the number of its coefficients minus :math:`1`.
Examples
--------
>>> cf = ContinuedFraction('.12345')
>>> cf
ContinuedFraction(2469, 20000)
>>> tuple(cf.coefficients)
(0, 8, 9, 1, 21, 1, 1, 5)
>>> cf.order
7
"""
return sum(1 for coeff in self.coefficients) - 1
@property
def counter(self) -> collections.Counter:
""":py:class:`collections.Counter` : A counter for the coefficients.
Examples
--------
>>> cf = ContinuedFraction(928374923, 8249234)
>>> cf.counter
Counter({1: 6, 2: 3, 24: 2, 112: 1, 5: 1, 3: 1})
"""
return collections.Counter(self.coefficients)
@property
def khinchin_mean(self) -> decimal.Decimal | None:
""":py:class:`decimal.Decimal` or :py:data:`None`: The Khinchin mean of the continued fraction, which is defined as the geometric mean of all the tail coefficients.
We define the Khinchin mean :math:`K_n` of a (simple) continued
fraction :math:`[a_0; a_1, a_2, \\ldots, a_n]` as:
.. math::
K_n := \\sqrt[n]{a_1a_2 \\cdots a_n} = \\left( a_1a_2 \\cdots a_n \\right)^{\\frac{1}{n}}, \\hskip{3em} n \\geq 1
This property is intended to make it easier to study the limit of
:math:`K_n` as :math:`n \\to \\infty`.
In the special case of integers or fractions representing integers,
whose continued fraction representations consist of only a single
element, a null value is returned.
Examples
--------
Note that the default :py:mod:`decimal` context precision of :math:`28`
is used in these examples.
>>> tuple(ContinuedFraction(649, 200).coefficients)
(3, 4, 12, 4)
>>> ContinuedFraction(649, 200).khinchin_mean
Decimal('5.76899828122963409526846589869819581508636474609375')
>>> tuple(ContinuedFraction(415, 93).coefficients)
(4, 2, 6, 7)
>>> ContinuedFraction(415, 93).khinchin_mean
Decimal('4.37951913988788898990378584130667150020599365234375')
>>> tuple((ContinuedFraction(649, 200) + ContinuedFraction(415, 93)).coefficients)
(7, 1, 2, 2, 2, 1, 1, 11, 1, 2, 12)
>>> (ContinuedFraction(649, 200) + ContinuedFraction(415, 93)).khinchin_mean
Decimal('2.15015313349074244086978069390170276165008544921875')
>>> ContinuedFraction(5000).khinchin_mean
"""
coeffs = tuple(self.coefficients)
if self.order == 1:
return Decimal(coeffs[-1])
elif self.order > 1:
return Decimal(statistics.geometric_mean(coeffs[1:]))
[docs]
@classmethod
def from_coefficients(cls, *coeffs: int) -> ContinuedFraction:
"""Returns a :py:class:`ContinuedFraction` instance from a sequence of (integer) coefficients of a (finite) simple continued fraction.
Invalid coefficients will trigger a :py:class:`ValueError`.
Parameters
----------
*coeffs : int
An ordered sequence of integer coefficients of a (finite) simple
continued fraction.
Returns
-------
ContinuedFraction
A new and fully initialised instance of :py:class:`ContinuedFraction` with
the given sequence of coefficients.
Raises
------
ValueError
If the given coefficients include non-integers, or where the tail
segment contains non-positive integers.
Examples
--------
Constructing a continued fraction for the rational :math:`\\frac{649}{200}` using
the sequence of coefficients :math:`3, 4, 12, 4`.
>>> c1 = ContinuedFraction.from_coefficients(3, 4, 12, 4)
>>> c1
ContinuedFraction(649, 200)
Constructing the continued fraction of the (multiplicative) inverse :math:`\\frac{200}{649}`
using the sequence of coefficients :math:`0, 3, 4, 12, 4`.
>>> c2 = ContinuedFraction.from_coefficients(0, 3, 4, 12, 4)
>>> c2
ContinuedFraction(200, 649)
Validation of coefficients.
>>> ContinuedFraction.from_coefficients('0', 1)
Traceback (most recent call last):
...
ValueError: Continued fraction coefficients must be integers, and all coefficients from the 1st onwards must be positive.
>>> ContinuedFraction.from_coefficients(0, 1, 2.5)
Traceback (most recent call last):
...
ValueError: Continued fraction coefficients must be integers, and all coefficients from the 1st onwards must be positive.
>>> ContinuedFraction.from_coefficients(1, 0)
Traceback (most recent call last):
...
ValueError: Continued fraction coefficients must be integers, and all coefficients from the 1st onwards must be positive.
>>> ContinuedFraction.from_coefficients(1, -1)
Traceback (most recent call last):
...
ValueError: Continued fraction coefficients must be integers, and all coefficients from the 1st onwards must be positive.
"""
# Create a new ``ContinuedFraction`` instance from the given coefficients
if any(not isinstance(coeff, int) or (coeff <= 0 and i > 0) for i, coeff in enumerate(coeffs)):
raise ValueError(
"Continued fraction coefficients must be integers, and all "
"coefficients from the 1st onwards must be positive."
)
# A step to ensure uniqueness of the simple form of the continued
# fraction - if the last element is ``1`` it can be "removed" by
# adding it to the second last element, thereby shortening the
# sequence by one element. The resulting simple continued
# fraction becomes unique for the number that is represented.
if len(coeffs) > 1 and coeffs[-1] == 1:
coeffs = coeffs[:-2] + (coeffs[-2] + 1,)
# Call the superclass constructor with the ``fractions.Fraction``
# instance returned by ``lib.fraction_from_coefficients`` - this will
# be the highest-order convergent of the simple continued
# fraction represented by the given sequence of coefficients
self = cls(fraction_from_coefficients(*coeffs))
return self
[docs]
def extend(self, *new_coeffs: int) -> None:
"""Performs an in-place tail extension of the current sequence of coefficients.
Raises a :py:class:`ValueError` if the given sequence of values is
empty, or includes non-integers or non-positive integers.
.. note::
As this method performs an in-place modification of the existing/
current instance the object ID remains the same.
Parameters
----------
new_coeffs : int
An (ordered) sequence of new (positive) integer coefficients by
which the tail of the existing sequence of coefficients is to be
extended.
Raises
------
ValueError
If the given sequence is empty or includes non-integers or non-
positive integers.
Examples
--------
>>> cf = ContinuedFraction('3.245')
>>> cf
ContinuedFraction(649, 200)
>>> tuple(cf.coefficients)
(3, 4, 12, 4)
>>> cf.order
3
>>> tuple(cf.convergents)
((0, ContinuedFraction(3, 1)), (1, ContinuedFraction(13, 4)), (2, ContinuedFraction(159, 49)), (3, ContinuedFraction(649, 200)))
>>> tuple(cf.remainders)
((3, ContinuedFraction(4, 1)), (2, ContinuedFraction(49, 4)), (1, ContinuedFraction(200, 49)), (0, ContinuedFraction(649, 200)))
>>> cf.extend(5, 2)
>>> cf
ContinuedFraction(7457, 2298)
>>> tuple(cf.coefficients)
(3, 4, 12, 4, 5, 2)
>>> cf.order
5
>>> tuple(cf.convergents)
((0, ContinuedFraction(3, 1)), (1, ContinuedFraction(13, 4)), (2, ContinuedFraction(159, 49)), (3, ContinuedFraction(649, 200)), (4, ContinuedFraction(3404, 1049)), (5, ContinuedFraction(7457, 2298)))
>>> tuple(cf.remainders)
((5, ContinuedFraction(2, 1)), (4, ContinuedFraction(11, 2)), (3, ContinuedFraction(46, 11)), (2, ContinuedFraction(563, 46)), (1, ContinuedFraction(2298, 563)), (0, ContinuedFraction(7457, 2298)))
>>> cf = ContinuedFraction(649, 200)
>>> cf.extend(0, 1)
Traceback (most recent call last):
...
ValueError: The coefficients to be added to the tail must be positive integers.
>>> cf.extend(1, -1)
Traceback (most recent call last):
...
ValueError: The coefficients to be added to the tail must be positive integers.
"""
if not new_coeffs or any(not isinstance(e, int) or e < 1 for e in new_coeffs):
raise ValueError(
"The coefficients to be added to the tail must be positive "
"integers."
)
coeffs = tuple(self.coefficients) + new_coeffs
# A step to ensure uniqueness of the simple form of the continued
# fraction - if the last of the new coefficients is ``1`` it can be
# "absorbed" by adding it to the second last coefficient, thereby
# shortening the sequence by one. The resulting simple continued
# fraction becomes unique for the number that is represented.
if len(coeffs) > 1 and coeffs[-1] == 1:
coeffs = coeffs[:-2] + (coeffs[-2] + 1,)
fraction = fraction_from_coefficients(*coeffs)
self._numerator, self._denominator = fraction.as_integer_ratio()
[docs]
def truncate(self, *tail_coeffs: int) -> None:
"""Performs an in-place truncation of a contiguous trailing segment of the coefficients in the tail.
.. note::
As this method performs an in-place modification of the existing/
current instance the object ID remains the same.
Parameters
----------
tail_coeffs : int
An (ordered) sequence of (positive) integers which form a
contiguous trailing segment of the current sequence of coefficients
and is to be truncated.
Raises
------
ValueError
If the tail coefficients provided are not positive integers, or do
not form a contiguous trailing segment, or their number exceeds the
length of the existing tail, i.e. the order of the continued
fraction represented by the instance.
Examples
--------
>>> cf = ContinuedFraction('3.245')
>>> cf
ContinuedFraction(649, 200)
>>> tuple(cf.coefficients)
(3, 4, 12, 4)
>>> cf.order
3
>>> cf.counter
Counter({4: 2, 3: 1, 12: 1})
>>> tuple(cf.convergents)
((0, ContinuedFraction(3, 1)), (1, ContinuedFraction(13, 4)), (2, ContinuedFraction(159, 49)), (3, ContinuedFraction(649, 200)))
>>> tuple(cf.remainders)
((3, ContinuedFraction(4, 1)), (2, ContinuedFraction(49, 4)), (1, ContinuedFraction(200, 49)), (0, ContinuedFraction(649, 200)))
>>> cf.truncate(12, 4)
>>> cf
ContinuedFraction(13, 4)
>>> tuple(cf.coefficients)
(3, 4)
>>> cf.order
1
>>> tuple(cf.convergents)
((0, ContinuedFraction(3, 1)), (1, ContinuedFraction(13, 4)))
>>> tuple(cf.remainders)
((1, ContinuedFraction(4, 1)), (0, ContinuedFraction(13, 4)))
>>> cf = ContinuedFraction(649, 200)
>>> cf.truncate(4, 12)
Traceback (most recent call last):
...
ValueError: The coefficients to be truncated from the tail must consist of positive integers and form a contiguous trailing segment of the tail.
>>> cf.truncate(3, 4, 12, 4)
Traceback (most recent call last):
...
ValueError: The coefficients to be truncated from the tail must consist of positive integers and form a contiguous trailing segment of the tail.
"""
coeffs = tuple(self.coefficients)
order = len(coeffs[1:])
truncation_length = len(tail_coeffs)
if (
not tail_coeffs or
any(not isinstance(coeff, int) or coeff < 1 for coeff in tail_coeffs) or
truncation_length > order or
coeffs[order + 1 - truncation_length:] != tail_coeffs
):
raise ValueError(
"The coefficients to be truncated from the tail must consist "
"of positive integers and form a contiguous trailing segment "
"of the tail."
)
coeffs = coeffs[:order + 1 - truncation_length]
# A step to ensure uniqueness of the simple form of the continued
# fraction - if the last coefficient is ``1`` it can be "removed" by
# adding it to the second last coefficient, thereby shortening the
# sequence by one. The resulting simple continued fraction becomes
# unique for the number that is represented.
if len(coeffs) > 1 and coeffs[-1] == 1:
coeffs = coeffs[:-2] + (coeffs[-2] + 1,)
fraction = fraction_from_coefficients(*coeffs)
self._numerator, self._denominator = fraction.as_integer_ratio()
[docs]
def as_decimal(self) -> Decimal:
"""Returns the :py:class:`decimal.Decimal` value of the continued fraction.
Returns
-------
decimal.Decimal
The :py:class:`decimal.Decimal` representation of the continued fraction.
Examples
--------
Note that the default :py:mod:`decimal` context precision of :math:`28`
is used in these examples.
>>> import math
>>> math.pi
3.141592653589793
Now construct a :py:class:`ContinuedFraction` instance from it, and check the
:py:class:`float` value.
>>> cf = ContinuedFraction(math.pi)
>>> cf
ContinuedFraction(884279719003555, 281474976710656)
>>> cf.as_decimal()
Decimal('3.141592653589793115997963469')
"""
return Decimal(self.numerator) / Decimal(self.denominator)
[docs]
def convergent(self, k: int, /) -> ContinuedFraction:
"""Returns the :math:`k`-th (simple) convergent of the continued fraction.
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:`~continuedfractions.continuedfraction.ContinuedFraction` instance.
If the continued fraction is 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`.
Parameters
----------
k : int
The index of the convergent, as described above.
Returns
-------
ContinuedFraction
A new :py:class:`ContinuedFraction` instance representing the :math:`k`-th
(simple) convergent of the original continued fraction, as
described above.
Examples
--------
>>> cf = ContinuedFraction('.12345')
>>> cf
ContinuedFraction(2469, 20000)
>>> cf.convergent(0)
ContinuedFraction(0, 1)
>>> cf.convergent(2)
ContinuedFraction(9, 73)
>>> cf.convergent(6)
ContinuedFraction(448, 3629)
>>> cf.convergent(7)
ContinuedFraction(2469, 20000)
"""
return self.__class__(convergent(k, *self.coefficients))
@property
def convergents(self) -> typing.Generator[tuple[int, ContinuedFraction], None, None]:
"""Generates an enumerated sequence of all convergents of the continued fraction.
The convergents are generated as tuples of :py:class:`int` and
:py:class:`~continuedfraction.continuedfraction.ContinuedFraction`
instances, where the integers represent the indices of the convergents.
If :math:`n` is the order of the continued fraction then :math:`n + 1`
convergents :math:`C_0, C_1, \\ldots, C_n` are generated in that order.
Yields
------
tuple
A tuple of convergent index (:py:class:`int`) and convergents
(:py:class:`~continuedfractions.continuedfraction.ContinuedFraction`)
of the continued fraction.
Examples
--------
>>> cf = ContinuedFraction('3.245')
>>> tuple(cf.convergents)
((0, ContinuedFraction(3, 1)), (1, ContinuedFraction(13, 4)), (2, ContinuedFraction(159, 49)), (3, ContinuedFraction(649, 200)))
"""
yield from enumerate(map(self.__class__, convergents(*self.coefficients)))
@property
def even_order_convergents(self) -> typing.Generator[tuple[int, ContinuedFraction], None, None]:
"""Generates an enumerated sequence of all even-order convergents of the continued fraction.
The convergents are generated as tuples of :py:class:`int` and
:py:class:`~continuedfraction.continuedfraction.ContinuedFraction`
instances, where the integers represent the indices of the convergents.
If :math:`n` is the order of the continued fraction then only the even-
indexed convergents :math:`C_0, C_2, C_4, \\ldots` are generated.
Yields
------
tuple
A tuple of convergent index (:py:class:`int`) and convergents
(:py:class:`~continuedfractions.continuedfraction.ContinuedFraction`)
of the continued fraction.
Examples
--------
>>> tuple(ContinuedFraction('3.245').even_order_convergents)
((0, ContinuedFraction(3, 1)), (2, ContinuedFraction(159, 49)))
"""
yield from (t for t in self.convergents if not t[0] % 2)
@property
def odd_order_convergents(self) -> typing.Generator[tuple[int, ContinuedFraction], None, None]:
"""Generates an enumerated sequence of all odd-order convergents of the continued fraction.
The convergents are generated as tuples of :py:class:`int` and
:py:class:`~continuedfraction.continuedfraction.ContinuedFraction`
instances, where the integers represent the indices of the convergents.
If :math:`n` is the order of the continued fraction then only the odd-
indexed convergents :math:`C_1, C_3, C_5, \\ldots` are generated.
Yields
------
tuple
A tuple of convergent index (:py:class:`int`) and convergents
(:py:class:`~continuedfractions.continuedfraction.ContinuedFraction`)
of the continued fraction.
Examples
--------
>>> tuple(ContinuedFraction('3.245').odd_order_convergents)
((1, ContinuedFraction(13, 4)), (3, ContinuedFraction(649, 200)))
"""
yield from (t for t in self.convergents if t[0] % 2)
[docs]
def semiconvergent(self, k: int, m: int, /) -> ContinuedFraction:
"""Returns the :math:`m`-th semiconvergent of two consecutive convergents :math:`p_{k - 1}` and :math:`p_k` of the continued fraction.
The integer :math:`k` must be positive and determine two consecutive
convergents :math:`p_{k - 1}` and :math:`p_k` of a (finite, simple)
continued fraction.
The integer :math:`m` can be any positive integer.
Parameters
----------
k : int
The integer :math:`k` determining two consecutive convergents
:math:`p_{k - 1}` and :math:`p_k` of a (finite, simple) continued
fraction
:math:`[a_0; a_1, \\ldots, a_{k}, a_{k + 1}, \\ldots, a_n]`.
m : int
The index of the semiconvergent of the convergents
:math:`p_{k - 1}` and :math:`p_k`.
Returns
-------
ContinuedFraction
The :math:`m`-th semiconvergent of the convergents
:math:`p_{k - 1}` and :math:`p_k`.
Raises
------
ValueError
If :math:`k` or :math:`m` are not positive integers, or :math:`k`
is an integer that does **not** satisfy :math:`1 \\leq k \\leq n`
where :math:`n` is the order of the (finite, simple) continued
fraction of which :math:`p_{k - 1}` and :math:`p_k` are
convergents.
Examples
--------
>>> cf = ContinuedFraction(-415, 93)
>>> tuple(cf.coefficients)
(-5, 1, 1, 6, 7)
>>> tuple(cf.convergents)
((0, ContinuedFraction(-5, 1)), (1, ContinuedFraction(-4, 1)), (2, ContinuedFraction(-9, 2)), (3, ContinuedFraction(-58, 13)), (4, ContinuedFraction(-415, 93)))
>>> cf.semiconvergent(3, 1)
ContinuedFraction(-67, 15)
>>> cf.semiconvergent(3, 2)
ContinuedFraction(-125, 28)
>>> cf.semiconvergent(3, 3)
ContinuedFraction(-183, 41)
>>> cf.semiconvergent(3, 4)
ContinuedFraction(-241, 54)
>>> cf.semiconvergent(3, 5)
ContinuedFraction(-299, 67)
>>> cf.semiconvergent(3, 6)
ContinuedFraction(-357, 80)
>>> cf.semiconvergent(3, 7)
ContinuedFraction(-415, 93)
"""
if not isinstance(k, int) or k not in range(1, self.order + 1) or not isinstance(m, int) or m < 1:
raise ValueError(
"`k` and `m` must be positive integers and `k` must be an "
"integer in the range `1..n` where `n` is the order of the "
"continued fraction"
)
return self.convergent(k - 1).right_mediant(self.convergent(k), k=m)
[docs]
def remainder(self, k: int, /) -> ContinuedFraction:
"""Returns the :math:`k`-th remainder of the continued fraction.
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 result is a :py:class:`~continuedfractions.continuedfraction.ContinuedFraction` instance.
Parameters
----------
k : int
The index of the remainder, as described above.
Returns
-------
ContinuedFraction
A new :py:class:`ContinuedFraction` instance representing the :math:`k`-th
remainder of the original continued fraction, as described above.
Examples
--------
>>> cf = ContinuedFraction('.12345')
>>> cf
ContinuedFraction(2469, 20000)
>>> cf.remainder(0)
ContinuedFraction(2469, 20000)
>>> cf.remainder(2)
ContinuedFraction(2469, 248)
>>> cf.remainder(6)
ContinuedFraction(6, 5)
>>> cf.remainder(7)
ContinuedFraction(5, 1)
"""
return self.__class__(remainder(k, *self.coefficients))
@property
def remainders(self) -> typing.Generator[tuple[int, ContinuedFraction], None, None]:
"""Generates an enumerated sequence of all remainders of the continued fraction in descending order of index.
If :math:`n` is the order of the continued fraction then there are
:math:`n + 1` remainders :math:`R_0, R_1, \\ldots, R_n`, and the method
generates these in reverse order :math:`R_0, R_1, \\ldots, R_n`.
The remainders are generated as tuples of :py:class:`int`
and :py:class:`~continuedfraction.continuedfraction.ContinuedFraction`
instances, where the integers represent the indexes of the remainders.
Yields
------
tuple
A tuple of remainder indices (:py:class:`int`) and remainders
(:py:class:`~continuedfractions.continuedfraction.ContinuedFraction`)
of the continued fraction.
Examples
--------
>>> tuple(ContinuedFraction('3.245').remainders)
((3, ContinuedFraction(4, 1)), (2, ContinuedFraction(49, 4)), (1, ContinuedFraction(200, 49)), (0, ContinuedFraction(649, 200)))
>>> tuple(ContinuedFraction(-415, 93).remainders)
((4, ContinuedFraction(7, 1)), (3, ContinuedFraction(43, 7)), (2, ContinuedFraction(50, 43)), (1, ContinuedFraction(93, 50)), (0, ContinuedFraction(-415, 93)))
"""
coeffs = tuple(self.coefficients)
order = len(coeffs[1:])
yield from zip(
reversed(range(order + 1)),
map(self.__class__, remainders(*coeffs))
)
@property
def height(self) -> int:
""":py:class:`int` : The height of this rational number.
Returns
-------
int
The height of the fraction as a rational number represented by
homogeneous coordinates in projective space :math:`\\mathbb{P}^1(\\mathbb{Q})`.
Examples
--------
>>> ContinuedFraction(0, 1).height
1
>>> ContinuedFraction(-1, 2).height
2
>>> ContinuedFraction(3, -2).height
3
"""
return max(abs(self).as_integer_ratio())
@property
def log_height(self) -> Decimal:
""":py:class:`decimal.Decimal` : The (natural) logarithm of the height of this rational number as defined above.
Returns
-------
decimal.Decimal
The (natural) logarithm of the height of this fraction
as a rational number as defined above.
Examples
--------
>>> ContinuedFraction(0, 1).log_height
Decimal('0')
>>> ContinuedFraction(-1, 2).log_height
Decimal('0.69314718055994528622676398299518041312694549560546875')
>>> ContinuedFraction(3, -2).log_height
Decimal('1.0986122886681097821082175869378261268138885498046875')
"""
return Decimal(math.log(self.height))
def __add__(self, other, /):
return self.__class__(super().__add__(other))
def __radd__(self, other, /):
return self.__class__(super().__radd__(other))
def __sub__(self, other, /):
return self.__class__(super().__sub__(other))
def __rsub__(self, other, /):
return self.__class__(super().__rsub__(other))
def __mul__(self, other, /):
return self.__class__(super().__mul__(other))
def __rmul__(self, other, /):
return self.__class__(super().__rmul__(other))
def __truediv__(self, other, /):
return self.__class__(super().__truediv__(other))
def __rtruediv__(self, other, /):
return self.__class__(super().__rtruediv__(other))
def __floordiv__(self, other, /):
return self.__class__(super().__floordiv__(other))
def __rfloordiv__(self, other, /):
return self.__class__(super().__rfloordiv__(other))
def __divmod__(self, other, /):
quo, rem = super().__divmod__(other)
return self.__class__(quo), self.__class__(rem)
def __rdivmod__(self, other, /):
quo, rem = super().__rdivmod__(other)
return self.__class__(quo), self.__class__(rem)
def __pow__(self, other, /) -> ContinuedFraction:
return self.__class__(super().__pow__(other))
def __rpow__(self, other, /):
return self.__class__(Fraction(other).__rpow__(self))
def __pos__(self) -> ContinuedFraction:
return self.__class__(super().__pos__())
[docs]
def __neg__(self) -> ContinuedFraction:
"""
The negation algorithm for a finite simple continued fraction.
The basic algorithm can be described as follows: if
:math:`[a_0; a_1,\\ldots, a_n]` is the simple continued fraction of a
**positive** rational number :math:`\\frac{a}{b}` of finite order
:math:`n` then :math:`-\\frac{a}{b}` has the simple continued
fraction:
.. math::
\\begin{cases}
[-a_0;] \\hskip{3em} & n = 0 \\\\
[-(a_0 + 1); 2] \\hskip{3em} & n = 1 \\text{ and } a_1 = 2 \\\\
[-(a_0 + 1); a_2 + 1, a_3,\\ldots, a_n] \\hskip{3em} & n \\geq 2 \\text{ and } a_1 = 1 \\\\
[-(a_0 + 1); 1, a_1 - 1, a_2, \\ldots,a_n] \\hskip{3em} & n \\geq 2 \\text{ and } a_1 \\geq 2
\\end{cases}
In applying this algorithm there is an assumption that the last
coefficient :math:`a_n > 1`, as any simple continued fraction of type
:math:`[a_0; a_1,\\ldots, a_{n} = 1]` can be reduced to the simple
continued fraction :math:`[a_0; a_1,\\ldots, a_{n - 1} + 1]`.
"""
coeffs = tuple(self.coefficients)
n = len(coeffs)
if n == 1:
# Case (1) of the algorithm
neg_coeffs = (-coeffs[0],)
elif n == 2 and coeffs[1] == 2:
# Case (2) of the algorithm
neg_coeffs = (-(coeffs[0] + 1), 2)
elif n > 1 and coeffs[1] == 1:
# Case (3) of the algorithm
neg_coeffs = (-(coeffs[0] + 1), coeffs[2] + 1, *coeffs[3:])
else:
# Case (4) of the algorithm
neg_coeffs = (-(coeffs[0] + 1), 1, coeffs[1] - 1, *coeffs[2:])
neg_fraction = convergent(len(neg_coeffs) - 1, *neg_coeffs)
neg_self = self.__class__(1)
neg_self._numerator, neg_self._denominator = neg_fraction.as_integer_ratio()
return neg_self
def __abs__(self) -> ContinuedFraction:
return self.__class__(super().__abs__())
if __name__ == "__main__": # pragma: no cover
# Doctest the module from the project root using
#
# PYTHONPATH="src" python3 -m doctest -v src/continuedfractions/continuedfraction.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()
