Metadata-Version: 2.4
Name: catena-scf
Version: 0.4.2
Summary: A Python library for simple continued fractions
Project-URL: Repository, https://github.com/LorenzoSilvaMoore/catena
Project-URL: Issues, https://github.com/LorenzoSilvaMoore/catena/issues
Project-URL: Documentation, https://lorenzosilvamoore.github.io/catena/
Author-email: Lorenzo Silva Moore <lorenzosilvamoore@ciencias.unam.mx>
License-Expression: GPL-3.0-or-later
License-File: LICENSE
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Requires-Python: >=3.12
Description-Content-Type: text/markdown

# catena

A pure-Python library for working with **simple continued fractions** (SCFs).

`catena` provides three main abstractions: a generative SCF driven by an
arbitrary callable, a finite SCF backed by a compact fixed sequence, and a
periodic SCF representing quadratic irrationals.  All three share a memoised
two-layer convergent engine with a full arithmetic interface — including
negation, subtraction, multiplication, division, equality, and hashing for
finite SCFs, and equality / hashing for periodic SCFs.  The `catena.numbers`
subpackage provides named mathematical constants (`e`, `φ`, `√2`, …) and
deterministic Gauss-Kuzmin random SCF generators backed by SHA-256.

The library has **zero dependencies** and requires Python ≥ 3.12.

