#![no_std]
pub trait IntegerCubeRoot {
fn integer_cbrt(&self) -> Self
where
Self: Sized,
{
self.integer_cbrt_checked()
.expect("cannot calculate cube root of negative number")
}
fn integer_cbrt_checked(&self) -> Option<Self>
where
Self: Sized;
}
impl<T: num_traits::PrimInt> IntegerCubeRoot for T {
fn integer_cbrt_checked(&self) -> Option<Self> {
use core::cmp::Ordering;
match self.cmp(&T::zero()) {
Ordering::Less => return None,
Ordering::Equal => return Some(T::zero()),
_ => {}
}
let one = T::one();
let three = one + one + one;
let mut x = *self;
let mut result = T::zero();
let num_bits = T::zero().leading_zeros() - x.leading_zeros();
for s in (0..num_bits).step_by(3).rev() {
result = result + result;
let b = three * result * (result + one) + one;
if (x >> s as usize) >= b {
x = x - (b << s as usize);
result = result + one;
}
}
Some(result)
}
}
#[cfg(test)]
mod tests {
use super::IntegerCubeRoot;
use core::{i8, u16, u64, u8};
macro_rules! gen_tests {
($($type:ty => $fn_name:ident),*) => {
$(
#[test]
fn $fn_name() {
let newton_raphson = |val, cube| 1./3. * (2. * val + (cube / (val as $type * val as $type)) as f64);
let max_cbrt = {
let cube = <$type>::max_value();
let mut value = (cube as f64).cbrt();
for _ in 0..2 {
value = newton_raphson(value, cube);
}
let mut value = value as $type;
if value.checked_mul(value*value).is_none() {
value -= 1;
}
value
};
let tests: [($type, $type); 10] = [
(0, 0),
(1, 1),
(2, 1),
(3, 1),
(4, 1),
(8, 2),
(64, 4),
(63, 3),
(<$type>::max_value(), max_cbrt),
(<$type>::max_value() - 1, max_cbrt),
];
for &(in_, out) in tests.iter() {
assert_eq!(in_.integer_cbrt(), out, "in {}", in_);
}
}
)*
};
}
gen_tests! {
i8 => i8_test,
u8 => u8_test,
i16 => i16_test,
u16 => u16_test,
i32 => i32_test,
u32 => u32_test,
i64 => i64_test,
u64 => u64_test,
isize => isize_test,
usize => usize_test
}
#[test]
fn i128_test() {
let tests: [(i128, i128); 10] = [
(0, 0),
(1, 1),
(2, 1),
(3, 1),
(4, 1),
(64, 4),
(63, 3),
(23_985_346_875, 2_883),
(24_958_973_498_745, 29_224),
(i128::max_value(), 5_541_191_377_756),
];
for &(in_, out) in tests.iter() {
assert_eq!(in_.integer_cbrt(), out, "in {}", in_);
}
}
#[test]
fn u128_test() {
let tests: [(u128, u128); 13] = [
(0, 0),
(1, 1),
(2, 1),
(3, 1),
(4, 1),
(64, 4),
(63, 3),
(438975000000, 7599),
(438975999999, 7599),
(14348907000000, 24300),
(23_985_346_875, 2_883),
(24_958_973_498_745, 29_224),
(u128::max_value(), 6_981_463_658_331),
];
for &(in_, out) in tests.iter() {
assert_eq!(in_.integer_cbrt(), out, "in {}", in_);
}
}
}