Trait IntegerRing

pub trait IntegerRing:
    Domain
    + EuclideanRing
    + OrderedRing
    + HashableElRing
    + IntegerPolyGCDRing
    + EvalPolyLocallyRing {
    // Required methods
    fn to_float_approx(&self, value: &Self::Element) -> f64;
    fn from_float_approx(&self, value: f64) -> Option<Self::Element>;
    fn abs_is_bit_set(&self, value: &Self::Element, i: usize) -> bool;
    fn abs_highest_set_bit(&self, value: &Self::Element) -> Option<usize>;
    fn abs_lowest_set_bit(&self, value: &Self::Element) -> Option<usize>;
    fn euclidean_div_pow_2(&self, value: &mut Self::Element, power: usize);
    fn mul_pow_2(&self, value: &mut Self::Element, power: usize);
    fn get_uniformly_random_bits<G: FnMut() -> u64>(
        &self,
        log2_bound_exclusive: usize,
        rng: G,
    ) -> Self::Element;
    fn representable_bits(&self) -> Option<usize>;

    // Provided methods
    fn rounded_div(
        &self,
        lhs: Self::Element,
        rhs: &Self::Element,
    ) -> Self::Element { ... }
    fn ceil_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element { ... }
    fn floor_div(
        &self,
        lhs: Self::Element,
        rhs: &Self::Element,
    ) -> Self::Element { ... }
    fn power_of_two(&self, power: usize) -> Self::Element { ... }
    fn parse(&self, string: &str, base: u32) -> Result<Self::Element, ()> { ... }
}

Trait for rings that are isomorphic to the ring of integers ZZ = { ..., -2, -1, 0, 1, 2, ... }.

Some of the functionality in this trait refers to the binary expansion of a positive integer. While this is not really general, it is often required for fast operations with integers.

As an additional requirement, the euclidean division (i.e. EuclideanRing::euclidean_div_rem() and IntegerRing::euclidean_div_pow_2()) are additionally expected to round towards zero.

Currently IntegerRing is a subtrait of the unstable traits IntegerPolyGCDRing and, EvalPolyLocallyRing so it is at the moment impossible to implement IntegerRing for a custom ring type without enabling unstable features. Sorry.

Required Methods

fn to_float_approx(&self, value: &Self::Element) -> f64

Computes a float value that is “close” to the given integer.

However, no guarantees are made on how close it must be, in particular, this function may also always return 0. (this is just an example - it’s not a good idea).

Some use cases include:

• Estimating control parameters (e.g. bounds for prime numbers during factoring algorithms)
• First performing some operation on floating point numbers, and then refining it to integers.

Note that a high-quality implementation of this function can vastly improve performance in some cases, e.g. of crate::algorithms::int_bisect::root_floor() or crate::algorithms::lll::lll_exact().

Example

let ZZ = BigIntRing::RING;
let x = ZZ.power_of_two(1023);
assert!(ZZ.to_float_approx(&x) > 2f64.powi(1023) * 0.99999);
assert!(ZZ.to_float_approx(&x) < 2f64.powi(1023) * 1.000001);

If the value is too large for the exponent of a f64, infinity is returned.

let ZZ = BigIntRing::RING;
let x = ZZ.power_of_two(1024);
assert!(ZZ.to_float_approx(&x).is_infinite());

fn from_float_approx(&self, value: f64) -> Option<Self::Element>

Computes a value that is “close” to the given float. However, no guarantees are made on the definition of close, in particular, this does not have to be the closest integer to the given float, and cannot be used to compute rounding. It is also implementation-defined when to return None, although this is usually the case on infinity and NaN.

For information when to use (or not use) this, see its counterpart IntegerRing::to_float_approx().

fn abs_is_bit_set(&self, value: &Self::Element, i: usize) -> bool

Return whether the i-th bit in the two-complements representation of abs(value) is 1.

Example

assert_eq!(false, StaticRing::<i32>::RING.abs_is_bit_set(&4, 1));
assert_eq!(true, StaticRing::<i32>::RING.abs_is_bit_set(&4, 2));
assert_eq!(true, StaticRing::<i32>::RING.abs_is_bit_set(&-4, 2));

fn abs_highest_set_bit(&self, value: &Self::Element) -> Option<usize>

Returns the index of the highest set bit in the two-complements representation of abs(value), or None if the value is zero.

Example

assert_eq!(None, StaticRing::<i32>::RING.abs_highest_set_bit(&0));
assert_eq!(Some(0), StaticRing::<i32>::RING.abs_highest_set_bit(&-1));
assert_eq!(Some(2), StaticRing::<i32>::RING.abs_highest_set_bit(&4));

fn abs_lowest_set_bit(&self, value: &Self::Element) -> Option<usize>

