malachite-base 0.4.6

A collection of utilities, including new arithmetic traits and iterators that generate all values of a type
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

use crate::num::basic::signeds::PrimitiveSigned;
use crate::num::basic::unsigneds::PrimitiveUnsigned;
use crate::num::conversion::traits::WrappingFrom;

pub fn extended_gcd_unsigned_euclidean<
    U: PrimitiveUnsigned,
    S: PrimitiveSigned + WrappingFrom<U>,
>(
    a: U,
    b: U,
) -> (U, S, S) {
    if a == U::ZERO && b == U::ZERO {
        (U::ZERO, S::ZERO, S::ZERO)
    } else if a == b || a == U::ZERO {
        (b, S::ZERO, S::ONE)
    } else {
        let (gcd, x, y) = extended_gcd_unsigned_euclidean(b % a, a);
        (gcd, y - S::wrapping_from(b / a) * x, x)
    }
}