# Fraction fields

Nemo allows the creation of fraction fields over any ring $R$. We don't require $R$ to be an integral domain, however no attempt is made to deal with the general case. Two fractions $a/b$ and $c/d$ are equal in Nemo iff $ad = bc$. Thus, in practice, a greatest common divisor function is currently required for the ring $R$.

In order to make the representation $a/b$ unique for printing, we have a notion of canonical unit for elements of a ring $R$. When canonicalising $a/b$, each of the elements $a$ and $b$ is first divided by the canonical unit of $b$.

The `canonical_unit`

function is defined for elements of every Nemo ring. It must have the properties

```
canonical_unit(u) == u
canonical_unit(a*b) == canonical_unit(a)*canonical_unit(b)
```

for any unit $u$ of the ring in question, and $a$ and $b$ arbitrary elements of the ring.

For example, the canonical unit of an integer is its sign. Thus a fraction of integers always has positive denominator after canonicalisation.

The canonical unit of a polynomial is the canonical unit of its leading coefficient, etc.

There are two different kinds of implementation of fraction fields in Nemo: a generic one for the case where no specific implementation exists (provided by AbstractAlgebra.jl), and efficient implementations of fractions over specific rings, usually provided by C/C++ libraries.

The following table shows each of the fraction types available in Nemo, the base ring $R$, and the Julia/Nemo types for that kind of fraction (the type information is mainly of concern to developers).

Base ring | Library | Element type | Parent type |
---|---|---|---|

Generic ring $R$ | AbstractAlgebra.jl | `Generic.Frac{T}` | `Generic.FracField{T}` |

$\mathbb{Z}$ | Flint | `fmpq` | `FlintRationalField` |

All fraction element types belong to the abstract type `FracElem`

and all of the fraction field types belong to the abstract type `FracField`

. This enables one to write generic functions that can accept any Nemo fraction type.

## Fraction functionality

All fraction types in Nemo provide functionality for fields described in AbstractAlgebra.jl:

https://nemocas.github.io/AbstractAlgebra.jl/stable/field

In addition all the fraction field functionality of AbstractAlgebra.jl is provided, along with generic fractions fields as described here:

https://nemocas.github.io/AbstractAlgebra.jl/stable/fraction

### Basic manipulation

`Base.sign`

— Method`sign(a::fmpq)`

Return the sign of $a$ ($-1$, $0$ or $1$) as a fraction.

`Nemo.height`

— Method`height(a::fmpq)`

Return the height of the fraction $a$, namely the largest of the absolute values of the numerator and denominator.

`Nemo.height_bits`

— Method`height_bits(a::fmpq)`

Return the number of bits of the height of the fraction $a$.

`Base.:<<`

— Method`<<(a::fmpq, b::Int)`

Return $a \times 2^b$.

`Base.:>>`

— Method`>>(a::fmpq, b::Int)`

Return $a/2^b$.

`Base.floor`

— Method`floor(a::fmpq)`

Return the greatest integer that is less than or equal to $a$. The result is returned as a rational with denominator $1$.

`Base.ceil`

— Method`ceil(a::fmpq)`

Return the least integer that is greater than or equal to $a$. The result is returned as a rational with denominator $1$.

**Examples**

```
d = abs(ZZ(11)//3)
4 <= ZZ(7)//ZZ(3)
```

### Modular arithmetic

The following functions are available for rationals.

`Base.mod`

— Method`mod(a::fmpq, b::fmpz)`

Return $a \pmod{b}$ where $b$ is an integer coprime to the denominator of $a$.

`Base.mod`

— Method`mod(a::fmpq, b::Integer)`

Return $a \pmod{b}$ where $b$ is an integer coprime to the denominator of $a$.

**Examples**

```
a = -fmpz(2)//3
b = fmpz(1)//2
c = mod(a, 7)
d = mod(b, fmpz(5))
```

### Rational Reconstruction

Rational reconstruction is available for rational numbers.

`Nemo.reconstruct`

— Method`reconstruct(a::fmpz, b::fmpz)`

Attempt to return a rational number $n/d$ such that $0 \leq |n| \leq \lfloor\sqrt{m/2}\rfloor$ and $0 < d \leq \lfloor\sqrt{m/2}\rfloor$ such that gcd$(n, d) = 1$ and $a \equiv nd^{-1} \pmod{m}$. If no solution exists, an exception is thrown.

`Nemo.reconstruct`

— Method`reconstruct(a::fmpz, b::Integer)`

Attempt to return a rational number $n/d$ such that $0 \leq |n| \leq \lfloor\sqrt{m/2}\rfloor$ and $0 < d \leq \lfloor\sqrt{m/2}\rfloor$ such that gcd$(n, d) = 1$ and $a \equiv nd^{-1} \pmod{m}$. If no solution exists, an exception is thrown.

`Nemo.reconstruct`

— Method`reconstruct(a::Integer, b::fmpz)`

Attempt to find a rational number $n/d$ such that $0 \leq |n| \leq \lfloor\sqrt{m/2}\rfloor$ and $0 < d \leq \lfloor\sqrt{m/2}\rfloor$ such that gcd$(n, d) = 1$ and $a \equiv nd^{-1} \pmod{m}$. If no solution exists, an exception is thrown.