Returns the index of the lowest set bit in the two-complements representation of abs(value), or None if the value is zero.

Example

assert_eq!(None, StaticRing::<i32>::RING.abs_lowest_set_bit(&0));
assert_eq!(Some(0), StaticRing::<i32>::RING.abs_lowest_set_bit(&1));
assert_eq!(Some(0), StaticRing::<i32>::RING.abs_lowest_set_bit(&-3));
assert_eq!(Some(2), StaticRing::<i32>::RING.abs_lowest_set_bit(&4));

fn euclidean_div_pow_2(&self, value: &mut Self::Element, power: usize)

Computes the euclidean division by a power of two, always rounding to zero (note that euclidean division requires that |remainder| < |divisor|, and thus would otherwise leave multiple possible results).

Example

let mut value = -7;
StaticRing::<i32>::RING.euclidean_div_pow_2(&mut value, 1);
assert_eq!(-3, value);

fn mul_pow_2(&self, value: &mut Self::Element, power: usize)

Multiplies the element by a power of two.

fn get_uniformly_random_bits<G: FnMut() -> u64>( &self, log2_bound_exclusive: usize, rng: G, ) -> Self::Element

Computes a uniformly random integer in [0, 2^log_bound_exclusive - 1], assuming that rng provides uniformly random values in the whole range of u64.

fn representable_bits(&self) -> Option<usize>

Returns n such that this ring can represent at least [-2^n, ..., 2^n - 1]. Returning None means that the size of representable integers is unbounded.

Provided Methods

fn rounded_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

Computes the rounded division, i.e. rounding to the closest integer. In the case of a tie (i.e. round(0.5)), we round towards +/- infinity.

Example

assert_eq!(2, StaticRing::<i32>::RING.rounded_div(7, &3));
assert_eq!(-2, StaticRing::<i32>::RING.rounded_div(-7, &3));
assert_eq!(-2, StaticRing::<i32>::RING.rounded_div(7, &-3));
assert_eq!(2, StaticRing::<i32>::RING.rounded_div(-7, &-3));
 
assert_eq!(3, StaticRing::<i32>::RING.rounded_div(8, &3));
assert_eq!(-3, StaticRing::<i32>::RING.rounded_div(-8, &3));
assert_eq!(-3, StaticRing::<i32>::RING.rounded_div(8, &-3));
assert_eq!(3, StaticRing::<i32>::RING.rounded_div(-8, &-3));
 
assert_eq!(4, StaticRing::<i32>::RING.rounded_div(7, &2));
assert_eq!(-4, StaticRing::<i32>::RING.rounded_div(-7, &2));
assert_eq!(-4, StaticRing::<i32>::RING.rounded_div(7, &-2));
assert_eq!(4, StaticRing::<i32>::RING.rounded_div(-7, &-2));

fn ceil_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

Computes the division lhs / rhs, rounding towards + infinity.

In particular, if rhs is positive, this gives the smallest integer quo such that quo * rhs >= lhs. On the other hand, if rhs is negative, this computes the largest integer quo such that quo * rhs <= lhs.

Example

assert_eq!(3, StaticRing::<i32>::RING.ceil_div(7, &3));
assert_eq!(-2, StaticRing::<i32>::RING.ceil_div(-7, &3));
assert_eq!(-2, StaticRing::<i32>::RING.ceil_div(7, &-3));
assert_eq!(3, StaticRing::<i32>::RING.ceil_div(-7, &-3));

fn floor_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

Computes the division lhs / rhs, rounding towards - infinity.

In particular, if rhs is positive, this gives the largest integer quo such that quo * rhs <= lhs. On the other hand, if rhs is negative, this computes the smallest integer quo such that quo * rhs >= lhs.

Example

assert_eq!(2, StaticRing::<i32>::RING.floor_div(7, &3));
assert_eq!(-3, StaticRing::<i32>::RING.floor_div(-7, &3));
assert_eq!(-3, StaticRing::<i32>::RING.floor_div(7, &-3));
assert_eq!(2, StaticRing::<i32>::RING.floor_div(-7, &-3));

fn power_of_two(&self, power: usize) -> Self::Element

Returns the value 2^power in this integer ring.

fn parse(&self, string: &str, base: u32) -> Result<Self::Element, ()>

Parses the given string as a number.

Returns Err(()) if it is not a valid number w.r.t. base, i.e. if the string is not a sequence of digit characters, optionally beginning with + or -. To denote digits larger than 9, the same characters as in u64::from_str_radix() should be used.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl IntegerRing for MPZBase

Available on crate feature mpir only.

impl<A: Allocator + Clone> IntegerRing for RustBigintRingBase<A>

impl<T: PrimitiveInt> IntegerRing for StaticRingBase<T>