Fixed precision real balls

Fixed precision real ball arithmetic is supplied by Arb which provides a ball representation which tracks error bounds rigorously. Real numbers are represented in mid-rad interval form $[m \pm r] = [m-r, m+r]$.

The Arb real field is constructed using the ArbField constructor. This constructs the parent object for the Arb real field.

The types of real balls in Nemo are given in the following table, along with the libraries that provide them and the associated types of the parent objects.

LibraryFieldElement typeParent type
Arb$\mathbb{R}$ (balls)ArbFieldElemArbField

All the real field types belong to the Field abstract type and the types of elements in this field, i.e. balls in this case, belong to the FieldElem abstract type.

Real ball functionality

Real balls in Nemo provide all the field functionality described in AbstractAlgebra:

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

Below, we document the additional functionality provided for real balls.

Constructors

In order to construct real balls in Nemo, one must first construct the Arb real field itself. This is accomplished with the following constructor.

ArbField(prec::Int)

Return the Arb field with precision in bits prec used for operations on interval midpoints. The precision used for interval radii is a fixed implementation-defined constant (30 bits).

Here is an example of creating an Arb real field and using the resulting parent object to coerce values into the resulting field.

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> a = RR("0.25")
0.25000000000000000000

julia> b = RR("0.1 +/- 0.001")
[0.1 +/- 1.01e-3]

julia> c = RR(0.5)
0.50000000000000000000

julia> d = RR(12)
12.000000000000000000

Note that whilst one can coerce double precision floating point values into an Arb real field, unless those values can be represented exactly in double precision the resulting ball can't be any more precise than the double precision supplied.

If instead, values can be represented precisely using decimal arithmetic then one can supply them to Arb using a string. In this case, Arb will store them to the precision specified when creating the Arb field.

If the values can be stored precisely as a binary floating point number, Arb will store the values exactly. See the function is_exact below for more information.

Real ball constructors

ballMethod
ball(x::ArbFieldElem, y::ArbFieldElem)

Constructs an Arb ball enclosing $x_m \pm (|x_r| + |y_m| + |y_r|)$, given the pair $(x, y) = (x_m \pm x_r, y_m \pm y_r)$.

source

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> c = ball(RR(3), RR("0.0001"))
[3.000 +/- 1.01e-4]

