Fraction fields

sign(a::QQFieldElem)

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

height(a::QQFieldElem)

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

height_bits(a::QQFieldElem)

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

<<(a::QQFieldElem, b::Int)

Return $a \times 2^b$.

>>(a::QQFieldElem, b::Int)

Return $a/2^b$.

floor(a::QQFieldElem)

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

ceil(a::QQFieldElem)

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

mod(a::QQFieldElem, b::ZZRingElem)
mod(a::QQFieldElem, b::Integer)

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

Examples

julia> mod(-ZZ(2)//3, 7)
4

julia> mod(ZZ(1)//2, ZZ(5))
3

reconstruct(a::ZZRingElem, m::ZZRingElem)
reconstruct(a::ZZRingElem, m::Integer)
reconstruct(a::Integer, m::ZZRingElem)
reconstruct(a::Integer, m::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

julia> a = reconstruct(7, 13)
1//2

julia> b = reconstruct(ZZ(15), 31)
-1//2

julia> c = reconstruct(ZZ(123), ZZ(237))
9//2

reconstruct(a::ZZRingElem, m::ZZRingElem, N::ZZRingElem, D::ZZRingElem)

Attempt to return a rational number $n/d$ such that $0 \leq |n| \leq N$ and $0 < d \leq D$ such that $2 N D < m$, gcd$(n, d) = 1$, and $a \equiv nd^{-1} \pmod{m}$.

Returns a tuple (success, n/d), where success signals the success of reconstruction.

next_minimal(a::QQFieldElem)

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 non-negative 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().

Examples

julia> next_minimal(ZZ(2)//3)
3//2

next_signed_minimal(a::QQFieldElem)

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.

Examples

julia> next_signed_minimal(-ZZ(21)//31)
31//21

next_calkin_wilf(a::QQFieldElem)

Return the next number after $a$ in the breadth-first traversal of the Calkin-Wilf tree. Starting with zero, this generates every non-negative 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.

Examples

julia> next_calkin_wilf(ZZ(321)//113)
113//244

next_signed_calkin_wilf(a::QQFieldElem)

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

julia> next_signed_calkin_wilf(-ZZ(51)//(17))
1//4

rand_bits(::QQField, 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.

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.

Examples

julia> a = harmonic(12)
86021//27720

bernoulli(n::Int)

Return the Bernoulli number $B_n$ for non-negative $n$.

See also bernoulli_cache.

Examples

julia> d = bernoulli(12)
-691//2730

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.

See also bernoulli.

Examples

julia> bernoulli_cache(100)

julia> e = bernoulli(100)
-94598037819122125295227433069493721872702841533066936133385696204311395415197247711//33330

dedekind_sum(h::ZZRingElem, k::ZZRingElem)

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

Examples

julia> b = dedekind_sum(12, 13)
-11//13

julia> c = dedekind_sum(-120, ZZ(1305))
-575//522

  simplest_between(l::QQFieldElem, r::QQFieldElem)

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

julia> simplest_between(QQ(1//10), QQ(3//10))
1//4