Struct Natural 

pub struct Natural { /* private fields */ }

Natural number, specifically well-suited for counting satisfying assignments

When counting the number of satisfying assignments in a decision diagram, the numbers often have many trailing zeros (in binary representation). Based on this observation, we decompose numbers as m × 2^^e with a mantissa m and an exponent e. We require that both m and e are natural numbers. Further, m is odd unless the represented number is zero, in which case both m and e are zero.

The exponent e is stored as a u64 and the mantissa m as an array of u64 “digits.” In case m fits into a single u64 digit, m is stored inline, i.e., without any heap allocation.

Conceptually, this type is similar to arbitrary precision floats. However, we do not require the user to choose the precision, instead we always represent numbers exactly.

To account for computation errors (e.g., an exponent that cannot be represented as a u64). this type includes a NaN value. It is undefined if this value is larger or smaller than actual natural numbers. Therefore, this type does not implement Ord but only PartialOrd.

Also note that the implementation of Shr is tailored to the application in counting satisfying assignments, where it is used as an exact division by (a power of) two. If a 1-bit would get lost by a shift to the right, i.e., the division result would not be exact, the computation result is NaN to make the error obvious. A context for such an error may be pretending that a Boolean function has a smaller domain than it actually has.

Implementations

impl Natural

pub const ZERO: Self

The number 0

pub fn from_le_digits(digits: &[u64]) -> Self

Create a Natural from a sequence of digits

Here, le stands for little endian, i.e., the first element of digits is the least significant digit.

pub fn mantissa(&self) -> &[u64]

Get the mantissa

The returned sequence starts with the least significant digit and has minimal length, but at least one element. So unless the mantissa is 0, the most significant digit (i.e., the last element) is non-zero.

pub fn exp(&self) -> u64

Get the exponent

pub fn is_nan(&self) -> bool

Check if the number is NaN

pub fn bit_width(&self) -> u128

Compute the number of bits needed to represent the number explicitly, that is 1 + floor(log₂(self)).

Trait Implementations

impl Add for Natural

type Output = Natural

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self

Performs the + operation.

impl Binary for Natural

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Clone for Natural

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Natural

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for Natural

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Drop for Natural

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl Eq for Natural

impl From<&Natural> for f64

fn from(value: &Natural) -> Self

Converts to this type from the input type.

impl From<u8> for Natural

fn from(value: u8) -> Self

Converts to this type from the input type.

impl From<u16> for Natural

fn from(value: u16) -> Self

Converts to this type from the input type.

impl From<u32> for Natural

fn from(value: u32) -> Self

Converts to this type from the input type.

impl From<u64> for Natural

fn from(value: u64) -> Self

Converts to this type from the input type.

impl From<u128> for Natural

fn from(value: u128) -> Self

Converts to this type from the input type.

impl Hash for Natural

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl IsFloatingPoint for Natural

cbindgen:ignore

const FLOATING_POINT: bool = false

true iff the underlying type is a floating point number

const MIN_EXP: i32 = 0

One greater than the minimum possible normal power of 2 exponent, see f64::MIN_EXP for instance. 0 for integers

impl LowerHex for Natural

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Octal for Natural

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq for Natural

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for Natural

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Send for Natural

impl Shl<u32> for Natural

type Output = Natural

The resulting type after applying the << operator.

fn shl(self, rhs: u32) -> Self

Performs the << operation.

impl Shl<u64> for Natural

type Output = Natural

The resulting type after applying the << operator.

fn shl(self, rhs: u64) -> Self

Performs the << operation.

impl Shr<u32> for Natural

type Output = Natural

The resulting type after applying the >> operator.

fn shr(self, rhs: u32) -> Self

Performs the >> operation.

impl Shr<u64> for Natural

type Output = Natural

The resulting type after applying the >> operator.

fn shr(self, rhs: u64) -> Self

Performs the >> operation.

impl Sync for Natural

impl TryFrom<&Natural> for UBig

type Error = NotRepresentable

The type returned in the event of a conversion error.

fn try_from(value: &Natural) -> Result<Self, Self::Error>

Performs the conversion.

impl TryFrom<&Natural> for u128

type Error = NotRepresentable

The type returned in the event of a conversion error.

fn try_from(value: &Natural) -> Result<Self, Self::Error>

Performs the conversion.

impl TryFrom<&Natural> for u64

type Error = NotRepresentable

The type returned in the event of a conversion error.

fn try_from(value: &Natural) -> Result<Self, Self::Error>

Performs the conversion.

impl UpperHex for Natural

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.