Struct ruint::algorithms::LehmerMatrix

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

⚠️ Lehmer update matrix

Warning. This struct 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.

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.

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

Applies the matrix to a u128.

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.

Panics

Panics if b > a.

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

Compute the Lehmer update matrix for small values.

This is essentially Euclids extended GCD algorithm for 64 bits.

Panics

Panics if r1 < r0.

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

Compute the largest valid Lehmer update matrix for a prefix.

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.

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<Matrix> for Matrix

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

This method tests for self and other values to be equal, and is used by ==.

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

This method 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 StructuralEq for Matrix

impl StructuralPartialEq for Matrix