Repository navigation
Expand file tree
/
Copy pathutils.rs
More file actions
110 lines (96 loc) · 2.77 KB
/
Copy pathutils.rs
File metadata and controls
110 lines (96 loc) · 2.77 KB
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
#[inline]
pub fn log2_ceil(n: usize) -> usize {
assert_ne!(n, 0, "Attempt log(0)!");
const NUM_OF_BITS_IN_BYTE: usize = 8;
let num_of_bits = std::mem::size_of_val(&n) * NUM_OF_BITS_IN_BYTE;
num_of_bits - (n - 1).leading_zeros() as usize
}
#[inline]
pub fn log2_floor(n: usize) -> usize {
assert_ne!(n, 0, "Attempt log(0)!");
const NUM_OF_BITS_IN_BYTE: usize = 8;
let num_of_bits = std::mem::size_of_val(&n) * NUM_OF_BITS_IN_BYTE;
num_of_bits - n.leading_zeros() as usize - 1
}
#[inline]
pub fn next_pow_two(n: usize) -> usize {
2_usize.pow(log2_ceil(n) as u32)
}
#[inline]
pub fn prev_pow_two(n: usize) -> usize {
2_usize.pow(log2_floor(n) as u32)
}
/// Get the ceiling value of an unsigned integer division.
// TODO(Ohad): Consider removing assertion.
#[inline]
pub fn usize_div_ceil(a: usize, b: usize) -> usize {
assert_ne!(b, 0, "Attempt division by 0!");
(a + b - 1) / b
}
#[inline]
pub fn usize_safe_div(a: usize, b: usize) -> usize {
assert_ne!(b, 0, "Attempt division by 0!");
let quotient = a / b;
assert_eq!(a, quotient * b, "Attempt division with remainder!");
quotient
}
/// Returns s, t, g such that g = gcd(x,y), sx + ty = g.
pub fn egcd(x: isize, y: isize) -> (isize, isize, isize) {
if x == 0 {
return (0, 1, y);
}
let k = y / x;
let (s, t, g) = egcd(y % x, x);
(t - s * k, s, g)
}
#[cfg(test)]
mod tests {
use crate::math::utils::{
egcd, log2_ceil, log2_floor, next_pow_two, prev_pow_two, usize_div_ceil,
};
#[test]
fn log2_ceil_test() {
assert_eq!(log2_ceil(1), 0);
assert_eq!(log2_ceil(63), 6);
assert_eq!(log2_ceil(64), 6);
assert_eq!(log2_ceil(65), 7);
}
#[test]
fn log2_floor_test() {
assert_eq!(log2_floor(1), 0);
assert_eq!(log2_floor(63), 5);
assert_eq!(log2_floor(64), 6);
assert_eq!(log2_floor(65), 6);
}
#[test]
fn next_power_of_two_test() {
assert_eq!(next_pow_two(1), 1);
assert_eq!(next_pow_two(2), 2);
assert_eq!(next_pow_two(3), 4);
}
#[test]
fn prev_power_of_two_test() {
assert_eq!(prev_pow_two(1), 1);
assert_eq!(prev_pow_two(2), 2);
assert_eq!(prev_pow_two(3), 2);
}
#[test]
fn div_ceil_test() {
assert_eq!(usize_div_ceil(6, 4), 2);
assert_eq!(usize_div_ceil(6, 3), 2);
}
#[test]
#[should_panic(expected = "Attempt division by 0!")]
fn div_ceil_by_zero_test() {
usize_div_ceil(6, 0);
}
#[test]
fn test_egcd() {
let pairs = [(17, 5, 1), (6, 4, 2), (7, 7, 7)];
for (x, y, res) in pairs.into_iter() {
let (a, b, gcd) = egcd(x, y);
assert_eq!(gcd, res);
assert_eq!(a * x + b * y, gcd);
}
}
}