Integer Square Root
isqrt(s)
returns \( \left\lfloor \sqrt{s} \right\rfloor \). It runs much faster than the typical binary search method, but slower than casting the result from std::f64::sqrt
. If the value can be perfectly represented with f64
and the memory limit isn't too short, it's better to use the f64
square root function from std
.
Example
fn main() { let x: u64 = 10002; let sq = isqrt(x); println!("{}", sq); // 100 } fn isqrt(s: u64) -> u64 { let mut x0 = s >> 1; if x0 != 0 { let mut x1 = (x0 + s / x0) >> 1; while x1 < x0 { x0 = x1; x1 = (x0 + s / x0) >> 1 } x0 } else { s } }
Code
fn isqrt<T>(s: T) -> T
where T: Copy + Shr<Output = T> + Add<Output = T> + Div<Output = T> + PartialOrd + From<u8> {
let mut x0 = s >> 1.into();
if x0 != 0.into() {
let mut x1 = (x0 + s / x0) >> 1.into();
while x1 < x0 {
x0 = x1;
x1 = (x0 + s / x0) >> 1.into();
}
x0
} else {
s
}
}
Last modified on 231203.