floor_sqrt/
lib.rs

1/// `floor(sqrt(n))` を返す。
2///
3/// # Examples
4/// ```
5/// use floor_sqrt::floor_sqrt;
6///
7/// assert_eq!(floor_sqrt(0), 0);
8/// assert_eq!(floor_sqrt(1), 1);
9/// assert_eq!(floor_sqrt(2), 1);
10/// assert_eq!(floor_sqrt(3), 1);
11/// assert_eq!(floor_sqrt(4), 2);
12/// assert_eq!(floor_sqrt(5), 2);
13/// ```
14pub fn floor_sqrt(n: u64) -> u64 {
15    let mut ok = 0;
16    let mut ng = u64::from(u32::MAX);
17    while ng - ok > 1 {
18        let m = (ng + ok) / 2;
19        if m * m <= n {
20            ok = m;
21        } else {
22            ng = m;
23        }
24    }
25    assert!(ok * ok <= n);
26    assert!((ok + 1) * (ok + 1) > n);
27    ok
28}
29
30#[cfg(test)]
31mod tests {
32    use crate::floor_sqrt;
33
34    #[test]
35    fn test() {
36        assert_eq!(floor_sqrt(0), 0);
37        assert_eq!(floor_sqrt(1), 1);
38        assert_eq!(floor_sqrt(2), 1);
39        assert_eq!(floor_sqrt(3), 1);
40        assert_eq!(floor_sqrt(4), 2);
41        assert_eq!(floor_sqrt(5), 2);
42    }
43}
floor_sqrt/lib.rs

floor_sqrt/
lib.rs
