Struct LehmerMatrix

pub struct LehmerMatrix(pub u64, pub u64, pub u64, pub u64, pub bool);

⚠️ Lehmer update matrix

⚠️ This function is not part of the stable API.

Signs are implicit, the boolean `.4` encodes which of two sign patterns applies. The signs and layout of the matrix are:

    true          false
 [ .0  -.1]    [-.0   .1]
 [-.2   .3]    [ .2  -.3]

Tuple Fields

0: u64

1: u64

2: u64

3: u64

4: bool

Implementations

impl Matrix

pub const IDENTITY: Self

pub const fn compose(self, other: Self) -> Self

⚠️ Returns the matrix product self * other.

⚠️ This function is not part of the stable API.

pub fn apply<const BITS: usize, const LIMBS: usize>( &self, a: &mut Uint<BITS, LIMBS>, b: &mut Uint<BITS, LIMBS>, )

⚠️ Applies the matrix to a Uint.

⚠️ This function is not part of the stable API.

pub const fn apply_u128(&self, a: u128, b: u128) -> (u128, u128)

⚠️ Applies the matrix to a u128.

⚠️ This function is not part of the stable API.

pub fn from<const BITS: usize, const LIMBS: usize>( a: Uint<BITS, LIMBS>, b: Uint<BITS, LIMBS>, ) -> Self

⚠️ Compute a Lehmer update matrix from two Uints.

⚠️ This function is not part of the stable API.

# Panics

Panics if b > a.

pub fn from_u64(r0: u64, r1: u64) -> Self

⚠️ Compute the Lehmer update matrix for small values.

⚠️ This function is not part of the stable API.

This is essentially Euclids extended GCD algorithm for 64 bits.

Panics

Panics if r0 < r1.

pub fn from_u64_prefix(a0: u64, a1: u64) -> Self

⚠️ Compute the largest valid Lehmer update matrix for a prefix.

⚠️ This function is not part of the stable API.

Compute the Lehmer update matrix for a0 and a1 such that the matrix is valid for any two large integers starting with the bits of a0 and a1.

See also mpn_hgcd2 in GMP, but ours handles the double precision bit separately in lehmer_double. https://gmplib.org/repo/gmp-6.1/file/tip/mpn/generic/hgcd2.c#l226

Panics

Panics if a0 does not have the highest bit set. Panics if a0 < a1.

pub fn from_u128_prefix(r0: u128, r1: u128) -> Self

⚠️ Compute the Lehmer update matrix in full 64 bit precision.

⚠️ This function is not part of the stable API.

Jebelean solves this by starting in double-precission followed by single precision once values are small enough. Cohen instead runs a single precision round, refreshes the r0 and r1 values and continues with another single precision round on top. Our approach is similar to Cohen, but instead doing the second round on the same matrix, we start we a fresh matrix and multiply both in the end. This requires 8 additional multiplications, but allows us to use the tighter stopping conditions from Jebelean. It also seems the simplest out of these solutions.

Trait Implementations

impl Clone for Matrix

fn clone(&self) -> Matrix

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Matrix

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

Formats the value using the given formatter.

impl PartialEq for Matrix

fn eq(&self, other: &Matrix) -> 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 Copy for Matrix

impl Eq for Matrix

impl StructuralPartialEq for Matrix