Conversions

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> convert(Float64, RR(1//3))
0.3333333333333333

Basic manipulation

is_nonzeroMethod
is_nonzero(x::ArbFieldElem)

Return true if $x$ is certainly not equal to zero, otherwise return false.

source
isfiniteMethod
isfinite(x::ArbFieldElem)

Return true if $x$ is finite, i.e. having finite midpoint and radius, otherwise return false.

source
is_exactMethod
is_exact(x::ArbFieldElem)

Return true if $x$ is exact, i.e. has zero radius, otherwise return false.

source
isintegerMethod
isinteger(x::ArbFieldElem)

Return true if $x$ is an exact integer, otherwise return false.

source
is_positiveMethod
is_positive(x::ArbFieldElem)

Return true if $x$ is certainly positive, otherwise return false.

source
is_nonnegativeMethod
is_nonnegative(x::ArbFieldElem)

Return true if $x$ is certainly non-negative, otherwise return false.

source
is_negativeMethod
is_negative(x::ArbFieldElem)

Return true if $x$ is certainly negative, otherwise return false.

source
is_nonpositiveMethod
is_nonpositive(x::ArbFieldElem)

Return true if $x$ is certainly nonpositive, otherwise return false.

source
midpointMethod
midpoint(x::ArbFieldElem)

Return the midpoint of the ball $x$ as an Arb ball.

source
radiusMethod
radius(x::ArbFieldElem)

Return the radius of the ball $x$ as an Arb ball.

source
accuracy_bitsMethod
accuracy_bits(x::ArbFieldElem)

Return the relative accuracy of $x$ measured in bits, capped between typemax(Int) and -typemax(Int).

source

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> a = RR("1.2 +/- 0.001")
[1.20 +/- 1.01e-3]

julia> b = RR(3)
3.0000000000000000000

julia> is_positive(a)
true

julia> isfinite(b)
true

julia> isinteger(b)
true

julia> is_negative(a)
false

julia> c = radius(a)
[0.0010000000038417056203 +/- 1.12e-23]

julia> d = midpoint(b)
3.0000000000000000000

julia> f = accuracy_bits(a)
9

Printing

Printing real balls can at first sight be confusing. Lets look at the following example:

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> a = RR(1)
1.0000000000000000000

julia> b = RR(2)
2.0000000000000000000

julia> c = RR(12)
12.000000000000000000

julia> x = ball(a, b)
[+/- 3.01]

julia> y = ball(c, b)
[1e+1 +/- 4.01]

julia> mid = midpoint(x)
1.0000000000000000000

julia> rad = radius(x)
[2.0000000037252902985 +/- 3.81e-20]

julia> print(x, "\n", y, "\n", mid, "\n", rad)
[+/- 3.01]
[1e+1 +/- 4.01]
1.0000000000000000000
[2.0000000037252902985 +/- 3.81e-20]

The first reason that c is not printed as [1 +/- 2] is that the midpoint does not have a greater exponent than the radius in its scientific notation. For similar reasons y is not printed as [12 +/- 2].

The second reason is that we get an additional error term after our addition. As we see, radius(c) is not equal to $2$, which when printed rounds it up to a reasonable decimal place. This is because real balls keep track of rounding errors of basic arithmetic.

Containment

It is often necessary to determine whether a given exact value or ball is contained in a given real ball or whether two balls overlap. The following functions are provided for this purpose.

overlapsMethod
overlaps(x::ArbFieldElem, y::ArbFieldElem)

Returns true if any part of the ball $x$ overlaps any part of the ball $y$, otherwise return false.

source
containsMethod
contains(x::ArbFieldElem, y::ArbFieldElem)

Returns true if the ball $x$ contains the ball $y$, otherwise return false.

source
containsMethod
contains(x::ArbFieldElem, y::Integer)

Returns true if the ball $x$ contains the given integer value, otherwise return false.

source
containsMethod
contains(x::ArbFieldElem, y::ZZRingElem)

Returns true if the ball $x$ contains the given integer value, otherwise return false.

source
containsMethod
contains(x::ArbFieldElem, y::QQFieldElem)

Returns true if the ball $x$ contains the given rational value, otherwise return false.

source
containsMethod
contains(x::ArbFieldElem, y::Rational{T}) where {T <: Integer}

Returns true if the ball $x$ contains the given rational value, otherwise return false.

source
containsMethod
contains(x::ArbFieldElem, y::BigFloat)

Returns true if the ball $x$ contains the given floating point value, otherwise return false.

source

The following functions are also provided for determining if a ball intersects a certain part of the real number line.

contains_zeroMethod
contains_zero(x::ArbFieldElem)

Returns true if the ball $x$ contains zero, otherwise return false.

source
contains_negativeMethod
contains_negative(x::ArbFieldElem)

Returns true if the ball $x$ contains any negative value, otherwise return false.

source
contains_positiveMethod
contains_positive(x::ArbFieldElem)

Returns true if the ball $x$ contains any positive value, otherwise return false.

source
contains_nonnegativeMethod
contains_nonnegative(x::ArbFieldElem)

Returns true if the ball $x$ contains any non-negative value, otherwise return false.

source
contains_nonpositiveMethod
contains_nonpositive(x::ArbFieldElem)

Returns true if the ball $x$ contains any nonpositive value, otherwise return false.

source

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> x = RR("1 +/- 0.001")
[1.00 +/- 1.01e-3]

julia> y = RR("3")
3.0000000000000000000

julia> overlaps(x, y)
false

julia> contains(x, y)
false

julia> contains(y, 3)
true

julia> contains(x, ZZ(1)//2)
false

julia> contains_zero(x)
false

julia> contains_positive(y)
true

Comparison

Nemo provides a full range of comparison operations for Arb balls. Note that a ball is considered less than another ball if every value in the first ball is less than every value in the second ball, etc.

In addition to the standard comparison operators, we introduce an exact equality. This is distinct from arithmetic equality implemented by ==, which merely compares up to the minimum of the precisions of its operands.

isequalMethod
isequal(x::ArbFieldElem, y::ArbFieldElem)

Return true if the balls $x$ and $y$ are precisely equal, i.e. have the same midpoints and radii.

source

We also provide a full range of ad hoc comparison operators. These are implemented directly in Julia, but we document them as though isless and == were provided.

Function
==(x::ArbFieldElem, y::Integer)
==(x::Integer, y::ArbFieldElem)
==(x::ArbFieldElem, y::ZZRingElem)
==(x::ZZRingElem, y::ArbFieldElem)
==(x::ArbFieldElem, y::Float64)
==(x::Float64, y::ArbFieldElem)
isless(x::ArbFieldElem, y::Integer)
isless(x::Integer, y::ArbFieldElem)
isless(x::ArbFieldElem, y::ZZRingElem)
isless(x::ZZRingElem, y::ArbFieldElem)
isless(x::ArbFieldElem, y::Float64)
isless(x::Float64, y::ArbFieldElem)
isless(x::ArbFieldElem, y::BigFloat)
isless(x::BigFloat, y::ArbFieldElem)
isless(x::ArbFieldElem, y::QQFieldElem)
isless(x::QQFieldElem, y::ArbFieldElem)

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> x = RR("1 +/- 0.001")
[1.00 +/- 1.01e-3]

julia> y = RR("3")
3.0000000000000000000

julia> z = RR("4")
4.0000000000000000000

julia> isequal(x, deepcopy(x))
true

julia> x == 3
false

julia> ZZ(3) < z
true

julia> x != 1.23
true

julia> 3 == y
true

Absolute value

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> x = RR("-1 +/- 0.001")
[-1.00 +/- 1.01e-3]

julia> a = abs(x)
[1.00 +/- 1.01e-3]

Shifting

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> x = RR("-3 +/- 0.001")
[-3.00 +/- 1.01e-3]

julia> a = ldexp(x, 23)
[-2.52e+7 +/- 4.26e+4]

julia> b = ldexp(x, -ZZ(15))
[-9.16e-5 +/- 7.78e-8]

Miscellaneous operations

add_error!Method
add_error!(x::ArbFieldElem, y::ArbFieldElem)

Adds the absolute values of the midpoint and radius of $y$ to the radius of $x$.

source
trimMethod
trim(x::ArbFieldElem)

Return an ArbFieldElem interval containing $x$ but which may be more economical, by rounding off insignificant bits from the midpoint.

source
unique_integerMethod
unique_integer(x::ArbFieldElem)

Return a pair where the first value is a boolean and the second is an ZZRingElem integer. The boolean indicates whether the interval $x$ contains a unique integer. If this is the case, the second return value is set to this unique integer.

source
setunionMethod
setunion(x::ArbFieldElem, y::ArbFieldElem)

Return an ArbFieldElem containing the union of the intervals represented by $x$ and $y$.

source

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> x = RR("-3 +/- 0.001")
[-3.00 +/- 1.01e-3]

julia> y = RR("2 +/- 0.5")
[2e+0 +/- 0.501]

julia> a = trim(x)
[-3.00 +/- 1.01e-3]

julia> b, c = unique_integer(x)
(true, -3)

julia> d = setunion(x, y)
[+/- 3.01]

Constants

const_piMethod
const_pi(r::ArbField)

Return $\pi = 3.14159\ldots$ as an element of $r$.

source
const_eMethod
const_e(r::ArbField)

Return $e = 2.71828\ldots$ as an element of $r$.

source
const_log2Method
const_log2(r::ArbField)

Return $\log(2) = 0.69314\ldots$ as an element of $r$.

source
const_log10Method
const_log10(r::ArbField)

Return $\log(10) = 2.302585\ldots$ as an element of $r$.

source
const_eulerMethod
const_euler(r::ArbField)

Return Euler's constant $\gamma = 0.577215\ldots$ as an element of $r$.

source
const_catalanMethod
const_catalan(r::ArbField)

Return Catalan's constant $C = 0.915965\ldots$ as an element of $r$.

source
const_khinchinMethod
const_khinchin(r::ArbField)

Return Khinchin's constant $K = 2.685452\ldots$ as an element of $r$.

source
const_glaisherMethod
const_glaisher(r::ArbField)

Return Glaisher's constant $A = 1.282427\ldots$ as an element of $r$.

source

Examples

julia> RR = ArbField(200)
Real Field with 200 bits of precision and error bounds

julia> a = const_pi(RR)
[3.14159265358979323846264338327950288419716939937510582097494 +/- 5.73e-60]

julia> b = const_e(RR)
[2.71828182845904523536028747135266249775724709369995957496697 +/- 7.06e-60]

julia> c = const_euler(RR)
[0.577215664901532860606512090082402431042159335939923598805767 +/- 5.37e-61]

julia> d = const_glaisher(RR)
[1.28242712910062263687534256886979172776768892732500119206374 +/- 2.18e-60]

Mathematical and special functions

rsqrtMethod
rsqrt(x::ArbFieldElem)

Return the reciprocal of the square root of $x$, i.e. $1/\sqrt{x}$.

source
sqrt1pm1Method
sqrt1pm1(x::ArbFieldElem)

Return $\sqrt{1+x}-1$, evaluated accurately for small $x$.

source
sqrtposMethod
sqrtpos(x::ArbFieldElem)

Return the sqrt root of $x$, assuming that $x$ represents a non-negative number. Thus any negative number in the input interval is discarded.

source
gammaMethod
gamma(x::ArbFieldElem)

Return the Gamma function evaluated at $x$.

source
lgammaMethod
lgamma(x::ArbFieldElem)

Return the logarithm of the Gamma function evaluated at $x$.

source
rgammaMethod
rgamma(x::ArbFieldElem)

Return the reciprocal of the Gamma function evaluated at $x$.

source
digammaMethod
digamma(x::ArbFieldElem)

Return the logarithmic derivative of the gamma function evaluated at $x$, i.e. $\psi(x)$.

source
gammaMethod
gamma(s::ArbFieldElem, x::ArbFieldElem)

Return the upper incomplete gamma function $\Gamma(s,x)$.

source
gamma_regularizedMethod
gamma_regularized(s::ArbFieldElem, x::ArbFieldElem)

Return the regularized upper incomplete gamma function $\Gamma(s,x) / \Gamma(s)$.

source
gamma_lowerMethod
gamma_lower(s::ArbFieldElem, x::ArbFieldElem)

Return the lower incomplete gamma function $\gamma(s,x) / \Gamma(s)$.

source
gamma_lower_regularizedMethod
gamma_lower_regularized(s::ArbFieldElem, x::ArbFieldElem)

Return the regularized lower incomplete gamma function $\gamma(s,x) / \Gamma(s)$.

source
zetaMethod
zeta(x::ArbFieldElem)

Return the Riemann zeta function evaluated at $x$.

source
atan2Method
atan2(y::ArbFieldElem, x::ArbFieldElem)

Return $\operatorname{atan2}(y,x) = \arg(x+yi)$. Same as atan(y, x).

source
agmMethod
agm(x::ArbFieldElem, y::ArbFieldElem)

Return the arithmetic-geometric mean of $x$ and $y$

source
zetaMethod
zeta(s::ArbFieldElem, a::ArbFieldElem)

Return the Hurwitz zeta function $\zeta(s,a)$.

source
rootMethod
root(x::ArbFieldElem, n::Int)

Return the $n$-th root of $x$. We require $x \geq 0$.

source
factorialMethod
factorial(x::ArbFieldElem)

Return the factorial of $x$.

source
factorialMethod
factorial(n::Int, r::ArbField)

Return the factorial of $n$ in the given Arb field.

source
binomialMethod
binomial(x::ArbFieldElem, n::UInt)

Return the binomial coefficient ${x \choose n}$.

source
binomialMethod
binomial(n::UInt, k::UInt, r::ArbField)

Return the binomial coefficient ${n \choose k}$ in the given Arb field.

source
fibonacciMethod
fibonacci(n::ZZRingElem, r::ArbField)

Return the $n$-th Fibonacci number in the given Arb field.

source
fibonacciMethod
fibonacci(n::Int, r::ArbField)

Return the $n$-th Fibonacci number in the given Arb field.

source
gammaMethod
gamma(x::ZZRingElem, r::ArbField)

Return the Gamma function evaluated at $x$ in the given Arb field.

source
gammaMethod
gamma(x::QQFieldElem, r::ArbField)

Return the Gamma function evaluated at $x$ in the given Arb field.

source
zetaMethod
zeta(n::Int, r::ArbField)

Return the Riemann zeta function $\zeta(n)$ as an element of the given Arb field.

source
bernoulliMethod
bernoulli(n::Int, r::ArbField)

Return the $n$-th Bernoulli number as an element of the given Arb field.

source
rising_factorialMethod
rising_factorial(x::ArbFieldElem, n::Int)

Return the rising factorial $x(x + 1)\ldots (x + n - 1)$ as an Arb.

source
rising_factorialMethod
rising_factorial(x::QQFieldElem, n::Int, r::ArbField)

Return the rising factorial $x(x + 1)\ldots (x + n - 1)$ as an element of the given Arb field.

source
rising_factorial2Method
rising_factorial2(x::ArbFieldElem, n::Int)

Return a tuple containing the rising factorial $x(x + 1)\ldots (x + n - 1)$ and its derivative.

source
polylogMethod
polylog(s::Union{ArbFieldElem,Int}, a::ArbFieldElem)

Return the polylogarithm Li$_s(a)$.

source
chebyshev_tMethod
chebyshev_t(n::Int, x::ArbFieldElem)

Return the value of the Chebyshev polynomial $T_n(x)$.

source
chebyshev_uMethod
chebyshev_u(n::Int, x::ArbFieldElem)

Return the value of the Chebyshev polynomial $U_n(x)$.

source
chebyshev_t2Method
chebyshev_t2(n::Int, x::ArbFieldElem)

Return the tuple $(T_{n}(x), T_{n-1}(x))$.

source
chebyshev_u2Method
chebyshev_u2(n::Int, x::ArbFieldElem)

Return the tuple $(U_{n}(x), U_{n-1}(x))$

source
bellMethod
bell(n::ZZRingElem, r::ArbField)

Return the Bell number $B_n$ as an element of $r$.

source
bellMethod
bell(n::Int, r::ArbField)

Return the Bell number $B_n$ as an element of $r$.

source
numpartMethod
numpart(n::ZZRingElem, r::ArbField)

Return the number of partitions $p(n)$ as an element of $r$.

source
numpartMethod
numpart(n::Int, r::ArbField)

Return the number of partitions $p(n)$ as an element of $r$.

source
airy_aiMethod
airy_ai(x::ArbFieldElem)

Return the Airy function $\operatorname{Ai}(x)$.

source
airy_ai_primeMethod
airy_ai_prime(x::ArbFieldElem)

Return the derivative of the Airy function $\operatorname{Ai}^\prime(x)$.

source
airy_biMethod
airy_bi(x::ArbFieldElem)

Return the Airy function $\operatorname{Bi}(x)$.

source
airy_bi_primeMethod
airy_bi_prime(x::ArbFieldElem)

Return the derivative of the Airy function $\operatorname{Bi}^\prime(x)$.

source

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> a = floor(exp(RR(1)))
2.0000000000000000000

julia> b = sinpi(QQ(5,6), RR)
0.50000000000000000000

julia> c = gamma(QQ(1,3), ArbField(256))
[2.6789385347077476336556929409746776441286893779573011009504283275904176101677 +/- 6.71e-77]

julia> d = bernoulli(1000, ArbField(53))
[-5.318704469415522e+1769 +/- 8.20e+1753]

julia> f = polylog(3, RR(-10))
[-5.92106480375697 +/- 6.68e-15]

Linear dependence

lindepMethod
lindep(A::Vector{ArbFieldElem}, bits::Int)

Find a small linear combination of the entries of the array $A$ that is small (using LLL). The entries are first scaled by the given number of bits before truncating to integers for use in LLL. This function can be used to find linear dependence between a list of real numbers. The algorithm is heuristic only and returns an array of Nemo integers representing the linear combination.

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> a = RR(-0.33198902958450931620250069492231652319)
[-0.33198902958450932088 +/- 4.15e-22]

julia> V = [RR(1), a, a^2, a^3, a^4, a^5]
6-element Vector{ArbFieldElem}:
 1.0000000000000000000
 [-0.33198902958450932088 +/- 4.15e-22]
 [0.11021671576446420510 +/- 7.87e-21]
 [-0.03659074051063616184 +/- 4.17e-21]
 [0.012147724433904692427 +/- 4.99e-22]
 [-0.004032911246472051677 +/- 6.25e-22]

julia> W = lindep(V, 20)
6-element Vector{ZZRingElem}:
 1
 3
 0
 0
 0
 1
source

Examples

julia> RR = ArbField(128)
Real Field with 128 bits of precision and error bounds

julia> a = RR(-0.33198902958450931620250069492231652319) # real root of x^5 + 3x + 1
[-0.331989029584509320880414406929048709571 +/- 3.62e-40]

julia> V = [RR(1), a, a^2, a^3, a^4, a^5]
6-element Vector{ArbFieldElem}:
 1.00000000000000000000000000000000000000
 [-0.331989029584509320880414406929048709571 +/- 3.62e-40]
 [0.110216715764464205102727554344054759368 +/- 3.32e-40]
 [-0.0365907405106361618384680031506015710184 +/- 8.30e-41]
 [0.0121477244339046924274232580429164920524 +/- 2.83e-41]
 [-0.00403291124647205167662794872826031818905 +/- 7.87e-42]

julia> W = lindep(V, 20)
6-element Vector{ZZRingElem}:
 1
 3
 0
 0
 0
 1
simplest_rational_insideMethod
  simplest_rational_inside(x::ArbFieldElem)

Return the simplest fraction inside the ball $x$. A canonical fraction $a_1/b_1$ is defined to be simpler than $a_2/b_2$ iff $b_1 < b_2$ or $b_1 = b_2$ and $a_1 < a_2$.

Examples

julia> RR = ArbField(64)
Real Field with 64 bits of precision and error bounds

julia> simplest_rational_inside(const_pi(RR))
8717442233//2774848045
source

Random generation

randMethod
rand(r::ArbField; randtype::Symbol=:urandom)

Return a random element in given Arb field.

The randtype default is :urandom which return an ArbFieldElem contained in $[0,1]$.

The rest of the methods return non-uniformly distributed values in order to exercise corner cases. The option :randtest will return a finite number, and :randtest_exact the same but with a zero radius. The option :randtest_precise return an ArbFieldElem with a radius around $2^{-\mathrm{prec}}$ the magnitude of the midpoint, while :randtest_wide return a radius that might be big relative to its midpoint. The :randtest_special-option might return a midpoint and radius whose values are NaN or inf.

source

Examples

RR = ArbField(100)

a = rand(RR)
b = rand(RR; randtype = :null_exact)
c = rand(RR; randtype = :exact)
d = rand(RR; randtype = :special)