A formal write-up of the theory and implementation decisions is available as a PDF:
**[catena — Architecture, Algorithm Decisions, and Formal Theory](https://lorenzosilvamoore.github.io/catena/catena-theory.pdf)**

The full API reference and usage examples are hosted at:
**[lorenzosilvamoore.github.io/catena](https://lorenzosilvamoore.github.io/catena/)**

---

## Mathematical background

A simple continued fraction expresses a number as

```
        1
a₀ + ─────────────
          1
     a₁ + ────────
               1
          a₂ + ───
               ⋱
```

written compactly as `[a₀; a₁, a₂, …]`, where `a₀` is any integer and
`a₁, a₂, …` are strictly positive integers.
When the sequence is finite the expression represents a rational number exactly.

Convergents are the rational approximations obtained by truncating the expansion:

```
pₙ/qₙ  =  [a₀; a₁, …, aₙ]
```

They satisfy the two-term recurrence

```
pₙ = aₙ·pₙ₋₁ + pₙ₋₂,   qₙ = aₙ·qₙ₋₁ + qₙ₋₂
```

and are the best rational approximations to the value being expanded.

---

## Why catena?

Existing Python libraries for continued fractions tend to focus on the finite,
rational case.  For example,
[`continuedfractions`](https://continuedfractions.readthedocs.io/) is a
well-designed object-oriented library that extends `fractions.Fraction` to cover
finite SCFs and related objects such as Farey sequences and mediants — but its
scope is explicitly limited to rationals.  Many other packages take an even more
procedural approach, exposing functions that operate on lists of coefficients
rather than first-class objects.

`catena` starts from the general, countably infinite definition.  A
`SimpleContinuedFraction` is driven by a generator callable that produces
partial quotients on demand — so an infinite expansion like `√2` or `e`
is represented by a small, fixed-size object regardless of how many convergents
you compute.  Convergents are memoised as they are requested; you pay only for
what you use, and the cache is shared transparently when the same tail is viewed
with a different integer part.

`catena` also does not subclass `fractions.Fraction`.  Convergents produced by
the two-term recurrence are guaranteed to be in lowest terms — consecutive
convergents satisfy `pₙ·qₙ₋₁ − pₙ₋₁·qₙ = ±1`, so `gcd(pₙ, qₙ) = 1`
always holds.  `fractions.Fraction` normalises every result through a GCD
reduction regardless, which means wrapping convergents in it would pay a cost
that buys nothing.  Instead, `catena` stores numerator/denominator pairs as
plain `(int, int)` tuples and implements only the arithmetic operations it
actually needs, with targeted GCD reductions where they are genuinely required
(e.g. when adding two finite SCFs).

The long-term goal is to build on this foundation a high-level API for concrete
applications of continued fraction theory.  The following are already
implemented or partially implemented:

- **Quadratic irrationals and periodic SCFs** — `PeriodicSimpleContinuedFraction`
  represents numbers of the form `(P + √D) / Q` as eventually-periodic
  expansions.  Provides `quadratic_surd()`, `conjugate()`, `inverse()`,
  `from_quadratic_surd()`, and `__float__` / `as_decimal()`.
- **Generator manipulation** — all four generator types support `advance(n)`,
  `insert(fg, at)`, and `prepend(fg)` for slicing, splicing, and reordering
  partial-quotient sequences.  `CachedGenerator` variants optionally copy and
  re-index the memoised cache across operations.
- **Full SCF arithmetic** — `FiniteSimpleContinuedFraction` supports `__neg__`,
  `__sub__`, `__mul__`, `__truediv__`, extended `__add__` (accepts `float`,
  `Fraction`, `Decimal`), `__eq__` (compares by exact rational value via
  `terminal_convergent`), and `__hash__`.  Periodic SCFs gain `__eq__` and
  `__hash__` via their `quadratic_surd()` triple.
- **Mathematical constants** — `catena.numbers.constants` provides ready-to-use
  SCF objects for `e`, `phi` (golden ratio), `sqrt2`, `sqrt3`, `sqrt5`, and a
  `metallic_mean(n)` factory for the entire metallic-mean family.
- **Deterministic random SCFs** — `catena.numbers.randoms` generates
  Gauss-Kuzmin-distributed partial quotients via a SHA-256 hash chain
  (`GaussKuzminSCF`, `GaussKuzminArbitrarySCF`).  A stateful `Seed` class
  ensures reproducibility and independence between successive callables.

Planned for future releases:

- **Best rational approximations** — direct extraction from the convergent sequence.
- **Pell's equation** — solutions via the periodic expansion of `√D`.
- **Farey sequences and mediants** — enumeration of rationals and their
  geometric interpretation as rational points in the plane.
- **Fibonacci-type sequences** — structural connections between convergents and
  linear recurrences.

---

## Installation

```bash
pip install catena-scf
```

The import name is `catena` (unchanged from the distribution name):

```python
import catena
```

**Development install** from the repository root:

```bash
pip install -e .
```

---

## Quick start

### Finite SCF from a rational number

```python
from catena import FiniteSimpleContinuedFraction

# 355/113  =  [3; 7, 16]
scf = FiniteSimpleContinuedFraction.from_rational((355, 113))

print(scf.integer_part)        # 3
print(scf.partial_quotients)   # (7, 16)
print(scf.terminal_convergent) # (355, 113)

# Successive convergents
scf.convergent(0)   # (22, 7)   — the classic 22/7 approximation
scf.convergent(1)   # (355, 113)
```

### Finite SCF from a float or decimal string

```python
import math

scf = FiniteSimpleContinuedFraction.from_float(math.pi, max_denominator=1000)
print(scf.terminal_convergent)   # (355, 113)

scf2 = FiniteSimpleContinuedFraction.from_decimal("3.14159265")
```

### Infinite (generative) SCF

```python
from catena import SimpleContinuedFraction

# Golden ratio  φ = [1; 1, 1, 1, ...]
phi = SimpleContinuedFraction(lambda n: 1, integer_part=1)

phi.tail_convergent(10)   # (89, 144) — consecutive Fibonacci numbers
phi.convergent(10)        # (233, 144)

# Shift the integer part without recomputing the cache
phi_shifted = phi + 2     # [3; 1, 1, 1, ...]  — shares phi's cache
```

### SCF arithmetic

```python
from catena import FiniteSimpleContinuedFraction

a = FiniteSimpleContinuedFraction.from_rational((1, 3))
b = FiniteSimpleContinuedFraction.from_rational((1, 6))

c = a + b                       # FiniteSimpleContinuedFraction for 1/2
c.terminal_convergent           # (1, 2)
float(c)                        # 0.5

# Multiplicative inverse
inv = a.inverse()               # FiniteSimpleContinuedFraction for 3/1
inv.terminal_convergent         # (3, 1)
inv.inverse() is a              # True — cached, returns original object
```

### Periodic SCF — quadratic irrationals

```python
from catena import PeriodicSimpleContinuedFraction

# √2 = [1; (2, 2, 2, ...)]
sqrt2 = PeriodicSimpleContinuedFraction(period=[2], integer_part=1)

float(sqrt2)                    # 1.4142135623730951
sqrt2.quadratic_coefficients()  # (1, 0, -2)  →  x² - 2 = 0
sqrt2.quadratic_surd()          # (0, 1, 2)   →  (0 + √2) / 1

conj = sqrt2.conjugate()        # the other root: -√2
float(conj)                     # -1.4142135623730951
conj.conjugate() is sqrt2       # True

inv = sqrt2.inverse()           # 1/√2 = [0; 1, (2)]
float(inv)                      # 0.7071067811865476

# Construct directly from surd parameters (P + √D) / Q
phi = PeriodicSimpleContinuedFraction.from_quadratic_surd(1, 2, 5)
float(phi)                      # 1.618033988749895
```

### Generator manipulation

```python
from catena.generators import FiniteGenerator

fg = FiniteGenerator([3, 1, 4, 1, 5, 9])

# advance: skip the first n terms
list(fg.advance(2))              # [4, 1, 5, 9]

# insert: splice another FiniteGenerator at the given position
patch = FiniteGenerator([7, 7])
list(fg.insert(patch, at=1))    # [3, 7, 7, 1, 4, 1, 5, 9]

# prepend: shorthand for insert at 0
list(fg.prepend(patch))         # [7, 7, 3, 1, 4, 1, 5, 9]
```

### SCF arithmetic

```python
from catena import FiniteSimpleContinuedFraction
from fractions import Fraction

a = FiniteSimpleContinuedFraction.from_rational((3, 4))
b = FiniteSimpleContinuedFraction.from_rational((1, 4))

(a - b).terminal_convergent     # (1, 2)
(a * b).terminal_convergent     # (3, 16)
(a / b).terminal_convergent     # (3, 1)

# Operations with plain numbers
(a + 0.5).terminal_convergent   # (5, 4)

# Equality and hashing
a == Fraction(3, 4)             # True
len({a, b, a})                  # 2  — deduplicated via __hash__
```

### Mathematical constants

```python
from catena.numbers import constants

float(constants.e)              # 2.718281828459045
float(constants.phi)            # 1.618033988749895
float(constants.sqrt2)          # 1.4142135623730951

# Metallic means  [n; (n)]
float(constants.metallic_mean(2))    # 2.414213562373095  (silver mean)
float(constants.metallic_mean(3))    # 3.302775637731995  (bronze mean)
```

### Deterministic random SCFs

```python
from catena.numbers.randoms import GaussKuzminSCF, Seed

seed = Seed("my-experiment")
rng  = GaussKuzminSCF(seed)

# Factory methods produce different SCF types
scf  = rng.scf(integer_part=1)          # SimpleContinuedFraction
fsf  = rng.finite_scf(size=10)          # FiniteSimpleContinuedFraction, 10 quotients
pscf = rng.periodic_scf(period_size=4)  # PeriodicSimpleContinuedFraction

# Each factory call advances the seed — successive objects are independent
str(seed)    # Seed(initial_state=my-experiment, step=3)
```

---

## Project structure

```
catena/
├── __init__.py          # Public exports
├── catena.py            # SimpleContinuedFraction, FiniteSimpleContinuedFraction,
│                        #   PeriodicSimpleContinuedFraction
├── generators.py        # Generator, CachedGenerator, FiniteGenerator, PeriodicGenerator
├── cache.py             # Cache, OrdinalCache, CacheHandler, SetCache, SetLightCache
├── strings.py           # safe_int_str, safe_full_int_str
├── mathlib/
│   ├── __init__.py      # Re-exports all submodules
│   ├── core.py          # Type aliases, get_sign, simplify, canonicalize, euclidean_step
│   ├── arithmetic.py    # add_fractions, multiply_fractions, square_fraction, sandwich_fraction
│   ├── convert.py       # from_rational_to_scf, from_float_to_*, from_decimal_to_rational,
│   │                    #   from_quadratic_surd_to_scf, from_quadratic_surd_to_conjugate_scf
│   ├── quadratic.py     # simplify/normalize_quadratic_surd, quadratic_roots/surd_from_coefficients
│   └── metric.py        # product_digit_count, average_digit_count
└── numbers/
    ├── __init__.py      # Re-exports constants and randoms submodules
    ├── constants.py     # e, phi, sqrt2, sqrt3, sqrt5, metallic_mean(n)
    └── randoms.py       # Seed, GaussKuzminSHA, UniformSHAArbitrary,
                         #   GaussKuzminSHAArbitrary, RandomSCF,
                         #   GaussKuzminSCF, GaussKuzminArbitrarySCF

testing/
├── conftest.py                  # Session fixtures, large-integer store management
├── bigints.py                   # Deterministic large-integer generation and binary store
├── test_scf.py                  # SimpleContinuedFraction tests
├── test_finite_scf.py           # FiniteSimpleContinuedFraction tests
├── test_periodic_scf.py         # PeriodicSimpleContinuedFraction tests
├── test_generators.py           # Generator / CachedGenerator / FiniteGenerator / PeriodicGenerator tests
├── test_cache.py                # Cache / OrdinalCache / CacheHandler / SetCache tests
├── test_math_core.py            # mathlib.core tests
├── test_math_arithmetic.py      # mathlib.arithmetic tests
├── test_math_quadratic.py       # mathlib.quadratic + convert surd helpers tests
├── test_math_metric.py          # mathlib.metric tests
├── test_strings.py              # strings tests
├── test_numbers_constants.py    # catena.numbers.constants tests
└── test_numbers_randoms.py      # catena.numbers.randoms tests
```

---

## API reference

### `catena.catena`

#### `SimpleContinuedFraction`

Represents an infinite SCF $[a_0;\, a_1, a_2, \ldots]$ driven by a callable generator.

```python
SimpleContinuedFraction(generator, integer_part=0)
```

| Member | Description |
|--------|-------------|
| `integer_part` | $a_0$; readable and writable |
| `generator` | The underlying `Generator` instance |
| `cache_handler` | `CacheHandler` managing the memoised convergents |
| `tail_convergent(n)` | $(h_n, k_n)$ for the tail $[a_1;\ldots,a_{n+1}]$; memoised |
| `convergent(n)` | $(a_0 k_n + h_n,\; k_n)$ — the full $n$-th convergent |
| `shift(n)` | New SCF with `integer_part + n`, sharing the same cache |
| `tail()` | New SCF with `integer_part = 0`, sharing the same generator and cache |
| `inverse()` | Multiplicative inverse $1/x$; result cached write-once in `_inverse` |
| `scf + k` / `k + scf` | Integer shift (delegates to `shift`) |
| `-scf` | Additive inverse; returns a new SCF of the same type |
| `repr(scf)` | Detailed string including `generator`, `integer_part`, and `cache_handler` |

The attributes `_generator`, `_cache_handler`, and `tail_convergent` are frozen
after construction; any attempt to reassign them raises `AttributeError`.
`_inverse` is write-once: set by the first call to `inverse()` and immutable
thereafter.

#### `FiniteSimpleContinuedFraction`

Extends `SimpleContinuedFraction` with a fixed, indexable tail.

```python
FiniteSimpleContinuedFraction(partial_quotients, integer_part=0, dtype=None)
```

| Member | Description |
|--------|-------------|
| `partial_quotients` | Tail as an immutable tuple (materialises the full sequence) |
| `size` / `len(scf)` | Number of partial quotients |
| `terminal_convergent` | Last convergent — exact rational value of the SCF |
| `terminal_tail_convergent` | Last tail convergent |
| `to_decimal()` | Exact value as `decimal.Decimal` |
| `inverse()` | Multiplicative inverse; raises `ZeroDivisionError` for the zero value |
| `float(scf)` | Terminal convergent as Python `float` |
| `int(scf)` | `integer_part` |
| `bool(scf)` | `False` only when `integer_part == 0` and the tail is empty |
| `-scf` | Additive inverse |
| `scf + other` | Addition; `other` may be `FiniteSimpleContinuedFraction`, `int`, `float`, `Fraction`, or `Decimal` |
| `scf - other` | Subtraction; same type support as `__add__` |
| `scf * other` | Multiplication; same type support |
| `scf / other` | Division; same type support |
| `scf == other` | Equality by `terminal_convergent`; also handles `int`, `float`, `Fraction` |
| `hash(scf)` | Consistent with `__eq__`; instances usable as dict keys and in sets |

**Factory class methods:**

| Method | Input |
|--------|-------|
| `from_rational(r)` | `Fraction`, `(p, q)` tuple, or `int` |
| `from_float(f, max_denominator=None)` | Python `float` |
| `from_decimal(d)` | Finite decimal string, e.g. `"3.14"` |

---

#### `PeriodicSimpleContinuedFraction`

Represents an eventually-periodic SCF $[a_0;\, a_1, \ldots, a_k,\, \overline{b_1, \ldots, b_m}]$
corresponding to a quadratic irrational $(P + \sqrt{D})/Q$.

```python
PeriodicSimpleContinuedFraction(period, integer_part=0, pre_period=())
```

The `period` is a non-empty tuple of strictly positive integers; `pre_period`
(if given) is the finite non-repeating tail $[a_1, \ldots, a_k]$.

| Member | Description |
|--------|-------------|
| `period` | Repeating part as an immutable tuple |
| `pre_period` | Non-repeating tail prefix (empty tuple if purely periodic) |
| `quadratic_surd()` | Returns `(P, Q, D)` such that the SCF represents $(P + \sqrt{D})/Q$ |
| `quadratic_coefficients()` | Minimal polynomial coefficients $(A, B, C)$ with $Ax^2 + Bx + C = 0$ |
| `is_principal_surd()` | `True` when the surd satisfies $0 < x$ and $-1 < x' < 0$ (principal / reduced) |
| `is_conjugate_root()` | `True` when the surd is the conjugate of a principal surd |
| `conjugate()` | The conjugate surd $\hat{x} = (P - \sqrt{D})/Q$; result cached write-once |
| `inverse()` | Multiplicative inverse $1/x$; result cached write-once |
| `from_quadratic_surd(P, Q, D)` | Class method — construct from surd parameters directly |
| `float(scf)` | Decimal approximation via `as_decimal()` (50 significant digits by default) |
| `as_decimal(n_digits)` | Arbitrarily precise `Decimal` value |
| `-scf` | Negation; returns a new `PeriodicSimpleContinuedFraction` for $-x$ |
| `scf == other` | Equality by `quadratic_surd()` triple; only defined for two `PeriodicSimpleContinuedFraction` instances |
| `hash(scf)` | Consistent with `__eq__`; instances usable as dict keys and in sets |

Key attributes (`_conjugate`, `_inverse`, `_quadratic_surd`, `_quadratic_coefficients`)
are write-once: computed on first access and frozen thereafter.

### `catena.generators`

| Class | Description |
|-------|-------------|
| `Generator(f)` | Validates that `f(n)` always returns a strictly positive `int`; avoids double-wrapping |
| `CachedGenerator(f)` | Like `Generator` but memoises results in an `OrdinalCache` |
| `FiniteGenerator(data, dtype=None)` | Fixed sequence; auto-selects the smallest unsigned `array` typecode (`B`/`H`/`I`/`L`/`Q`); falls back to `tuple` for values exceeding 64-bit range |
| `PeriodicGenerator(period, pre_period=())` | Repeating sequence; delegates to `FiniteGenerator` for each segment |

All four types share the following manipulation methods:

| Method | Description |
|--------|-------------|
| `advance(n)` | Returns a new generator whose *k*-th term equals the original's *(n+k)*-th term |
| `insert(fg, at)` | Splices a `FiniteGenerator` into the sequence at the given index |
| `prepend(fg)` | Shorthand for `insert(fg, at=0)` |

`CachedGenerator.advance` and `CachedGenerator.insert` accept an additional
`copy_cache=False` keyword; when `True`, eligible memoised values are copied
and re-indexed into the new generator.

---

### `catena.numbers`

#### `catena.numbers.constants`

Module-level SCF instances for standard mathematical constants.

| Name | Type | Value |
|------|------|-------|
| `e` | `SimpleContinuedFraction` | Euler's number $[2;\, 1, 2, 1, 1, 4, 1, 1, 6, \ldots]$ |
| `phi` | `PeriodicSimpleContinuedFraction` | Golden ratio $[1;\, \overline{1}]$ |
| `sqrt2` | `PeriodicSimpleContinuedFraction` | $[1;\, \overline{2}]$ |
| `sqrt3` | `PeriodicSimpleContinuedFraction` | $[1;\, \overline{1, 2}]$ |
| `sqrt5` | `PeriodicSimpleContinuedFraction` | $[2;\, \overline{4}]$ |
| `metallic_mean(n)` | `PeriodicSimpleContinuedFraction` | $[n;\, \overline{n}]$; satisfies $x^2 - nx - 1 = 0$ |

#### `catena.numbers.randoms`

Deterministic pseudo-random SCF generation via the Gauss-Kuzmin distribution.

| Symbol | Description |
|--------|-------------|
| `Seed(initial_state=None)` | Stateful SHA-256 chain dispenser; each access to `.state` returns the current bytes and advances the chain; `.step` counts accesses; `str(seed)` decodes the original `initial_state` |
| `GaussKuzminSHA(seed)` | Callable — 53-bit SHA-256 uniform → $\lfloor 1/(2^u - 1) \rfloor$; O(1) per call, deterministic by index |
| `UniformSHAArbitrary(precision)` | Callable — multi-round SHA-256 chain → `Decimal` uniform in $[0, 1)$ with `precision` significant digits |
| `GaussKuzminSHAArbitrary(seed, precision)` | Callable — arbitrary-precision Gauss-Kuzmin built on `UniformSHAArbitrary`; `precision` defaults to 50 |
| `RandomSCF` | ABC; concrete subclasses implement `__make_callable__()`; exposes `generator()`, `cached_generator()`, `finite_generator(size)`, `periodic_generator(period_size, pre_period_size)`, `scf()`, `finite_scf()`, `periodic_scf()` |
| `GaussKuzminSCF(seed=None)` | `RandomSCF` backed by `GaussKuzminSHA`; each factory call consumes one `Seed.state` step |
| `GaussKuzminArbitrarySCF(precision=50, seed=None)` | `RandomSCF` backed by `GaussKuzminSHAArbitrary` |

---

### `catena.cache`

`functools.lru_cache` / `functools.cache` bind the cache to a single function
with no public API to extract or share the underlying store.  `catena` needs
the cache to be an explicit, first-class object for three reasons:

- **Shareability.**  Two SCF instances with the same tail (e.g. `phi` and
  `phi + 2` after an integer shift) should share a single convergent cache.
  The same applies to an expensive recursive generator used by several SCFs —
  the computation should be paid once, not once per instance.
- **Pruning.**  `CacheHandler.prune_cache(n)` drops all entries below index
  `n`, letting callers free memory mid-computation without discarding the
  handler or its references.
- **Coherent reset.**  `CacheHandler.reset_cache()` clears the store while
  keeping the same handler object alive.  Because every SCF that shares a tail
  holds a reference to the same `CacheHandler`, a single reset is visible to
  all of them simultaneously — something that is impossible when the cache is
  private to each decorated function.

`CacheHandler` owns the underlying store and exposes it; `SetLightCache` and
`SetCache` are thin wrappers that delegate to it.

| Symbol | Description |
|--------|-------------|
| `Cache` | Append-only `UserDict`; raises `KeyError` if an existing key is overwritten |
| `OrdinalCache` | `Cache` restricted to integer keys; tracks `smallest_key` and `largest_key` |
| `CacheHandler` | Owns a `Cache`; records `call_count` (misses) and `read_count` (hits); supports `reset_cache()` and `prune_cache(n)` |
| `SetCache(func, cache_handler)` | Decorator/factory; keys by `(args, frozenset(kwargs))` |
| `SetLightCache(func, cache_handler)` | Lightweight variant for single-argument callables; keys by the argument directly |

---

### `catena.mathlib`

#### `core`

| Function | Description |
|----------|-------------|
| `get_sign(n)` | `1`, `-1`, or `0` |
| `simplify(p, q)` | Reduce fraction by $\gcd$; preserves signs |
| `canonicalize(p, q)` | `simplify` + ensure denominator is positive |
| `euclidean_step(p, q)` | Returns `(p//q, p%q, q)` — one step of the Euclidean algorithm |
| `quotent_sign(p, q)` | Sign of $p/q$ without division; `None` if $q = 0$ |

Type aliases: `IntPair = tuple[int, int]`, `IntTriplet = tuple[int, int, int]`.

#### `arithmetic`

| Function | Description |
|----------|-------------|
| `add_fractions(a, b)` | $a + b$ with GCD-based intermediate reduction |
| `multiply_fractions(a, b)` | $a \times b$ with cross-GCD reduction |
| `square_fraction(a)` | $a^2$ |
| `sandwich_fraction(a, b)` | $(p/q) \text{ sandwich } (r/s) = (ps, qr)$ |

Each function has an `u`-prefixed unpacked variant (e.g. `uadd_fractions(p, q, r, s)`) to avoid tuple construction overhead in hot paths.

#### `convert`

| Function | Description |
|----------|-------------|
| `from_rational_to_scf(r)` | `Rational` → `(a0, [a1, …])` via Euclidean algorithm |
| `from_float_to_rational(f, limit_denominator)` | `float` → `(p, q)` via `fractions.Fraction` |
| `from_float_to_scf(f, limit_denominator)` | Chains the two above |
| `from_decimal_to_rational(d)` | Finite decimal string → exact `(p, q)` in lowest terms |
| `from_quadratic_surd_to_scf(P, Q, D)` | $(P + \sqrt{D})/Q$ → `(a0, period, pre_period)` via integer-only Euclidean expansion |
| `from_quadratic_surd_to_conjugate_scf(P, Q, D)` | Conjugate surd $(-P + \sqrt{D})/(-Q)$ → same output format |

`Rational` alias: `Fraction | tuple[int, int] | int`.

#### `quadratic`

Pure-integer helpers for quadratic surds $(P + \sqrt{D})/Q$.

| Function | Description |
|----------|-------------|
| `simplify_quadratic_surd(P, Q, D)` | Divides $P$, $Q$ by $\gcd(P, Q)$ where the same factor divides $D$; returns `(P, Q, D)` |
| `normalize_quadratic_surd(P, Q, D)` | Full normalisation: simplify + ensure $Q > 0$ |
| `quadratic_roots_from_coefficients(A, B, C)` | Both roots of $Ax^2 + Bx + C = 0$ as `(P, Q, D)` pairs |
| `quadratic_surd_from_coefficients(A, B, C)` | The larger root of $Ax^2 + Bx + C = 0$ as a `(P, Q, D)` surd |

#### `metric`

| Function | Description |
|----------|-------------|
| `product_digit_count(arr)` | Total decimal digit count of $\prod arr$ (log-sum, no actual multiplication) |
| `product_digit_count_high_precision(arr)` | Same via `Decimal` for higher accuracy |
| `average_digit_count(arr)` | `product_digit_count(arr) / len(arr)` |

---

### `catena.strings`

| Function | Description |
|----------|-------------|
| `safe_int_str(n, n_trailing=99)` | Abbreviated repr for large integers, avoiding PEP 678 conversion limits |
| `safe_full_int_str(n)` | Full decimal string of arbitrarily large integers via chunked conversion |

---

## Design notes

**Zero dependencies.**  The library is pure Python and relies only on the
standard library (`fractions`, `decimal`, `array`, `collections`, `math`).

**Immutability by default.**  Core attributes of `SimpleContinuedFraction`,
`CacheHandler`, and related classes are frozen after construction.  Mutations
raise `AttributeError` early rather than silently producing wrong results.

**Two-layer convergent computation.**  `tail_convergent` computes the
recurrence for the tail $[a_1; a_2, \ldots]$ independently of $a_0$.  This
allows `shift` and integer addition to create new SCF views sharing a fully
populated cache without recomputation.  For periodic SCFs the same tail is
shared between an instance and its `inverse()` / `conjugate()` counterparts.

**Write-once inverse and conjugate.**  The first call to `inverse()` or
`conjugate()` on a `SimpleContinuedFraction` or `PeriodicSimpleContinuedFraction`
stores the result in a frozen attribute.  Subsequent calls return the cached
object directly, and the double-inverse / double-conjugate identity `x.inv().inv() is x`
holds by construction.

**Compact storage.**  `FiniteGenerator` automatically selects the smallest
unsigned `array.array` typecode that covers the value range, falling back to
a plain `tuple` only when values exceed the 64-bit ceiling.

---

## Running the tests

```bash
pytest testing/
```

The test suite uses a binary large-integer store (`testing/store/`) for
expensive pre-computed values.  It is rebuilt automatically when
`conftest._PRECOMPUTED` changes.

---

## Contributing

Contributions are welcome.  See [CONTRIBUTING.md](CONTRIBUTING.md) for
guidelines on setting up the development environment, running the test suite,
and the conventions used across the project.

---

## License

GPL-3.0-or-later
