integer_cbrt/
lib.rs

1//!
2//! This module contains the single trait [`IntegerCubeRoot`] and implements it for primitive
3//! integer types.
4//!
5//! # Example
6//!
7//! ```
8//! extern crate integer_cbrt;
9//! // `use` trait to get functionality
10//! use integer_cbrt::IntegerCubeRoot;
11//!
12//! # fn main() {
13//! assert_eq!(8u8.integer_cbrt(), 2);
14//! # }
15//! ```
16//!
17//! [`IntegerCubeRoot`]: ./trait.IntegerCubeRoot.html
18#![no_std]
19
20/// A trait implementing integer cube root.
21pub trait IntegerCubeRoot {
22    /// Find the integer cube root.
23    ///
24    /// # Panics
25    ///
26    /// For negative numbers (`i` family) this function will panic on negative input
27    fn integer_cbrt(&self) -> Self
28    where
29        Self: Sized,
30    {
31        self.integer_cbrt_checked()
32            .expect("cannot calculate cube root of negative number")
33    }
34
35    /// Find the integer cube root, returning `None` if the number is negative (this can never
36    /// happen for unsigned types).
37    fn integer_cbrt_checked(&self) -> Option<Self>
38    where
39        Self: Sized;
40}
41
42impl<T: num_traits::PrimInt> IntegerCubeRoot for T {
43    fn integer_cbrt_checked(&self) -> Option<Self> {
44        use core::cmp::Ordering;
45        match self.cmp(&T::zero()) {
46            // Hopefully this will be stripped for unsigned numbers (impossible condition)
47            Ordering::Less => return None,
48            Ordering::Equal => return Some(T::zero()),
49            _ => {}
50        }
51
52        // Taken from: https://gist.github.com/anonymous/729557, and generalized to all
53        // integer primitive types.
54        let one = T::one();
55        let three = one + one + one;
56
57        let mut x = *self;
58        let mut result = T::zero();
59        let num_bits = T::zero().leading_zeros() - x.leading_zeros();
60        for s in (0..num_bits).step_by(3).rev() {
61            result = result + result;
62            let b = three * result * (result + one) + one;
63            if (x >> s as usize) >= b {
64                x = x - (b << s as usize);
65                result = result + one;
66            }
67        }
68        Some(result)
69    }
70}
71
72#[cfg(test)]
73mod tests {
74    use super::IntegerCubeRoot;
75    use core::{i8, u16, u64, u8};
76    // use std::println;
77
78    macro_rules! gen_tests {
79        ($($type:ty => $fn_name:ident),*) => {
80            $(
81                #[test]
82                fn $fn_name() {
83                    // https://en.wikipedia.org/wiki/Cube_root#Numerical_methods
84                    let newton_raphson = |val, cube| 1./3. * (2. * val + (cube / (val as $type * val as $type)) as f64);
85                    let max_cbrt = {
86                        let cube = <$type>::max_value();
87                        let mut value = (cube as f64).cbrt();
88                        for _ in 0..2 {
89                            value = newton_raphson(value, cube);
90                        }
91                        let mut value = value as $type;
92                        // make sure we are below the max value (this is how integer cube
93                        // root works)
94                        if value.checked_mul(value*value).is_none() {
95                            value -= 1;
96                        }
97                        value
98                    };
99                    let tests: [($type, $type); 10] = [
100                        (0, 0),
101                        (1, 1),
102                        (2, 1),
103                        (3, 1),
104                        (4, 1),
105                        (8, 2),
106                        (64, 4),
107                        (63, 3),
108                        (<$type>::max_value(), max_cbrt),
109                        (<$type>::max_value() - 1, max_cbrt),
110                    ];
111                    for &(in_, out) in tests.iter() {
112                        assert_eq!(in_.integer_cbrt(), out, "in {}", in_);
113                    }
114                }
115            )*
116        };
117    }
118
119    gen_tests! {
120        i8 => i8_test,
121        u8 => u8_test,
122        i16 => i16_test,
123        u16 => u16_test,
124        i32 => i32_test,
125        u32 => u32_test,
126        i64 => i64_test,
127        u64 => u64_test,
128        isize => isize_test,
129        usize => usize_test
130    }
131
132    #[test]
133    fn i128_test() {
134        let tests: [(i128, i128); 10] = [
135            (0, 0),
136            (1, 1),
137            (2, 1),
138            (3, 1),
139            (4, 1),
140            (64, 4),
141            (63, 3),
142            (23_985_346_875, 2_883),
143            (24_958_973_498_745, 29_224),
144            (i128::max_value(), 5_541_191_377_756),
145        ];
146        for &(in_, out) in tests.iter() {
147            assert_eq!(in_.integer_cbrt(), out, "in {}", in_);
148        }
149    }
150
151    #[test]
152    fn u128_test() {
153        let tests: [(u128, u128); 13] = [
154            (0, 0),
155            (1, 1),
156            (2, 1),
157            (3, 1),
158            (4, 1),
159            (64, 4),
160            (63, 3),
161            (438975000000, 7599),
162            (438975999999, 7599),
163            (14348907000000, 24300),
164            (23_985_346_875, 2_883),
165            (24_958_973_498_745, 29_224),
166            (u128::max_value(), 6_981_463_658_331),
167        ];
168        for &(in_, out) in tests.iter() {
169            assert_eq!(in_.integer_cbrt(), out, "in {}", in_);
170        }
171    }
172}
integer_cbrt/lib.rs

integer_cbrt/
lib.rs