`Nemo.reconstruct`

— Method`reconstruct(a::Integer, b::Integer)`

Attempt to return a rational number $n/d$ such that $0 \leq |n| \leq \lfloor\sqrt{m/2}\rfloor$ and $0 < d \leq \lfloor\sqrt{m/2}\rfloor$ such that gcd$(n, d) = 1$ and $a \equiv nd^{-1} \pmod{m}$. If no solution exists, an exception is thrown.

**Examples**

```
a = reconstruct(7, 13)
b = reconstruct(fmpz(15), 31)
c = reconstruct(fmpz(123), fmpz(237))
```

## Rational enumeration

Various methods exist to enumerate rationals.

`Nemo.next_minimal`

— Method`next_minimal(a::fmpq)`

Given $a$, return the next rational number in the sequence obtained by enumerating all positive denominators $q$, and for each $q$ enumerating the numerators $1 \le p < q$ in order and generating both $p/q$ and $q/p$, but skipping all gcd$(p,q) \neq 1$. Starting with zero, this generates every nonnegative rational number once and only once, with the first few entries being $0, 1, 1/2, 2, 1/3, 3, 2/3, 3/2, 1/4, 4, 3/4, 4/3, \ldots$. This enumeration produces the rational numbers in order of minimal height. It has the disadvantage of being somewhat slower to compute than the Calkin-Wilf enumeration. If $a < 0$ we throw a `DomainError()`

.

`Nemo.next_signed_minimal`

— Method`next_signed_minimal(a::fmpq)`

Given a signed rational number $a$ assumed to be in canonical form, return the next element in the minimal-height sequence generated by `next_minimal`

but with negative numbers interleaved. The sequence begins $0, 1, -1, 1/2, -1/2, 2, -2, 1/3, -1/3, \ldots$. Starting with zero, this generates every rational number once and only once, in order of minimal height.

`Nemo.next_calkin_wilf`

— Method`next_calkin_wilf(a::fmpq)`

Return the next number after $a$ in the breadth-first traversal of the Calkin-Wilf tree. Starting with zero, this generates every nonnegative rational number once and only once, with the first few entries being $0, 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, \ldots$. Despite the appearance of the initial entries, the Calkin-Wilf enumeration does not produce the rational numbers in order of height: some small fractions will appear late in the sequence. This order has the advantage of being faster to produce than the minimal-height order.

`Nemo.next_signed_calkin_wilf`

— Method`next_signed_calkin_wilf(a::fmpq)`

Given a signed rational number $a$ returns the next element in the Calkin-Wilf sequence with negative numbers interleaved. The sequence begins $0, 1, -1, 1/2, -1/2, 2, -2, 1/3, -1/3, \ldots$. Starting with zero, this generates every rational number once and only once, but not in order of minimal height.

**Examples**

```
next_minimal(fmpz(2)//3)
next_signed_minimal(-fmpz(21)//31)
next_calkin_wilf(fmpz(321)//113)
next_signed_calkin_wilf(-fmpz(51)//(17))
```

### Random generation

`Nemo.rand_bits`

— Method`rand_bits(::FlintRationalField, b::Int)`

Return a random signed rational whose numerator and denominator both have $b$ bits before canonicalisation. Note that the resulting numerator and denominator can be smaller than $b$ bits.

### Special functions

The following special functions are available for specific rings in Nemo.

`Nemo.harmonic`

— Method`harmonic(n::Int)`

Return the harmonic number $H_n = 1 + 1/2 + 1/3 + \cdots + 1/n$. Table lookup is used for $H_n$ whose numerator and denominator fit in a single limb. For larger $n$, a divide and conquer strategy is used.

`Nemo.bernoulli`

— Method`bernoulli(n::Int)`

Return the Bernoulli number $B_n$ for nonnegative $n$.

`Nemo.bernoulli_cache`

— Method`bernoulli_cache(n::Int)`

Precomputes and caches all the Bernoulli numbers up to $B_n$. This is much faster than repeatedly calling `bernoulli(k)`

. Once cached, subsequent calls to `bernoulli(k)`

for any $k \le n$ will read from the cache, making them virtually free.

`Nemo.dedekind_sum`

— Method`dedekind_sum(h::fmpz, k::fmpz)`

Return the Dedekind sum $s(h,k)$ for arbitrary $h$ and $k$.

**Examples**

```
a = harmonic(12)
b = dedekind_sum(12, 13)
c = dedekind_sum(-120, fmpz(1305))
d = bernoulli(12)
bernoulli_cache(100)
e = bernoulli(100)
```

`Nemo.simplest_between`

— Method` simplest_between(l::fmpq, r::fmpq)`

Return the simplest fraction in the closed interval $[l, r]$. A canonical fraction $a_1 / b_1$ is defined to be simpler than $a_2 / b_2$ if and only if $b_1 < b_2$ or $b_1 = b_2$ and $a_1 < a_2$.

**Examples**

`simplest_between(fmpq(1//10), fmpq(3//10))`