Trait feanor_math::integer::IntegerRing

source ·

pub trait IntegerRing: Domain + EuclideanRing + OrderedRing + HashableElRing {
    // 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 power_of_two(&self, power: usize) -> Self::Element { ... }
}

Expand description

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.

Required Methods§

source

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

Computes a float value that is supposed to be close to value. 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().

source

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

source

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));

source

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));

source

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));

source

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);

source

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

Multiplies the element by a power of two.

source

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.

source

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§

source

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));