uint icon indicating copy to clipboard operation
uint copied to clipboard

`algorithms/gcd/matrix`: We can update r0 and r1 in place. This won't remove the partially

Open github-actions[bot] opened this issue 2 years ago • 0 comments

On 2022-06-06 @recmo wrote in 4c74c09 “Merge pull request #110 from recmo/gcd”:

We can update r0 and r1 in place. This won't remove the partially redundant call to lehmer_update, but it reduces memory usage.

    /// 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.
    // OPT: We can update r0 and r1 in place. This won't remove the partially
    // redundant call to lehmer_update, but it reduces memory usage.
    #[must_use]
    pub fn from_u128_prefix(r0: u128, r1: u128) -> Self {
        debug_assert!(r0 >= r1);
        let s = r0.leading_zeros();
        let r0s = r0 << s;

From src/algorithms/gcd/matrix.rs:298

github-actions[bot] avatar Jun 06 '22 03:06 github-actions[bot]