Skip to content

compose division ops for ContinuedFraction #66

@sr-murthy

Description

@sr-murthy

All division operations in ContinuedFraction:

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.

A new __invert__ operation is required for the composition, which implements the following algorithm for the inversion of a positive rational number $\frac{a}{b}$ with simple continued fraction $[a_0; a_1,\ldots, a_n]$: the positive inversion $+\frac{b}{a}$ is given by:

$$ +\frac{b}{a} = \begin{cases} [a_1; a_2,\ldots, a_n], \hskip{3em} & \text{if } 0 < a < b \iff a_0 = 0 \\ [0; a_0, a_1,\ldots, a_n], \hskip{3em} & \text{if } 0 < b < a \iff a_0 \geq 1 \end{cases} $$

This makes it possible to implement negative inversion $-\frac{b}{a}$ as the composition:

$$ -\frac{b}{a} = \frac{1}{-\frac{a}{b}} = -\left(\frac{1}{\frac{a}{b}}\right) = \begin{cases} [-1; a_0 - 1], \hskip{3em} & n = 0 \text{ and } a_0 \geq 1 \\ [-1; 1, a_0 - 1, 2], \hskip{3em} & n = 1 \text{ and } a_0 \geq 2 \\ [-1; 2, a_2, \ldots, a_n], \hskip{3em} & n \geq 2 \text{ and } a_0 = 1 \\ [-1; 1, a_0 - 1, 1, a_2, \ldots, a_n], \hskip{3em} & n \geq 2 \text{ and } a_0 > 1 \end{cases} $$

In applying this algorithm there is an assumption that the last element $a_n &gt; 1$, as any simple continued fraction of type $[a_0; a_1,\ldots, a_{n} = 1]$ can be reduced to the simple continued fraction $[a_0; a_1,\ldots, a_{n - 1} + 1]$.

Metadata

Metadata

Assignees

No one assigned

    Labels

    documentationImprovements or additions to documentationenhancementNew feature or requestrefactorRefactoring changes

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions