mathematics/
lib.rs

1/// Computes the greatest common divisor of 2 natural numbers and 2 additional numbers such that gcd(a,b)=s·a+t·b holds.
2///
3/// # Examples
4///
5/// ```
6/// let a = 27;
7/// let b = 5;
8/// let  (gcd, s, t) = mathematics::extended_euclidean_algorithm(a, b);
9///
10///  assert_eq!(gcd,5);
11///  assert_eq!(s, 1);
12///  assert_eq!(t, -4);
13/// ```
14pub fn extended_euclidean_algorithm(a:i64,b:i64)->(i64, i64, i64){ if a <= 0 || b <= 0{
15        panic!("natural numbers only")
16    }
17    let mut q =0;
18    let mut r1 = a;
19    let mut r2=b;
20    let mut s = 1;
21    let mut t = 0;
22    let mut s1 = 0;
23    let mut t1 = 1;
24
25    loop{
26        q = r1/r2;
27        let new_r = r2;
28        let new_s = s1;
29        let new_t = t1;
30
31        r2 = r1 % r2;
32
33        s1 = s - q * s1;
34
35        s = new_s;
36        t1 = t - q * t1;
37        t = new_t;
38        r1 =  new_r;
39        if r2 == 0{
40        break  (s*a + t*b, s, t);
41        }
42   
43    }
44    
45
46
47}
48
49
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn moon_math1() {
57        let (gcd, s, t)=extended_euclidean_algorithm(27, 5);
58        assert_eq!(gcd,1);
59        assert_eq!(s, -2);
60        assert_eq!(t, 11);
61    }
62    #[test]
63    fn moon_math2() {
64      let (gcd, s, t)=extended_euclidean_algorithm(45, 10);
65        assert_eq!(gcd,5);
66        assert_eq!(s, 1);
67        assert_eq!(t, -4);
68    }
69    #[test]
70    fn moon_math3() {
71      let (gcd, s, t) =extended_euclidean_algorithm(13, 11);
72        assert_eq!(gcd,1);
73        assert_eq!(s, -5);
74        assert_eq!(t, 6);
75    }
76    #[test]
77    fn moon_math4() {
78      let (gcd, s, t)=extended_euclidean_algorithm(13, 12);
79        assert_eq!(gcd,1);
80        assert_eq!(s, 1);
81        assert_eq!(t, -1);
82    }
83      #[test]
84    #[should_panic(expected = "natural numbers only")]
85    fn moon_math5() {
86    extended_euclidean_algorithm(0, 12);
87    }
88      #[test]
89    #[should_panic(expected = "natural numbers only")]
90    fn moon_math6() {
91    extended_euclidean_algorithm(12, 0);
92    }
93
94       #[test]
95    #[should_panic(expected = "natural numbers only")]
96    fn moon_math7() {
97    extended_euclidean_algorithm(0, 0);
98    }
99   
100}
mathematics/lib.rs

mathematics/
lib.rs
