algo 0.1.9

Algorithms & Data Structure implementations
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

use std::num::{Zero, One};
use std::ops::{Shl, Shr, BitAnd, BitOr, Add, Sub, Neg, Rem};

pub fn euclid_gcd<T>(mut u: T, mut v: T) -> T
where T: Copy,
      T: Zero,
      T: PartialEq,
      T: PartialOrd,
      T: Rem<Output = T>,
      T: Neg<Output = T>
{
    let mut t;
    let zero = T::zero();
    while v != zero {
        t = u;
        u = v;
        v = t % v;
    }

    if u < zero {
        -u
    } else {
        u
    }
}

pub fn binary_gcd<T>(mut u: T, mut v: T) -> T
where T: Copy,
      T: Zero,
      T: One,
      T: PartialEq,
      T: PartialOrd,
      T: Shl<T, Output = T>,
      T: Shr<T, Output = T>,
      T: BitAnd<Output = T>,
      T: BitOr<Output = T>,
      T: Add<Output = T>,
      T: Sub<Output = T>
{
    if u == v {
        return u;
    }

    let zero = T::zero();
    if u == zero || v == zero {
        return u + v;
    }

    let mut shift = T::zero();
    let one = T::one();

    while ((u | v) & one) == zero {
        u = u >> one;
        v = v >> one;

        shift = shift + one;
    }

    while (u & one) == zero {
        u = u >> one;
    }

    while v != zero {
        while (v & one) == zero {
            v = v >> one;
        }

        if u > v {
            let t = v;
            v = u;
            u = t;
        }

        v = v - u;
    }

    u << shift
}

#[test]
fn test_euclid_zero() {
    assert_eq!(0, euclid_gcd(0, 0));
}

#[test]
fn test_euclid_same() {
    assert_eq!(10, euclid_gcd(10, 10));
}

#[test]
fn test_euclid_simple() {
    assert_eq!(7, euclid_gcd(14, 21));
}

#[test]
fn test_euclid_prime() {
    assert_eq!(1, euclid_gcd(132512537, 132512351));
}
#[test]
fn test_binary_zero() {
    assert_eq!(0, binary_gcd(0, 0));
}

#[test]
fn test_binary_same() {
    assert_eq!(10, binary_gcd(10, 10));
}

#[test]
fn test_binary_simple() {
    assert_eq!(7, binary_gcd(14, 21));
}

#[test]
fn test_binary_prime() {
    assert_eq!(1, binary_gcd(132512537, 132512351));
}

#[bench]
fn bench_euclid_primes(b: &mut ::test::Bencher) {
    b.iter(|| euclid_gcd(132512537, 132512351))
}

#[bench]
fn bench_binary_primes(b: &mut ::test::Bencher) {
    b.iter(|| binary_gcd(132512537, 132512351))
}