/rust/registry/src/index.crates.io-1949cf8c6b5b557f/num-integer-0.1.47/src/roots.rs

Source
use crate::Integer;
use core::mem;
use num_traits::{checked_pow, PrimInt};

/// Provides methods to compute an integer's square root, cube root,
/// and arbitrary `n`th root.
pub trait Roots: Integer {
    /// Returns the truncated principal `n`th root of an integer
    /// -- `if x >= 0 { ⌊ⁿ√x⌋ } else { ⌈ⁿ√x⌉ }`
    ///
    /// This is solving for `r` in `rⁿ = x`, rounding toward zero.
    /// If `x` is positive, the result will satisfy `rⁿ ≤ x < (r+1)ⁿ`.
    /// If `x` is negative and `n` is odd, then `(r-1)ⁿ < x ≤ rⁿ`.
    ///
    /// # Panics
    ///
    /// Panics if `n` is zero:
    ///
    /// ```should_panic
    /// # use num_integer::Roots;
    /// println!("can't compute ⁰√x : {}", 123.nth_root(0));
    /// ```
    ///
    /// or if `n` is even and `self` is negative:
    ///
    /// ```should_panic
    /// # use num_integer::Roots;
    /// println!("no imaginary numbers... {}", (-1).nth_root(10));
    /// ```
    ///
    /// # Examples
    ///
    /// ```
    /// use num_integer::Roots;
    ///
    /// let x: i32 = 12345;
    /// assert_eq!(x.nth_root(1), x);
    /// assert_eq!(x.nth_root(2), x.sqrt());
    /// assert_eq!(x.nth_root(3), x.cbrt());
    /// assert_eq!(x.nth_root(4), 10);
    /// assert_eq!(x.nth_root(13), 2);
    /// assert_eq!(x.nth_root(14), 1);
    /// assert_eq!(x.nth_root(std::u32::MAX), 1);
    ///
    /// assert_eq!(std::i32::MAX.nth_root(30), 2);
    /// assert_eq!(std::i32::MAX.nth_root(31), 1);
    /// assert_eq!(std::i32::MIN.nth_root(31), -2);
    /// assert_eq!((std::i32::MIN + 1).nth_root(31), -1);
    ///
    /// assert_eq!(std::u32::MAX.nth_root(31), 2);
    /// assert_eq!(std::u32::MAX.nth_root(32), 1);
    /// ```
    fn nth_root(&self, n: u32) -> Self;

    /// Returns the truncated principal square root of an integer -- `⌊√x⌋`
    ///
    /// This is solving for `r` in `r² = x`, rounding toward zero.
    /// The result will satisfy `r² ≤ x < (r+1)²`.
    ///
    /// # Panics
    ///
    /// Panics if `self` is less than zero:
    ///
    /// ```should_panic
    /// # use num_integer::Roots;
    /// println!("no imaginary numbers... {}", (-1).sqrt());
    /// ```
    ///
    /// # Examples
    ///
    /// ```
    /// use num_integer::Roots;
    ///
    /// let x: i32 = 12345;
    /// assert_eq!((x * x).sqrt(), x);
    /// assert_eq!((x * x + 1).sqrt(), x);
    /// assert_eq!((x * x - 1).sqrt(), x - 1);
    /// ```
    #[inline]
    fn sqrt(&self) -> Self {
        self.nth_root(2)
    }

    /// Returns the truncated principal cube root of an integer --
    /// `if x >= 0 { ⌊∛x⌋ } else { ⌈∛x⌉ }`
    ///
    /// This is solving for `r` in `r³ = x`, rounding toward zero.
    /// If `x` is positive, the result will satisfy `r³ ≤ x < (r+1)³`.
    /// If `x` is negative, then `(r-1)³ < x ≤ r³`.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_integer::Roots;
    ///
    /// let x: i32 = 1234;
    /// assert_eq!((x * x * x).cbrt(), x);
    /// assert_eq!((x * x * x + 1).cbrt(), x);
    /// assert_eq!((x * x * x - 1).cbrt(), x - 1);
    ///
    /// assert_eq!((-(x * x * x)).cbrt(), -x);
    /// assert_eq!((-(x * x * x + 1)).cbrt(), -x);
    /// assert_eq!((-(x * x * x - 1)).cbrt(), -(x - 1));
    /// ```
    #[inline]
    fn cbrt(&self) -> Self {
        self.nth_root(3)
    }
}

/// Returns the truncated principal square root of an integer --
/// see [Roots::sqrt](trait.Roots.html#method.sqrt).
#[inline]
pub fn sqrt<T: Roots>(x: T) -> T {
    x.sqrt()
}

/// Returns the truncated principal cube root of an integer --
/// see [Roots::cbrt](trait.Roots.html#method.cbrt).
#[inline]
pub fn cbrt<T: Roots>(x: T) -> T {
    x.cbrt()
}

/// Returns the truncated principal `n`th root of an integer --
/// see [Roots::nth_root](trait.Roots.html#tymethod.nth_root).
#[inline]
pub fn nth_root<T: Roots>(x: T, n: u32) -> T {
    x.nth_root(n)
}

macro_rules! signed_roots {
    ($T:ty, $U:ty) => {
        impl Roots for $T {
            #[inline]
            fn nth_root(&self, n: u32) -> Self {
                if *self >= 0 {
                    (*self as $U).nth_root(n) as Self
                } else {
                    assert!(n.is_odd(), "even roots of a negative are imaginary");
                    -((self.wrapping_neg() as $U).nth_root(n) as Self)
                }
            }

            #[inline]
            fn sqrt(&self) -> Self {
                assert!(*self >= 0, "the square root of a negative is imaginary");
                (*self as $U).sqrt() as Self
            }

            #[inline]
            fn cbrt(&self) -> Self {
                if *self >= 0 {
                    (*self as $U).cbrt() as Self
                } else {
                    -((self.wrapping_neg() as $U).cbrt() as Self)
                }
            }
        }
    };
}

signed_roots!(i8, u8);
signed_roots!(i16, u16);
signed_roots!(i32, u32);
signed_roots!(i64, u64);
signed_roots!(i128, u128);
signed_roots!(isize, usize);

#[inline]
fn fixpoint<T, F>(mut x: T, f: F) -> T
where
    T: Integer + Copy,
    F: Fn(T) -> T,
{
    let mut xn = f(x);
    while x < xn {
        x = xn;
        xn = f(x);
    }
    while x > xn {
        x = xn;
        xn = f(x);
    }
    x
}

#[inline]
fn bits<T>() -> u32 {
    8 * mem::size_of::<T>() as u32
}

#[inline]
fn log2<T: PrimInt>(x: T) -> u32 {
    debug_assert!(x > T::zero());
    bits::<T>() - 1 - x.leading_zeros()
}

/// 128-bit Karatsuba Square Root, using b = 2³²
///
/// Reference:
/// Paul Zimmermann. Karatsuba Square Root. [Research Report] RR-3805, INRIA. 1999, pp.8.
/// <https://inria.hal.science/inria-00072854/en/>
#[inline]
fn karatsuba_sqrt(n: u128) -> u128 {
    // Algorithm SqrtRem(n = a₃b³ + a₂b² + a₁b + a₀)
    // Input: 0 ≤ aᵢ < b with a₃ ≥ b/4
    // Output: (s,r) such that s² ≤ n = s² + r < (s+1)²
    debug_assert!(n.leading_zeros() < 2);
    let a0 = n as u32 as u128;
    let a1 = (n >> 32) as u32 as u128;
    let a23 = n >> 64;

    // (s',r') ← SqrtRem(a₃b + a₂)
    let s1 = (a23 as u64).sqrt() as u128;
    let r1 = a23 - s1 * s1;

    // (q,u) ← DivRem(r'b + a₁, 2s')
    let (q, u) = ((r1 << 32) | a1).div_rem(&(2 * s1));

    // s ← s'b + q
    let mut s = (s1 << 32) + q;

    // r ← ub + a₀ - q²
    // if r < 0 then
    //   r ← r + 2s - 1
    //   s ← s - 1
    //
    // but to avoid negatives, we compare and adjust before subtraction,
    // and in this case we don't care about the actual remainder.
    if ((u << 32) | a0) < q * q {
        s -= 1;
    }
    s
}

macro_rules! unsigned_roots {
    ($T:ident) => {
        impl Roots for $T {
            #[inline]
            fn nth_root(&self, n: u32) -> Self {
                fn go(a: $T, n: u32) -> $T {
                    // Specialize small roots
                    match n {
                        0 => panic!("can't find a root of degree 0!"),
                        1 => return a,
                        2 => return a.sqrt(),
                        3 => return a.cbrt(),
                        _ => (),
                    }

                    // The root of values less than 2ⁿ can only be 0 or 1.
                    if bits::<$T>() <= n || a < (1 << n) {
                        return (a > 0) as $T;
                    }

                    if bits::<$T>() > 64 {
                        // 128-bit division is slow, so do a bitwise `nth_root` until it's small enough.
                        return if a <= core::u64::MAX as $T {
                            (a as u64).nth_root(n) as $T
                        } else {
                            let lo = (a >> n).nth_root(n) << 1;
                            let hi = lo + 1;
                            // 128-bit `checked_mul` also involves division, but we can't always
                            // compute `hiⁿ` without risking overflow.  Try to avoid it though...
                            if hi.next_power_of_two().trailing_zeros() * n >= bits::<$T>() {
                                match checked_pow(hi, n as usize) {
                                    Some(x) if x <= a => hi,
                                    _ => lo,
                                }
                            } else {
                                if hi.pow(n) <= a {
                                    hi
                                } else {
                                    lo
                                }
                            }
                        };
                    }

                    #[cfg(feature = "std")]
                    #[inline]
                    fn guess(x: $T, n: u32) -> $T {
                        // for smaller inputs, `f64` doesn't justify its cost.
                        if bits::<$T>() <= 32 || x <= core::u32::MAX as $T {
                            1 << ((log2(x) + n - 1) / n)
                        } else {
                            ((x as f64).ln() / f64::from(n)).exp() as $T
                        }
                    }

                    #[cfg(not(feature = "std"))]
                    #[inline]
                    fn guess(x: $T, n: u32) -> $T {
                        1 << ((log2(x) + n - 1) / n)
                    }

                    // https://en.wikipedia.org/wiki/Nth_root_algorithm
                    let n1 = n - 1;
                    let next = |x: $T| {
                        let y = match checked_pow(x, n1 as usize) {
                            Some(ax) => a / ax,
                            None => 0,
                        };
                        (y + x * n1 as $T) / n as $T
                    };
                    fixpoint(guess(a, n), next)
                }
                go(*self, n)
            }

            #[inline]
            fn sqrt(&self) -> Self {
                fn go(a: $T) -> $T {
                    if bits::<$T>() > 64 {
                        // 128-bit division is slow in the Babylonian method,
                        // so use 64-bit sqrt and Karatsuba if needed.
                        return if a <= core::u64::MAX as $T {
                            (a as u64).sqrt() as $T
                        } else {
                            let shift = a.leading_zeros() / 2;
                            let n = a << (shift * 2);
                            (karatsuba_sqrt(n as u128) >> shift) as $T
                        };
                    }

                    if a < 4 {
                        return (a > 0) as $T;
                    }

                    #[cfg(feature = "std")]
                    #[inline]
                    fn guess(x: $T) -> $T {
                        (x as f64).sqrt() as $T
                    }

                    #[cfg(not(feature = "std"))]
                    #[inline]
                    fn guess(x: $T) -> $T {
                        1 << ((log2(x) + 1) / 2)
                    }

                    // https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
                    let next = |x: $T| (a / x + x) >> 1;
                    fixpoint(guess(a), next)
                }
                go(*self)
            }

            #[inline]
            fn cbrt(&self) -> Self {
                fn go(a: $T) -> $T {
                    if bits::<$T>() > 64 {
                        // 128-bit division is slow, so do a bitwise `cbrt` until it's small enough.
                        return if a <= core::u64::MAX as $T {
                            (a as u64).cbrt() as $T
                        } else {
                            let lo = (a >> 3u32).cbrt() << 1;
                            let hi = lo + 1;
                            if hi * hi * hi <= a {
                                hi
                            } else {
                                lo
                            }
                        };
                    }

                    if bits::<$T>() <= 32 {
                        // Implementation based on Hacker's Delight `icbrt2`
                        let mut x = a;
                        let mut y2 = 0;
                        let mut y = 0;
                        let smax = bits::<$T>() / 3;
                        for s in (0..smax + 1).rev() {
                            let s = s * 3;
                            y2 *= 4;
                            y *= 2;
                            let b = 3 * (y2 + y) + 1;
                            if x >> s >= b {
                                x -= b << s;
                                y2 += 2 * y + 1;
                                y += 1;
                            }
                        }
                        return y;
                    }

                    if a < 8 {
                        return (a > 0) as $T;
                    }
                    if a <= core::u32::MAX as $T {
                        return (a as u32).cbrt() as $T;
                    }

                    #[cfg(feature = "std")]
                    #[inline]
                    fn guess(x: $T) -> $T {
                        (x as f64).cbrt() as $T
                    }

                    #[cfg(not(feature = "std"))]
                    #[inline]
                    fn guess(x: $T) -> $T {
                        1 << ((log2(x) + 2) / 3)
                    }

                    // https://en.wikipedia.org/wiki/Cube_root#Numerical_methods
                    let next = |x: $T| (a / (x * x) + x * 2) / 3;
                    fixpoint(guess(a), next)
                }
                go(*self)
            }
        }
    };
}

unsigned_roots!(u8);
unsigned_roots!(u16);
unsigned_roots!(u32);
unsigned_roots!(u64);
unsigned_roots!(u128);
unsigned_roots!(usize);

Coverage Report

Created: 2026-10-17 07:26

Line	Count	Source
1		use crate::Integer;
2		use core::mem;
3		use num_traits::{checked_pow, PrimInt};
4
5		/// Provides methods to compute an integer's square root, cube root,
6		/// and arbitrary `n`th root.
7		pub trait Roots: Integer {
8		/// Returns the truncated principal `n`th root of an integer
9		/// -- `if x >= 0 { ⌊ⁿ√x⌋ } else { ⌈ⁿ√x⌉ }`
10		///
11		/// This is solving for `r` in `rⁿ = x`, rounding toward zero.
12		/// If `x` is positive, the result will satisfy `rⁿ ≤ x < (r+1)ⁿ`.
13		/// If `x` is negative and `n` is odd, then `(r-1)ⁿ < x ≤ rⁿ`.
14		///
15		/// # Panics
16		///
17		/// Panics if `n` is zero:
18		///
19		/// ```should_panic
20		/// # use num_integer::Roots;
21		/// println!("can't compute ⁰√x : {}", 123.nth_root(0));
22		/// ```
23		///
24		/// or if `n` is even and `self` is negative:
25		///
26		/// ```should_panic
27		/// # use num_integer::Roots;
28		/// println!("no imaginary numbers... {}", (-1).nth_root(10));
29		/// ```
30		///
31		/// # Examples
32		///
33		/// ```
34		/// use num_integer::Roots;
35		///
36		/// let x: i32 = 12345;
37		/// assert_eq!(x.nth_root(1), x);
38		/// assert_eq!(x.nth_root(2), x.sqrt());
39		/// assert_eq!(x.nth_root(3), x.cbrt());
40		/// assert_eq!(x.nth_root(4), 10);
41		/// assert_eq!(x.nth_root(13), 2);
42		/// assert_eq!(x.nth_root(14), 1);
43		/// assert_eq!(x.nth_root(std::u32::MAX), 1);
44		///
45		/// assert_eq!(std::i32::MAX.nth_root(30), 2);
46		/// assert_eq!(std::i32::MAX.nth_root(31), 1);
47		/// assert_eq!(std::i32::MIN.nth_root(31), -2);
48		/// assert_eq!((std::i32::MIN + 1).nth_root(31), -1);
49		///
50		/// assert_eq!(std::u32::MAX.nth_root(31), 2);
51		/// assert_eq!(std::u32::MAX.nth_root(32), 1);
52		/// ```
53		fn nth_root(&self, n: u32) -> Self;
54
55		/// Returns the truncated principal square root of an integer -- `⌊√x⌋`
56		///
57		/// This is solving for `r` in `r² = x`, rounding toward zero.
58		/// The result will satisfy `r² ≤ x < (r+1)²`.
59		///
60		/// # Panics
61		///
62		/// Panics if `self` is less than zero:
63		///
64		/// ```should_panic
65		/// # use num_integer::Roots;
66		/// println!("no imaginary numbers... {}", (-1).sqrt());
67		/// ```
68		///
69		/// # Examples
70		///
71		/// ```
72		/// use num_integer::Roots;
73		///
74		/// let x: i32 = 12345;
75		/// assert_eq!((x * x).sqrt(), x);
76		/// assert_eq!((x * x + 1).sqrt(), x);
77		/// assert_eq!((x * x - 1).sqrt(), x - 1);
78		/// ```
79		#[inline]
80	0	fn sqrt(&self) -> Self {
81	0	self.nth_root(2)
82	0	}
83
84		/// Returns the truncated principal cube root of an integer --
85		/// `if x >= 0 { ⌊∛x⌋ } else { ⌈∛x⌉ }`
86		///
87		/// This is solving for `r` in `r³ = x`, rounding toward zero.
88		/// If `x` is positive, the result will satisfy `r³ ≤ x < (r+1)³`.
89		/// If `x` is negative, then `(r-1)³ < x ≤ r³`.
90		///
91		/// # Examples
92		///
93		/// ```
94		/// use num_integer::Roots;
95		///
96		/// let x: i32 = 1234;
97		/// assert_eq!((x * x * x).cbrt(), x);
98		/// assert_eq!((x * x * x + 1).cbrt(), x);
99		/// assert_eq!((x * x * x - 1).cbrt(), x - 1);
100		///
101		/// assert_eq!((-(x * x * x)).cbrt(), -x);
102		/// assert_eq!((-(x * x * x + 1)).cbrt(), -x);
103		/// assert_eq!((-(x * x * x - 1)).cbrt(), -(x - 1));
104		/// ```
105		#[inline]
106	0	fn cbrt(&self) -> Self {
107	0	self.nth_root(3)
108	0	}
109		}
110
111		/// Returns the truncated principal square root of an integer --
112		/// see [Roots::sqrt](trait.Roots.html#method.sqrt).
113		#[inline]
114	0	pub fn sqrt<T: Roots>(x: T) -> T {
115	0	x.sqrt()
116	0	}
117
118		/// Returns the truncated principal cube root of an integer --
119		/// see [Roots::cbrt](trait.Roots.html#method.cbrt).
120		#[inline]
121	0	pub fn cbrt<T: Roots>(x: T) -> T {
122	0	x.cbrt()
123	0	}
124
125		/// Returns the truncated principal `n`th root of an integer --
126		/// see [Roots::nth_root](trait.Roots.html#tymethod.nth_root).
127		#[inline]
128	0	pub fn nth_root<T: Roots>(x: T, n: u32) -> T {
129	0	x.nth_root(n)
130	0	}
131
132		macro_rules! signed_roots {
133		($T:ty, $U:ty) => {
134		impl Roots for $T {
135		#[inline]
136	0	fn nth_root(&self, n: u32) -> Self {
137	0	if *self >= 0 {
138	0	(*self as $U).nth_root(n) as Self
139		} else {
140	0	assert!(n.is_odd(), "even roots of a negative are imaginary");
141	0	-((self.wrapping_neg() as $U).nth_root(n) as Self)
142		}
143	0	} Unexecuted instantiation: <i8 as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <i32 as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <i64 as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <i128 as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <isize as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <i16 as num_integer::roots::Roots>::nth_root
144
145		#[inline]
146	0	fn sqrt(&self) -> Self {
147	0	assert!(*self >= 0, "the square root of a negative is imaginary");
148	0	(*self as $U).sqrt() as Self
149	0	} Unexecuted instantiation: <i8 as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <i32 as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <i64 as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <i128 as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <isize as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <i16 as num_integer::roots::Roots>::sqrt
150
151		#[inline]
152	0	fn cbrt(&self) -> Self {
153	0	if *self >= 0 {
154	0	(*self as $U).cbrt() as Self
155		} else {
156	0	-((self.wrapping_neg() as $U).cbrt() as Self)
157		}
158	0	} Unexecuted instantiation: <i8 as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <i32 as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <i64 as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <i128 as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <isize as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <i16 as num_integer::roots::Roots>::cbrt
159		}
160		};
161		}
162
163		signed_roots!(i8, u8);
164		signed_roots!(i16, u16);
165		signed_roots!(i32, u32);
166		signed_roots!(i64, u64);
167		signed_roots!(i128, u128);
168		signed_roots!(isize, usize);
169
170		#[inline]
171	0	fn fixpoint<T, F>(mut x: T, f: F) -> T
172	0	where
173	0	T: Integer + Copy,
174	0	F: Fn(T) -> T,
175		{
176	0	let mut xn = f(x);
177	0	while x < xn {
178	0	x = xn;
179	0	xn = f(x);
180	0	}
181	0	while x > xn {
182	0	x = xn;
183	0	xn = f(x);
184	0	}
185	0	x
186	0	} Unexecuted instantiation: num_integer::roots::fixpoint::<u8, <u8 as num_integer::roots::Roots>::cbrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u8, <u8 as num_integer::roots::Roots>::sqrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u8, <u8 as num_integer::roots::Roots>::nth_root::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<usize, <usize as num_integer::roots::Roots>::cbrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<usize, <usize as num_integer::roots::Roots>::sqrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<usize, <usize as num_integer::roots::Roots>::nth_root::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u32, <u32 as num_integer::roots::Roots>::cbrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u32, <u32 as num_integer::roots::Roots>::sqrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u32, <u32 as num_integer::roots::Roots>::nth_root::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u128, <u128 as num_integer::roots::Roots>::cbrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u128, <u128 as num_integer::roots::Roots>::sqrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u128, <u128 as num_integer::roots::Roots>::nth_root::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u16, <u16 as num_integer::roots::Roots>::cbrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u16, <u16 as num_integer::roots::Roots>::sqrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u16, <u16 as num_integer::roots::Roots>::nth_root::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u64, <u64 as num_integer::roots::Roots>::cbrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u64, <u64 as num_integer::roots::Roots>::sqrt::go::{closure#0}> Unexecuted instantiation: num_integer::roots::fixpoint::<u64, <u64 as num_integer::roots::Roots>::nth_root::go::{closure#0}>
187
188		#[inline]
189	0	fn bits<T>() -> u32 {
190	0	8 * mem::size_of::<T>() as u32
191	0	} Unexecuted instantiation: num_integer::roots::bits::<u8> Unexecuted instantiation: num_integer::roots::bits::<usize> Unexecuted instantiation: num_integer::roots::bits::<u32> Unexecuted instantiation: num_integer::roots::bits::<u128> Unexecuted instantiation: num_integer::roots::bits::<u16> Unexecuted instantiation: num_integer::roots::bits::<u64>
192
193		#[inline]
194	0	fn log2<T: PrimInt>(x: T) -> u32 {
195	0	debug_assert!(x > T::zero());
196	0	bits::<T>() - 1 - x.leading_zeros()
197	0	} Unexecuted instantiation: num_integer::roots::log2::<u8> Unexecuted instantiation: num_integer::roots::log2::<usize> Unexecuted instantiation: num_integer::roots::log2::<u32> Unexecuted instantiation: num_integer::roots::log2::<u128> Unexecuted instantiation: num_integer::roots::log2::<u16> Unexecuted instantiation: num_integer::roots::log2::<u64>
198
199		/// 128-bit Karatsuba Square Root, using b = 2³²
200		///
201		/// Reference:
202		/// Paul Zimmermann. Karatsuba Square Root. [Research Report] RR-3805, INRIA. 1999, pp.8.
203		/// <https://inria.hal.science/inria-00072854/en/>
204		#[inline]
205	0	fn karatsuba_sqrt(n: u128) -> u128 {
206		// Algorithm SqrtRem(n = a₃b³ + a₂b² + a₁b + a₀)
207		// Input: 0 ≤ aᵢ < b with a₃ ≥ b/4
208		// Output: (s,r) such that s² ≤ n = s² + r < (s+1)²
209	0	debug_assert!(n.leading_zeros() < 2);
210	0	let a0 = n as u32 as u128;
211	0	let a1 = (n >> 32) as u32 as u128;
212	0	let a23 = n >> 64;
213
214		// (s',r') ← SqrtRem(a₃b + a₂)
215	0	let s1 = (a23 as u64).sqrt() as u128;
216	0	let r1 = a23 - s1 * s1;
217
218		// (q,u) ← DivRem(r'b + a₁, 2s')
219	0	let (q, u) = ((r1 << 32) \| a1).div_rem(&(2 * s1));
220
221		// s ← s'b + q
222	0	let mut s = (s1 << 32) + q;
223
224		// r ← ub + a₀ - q²
225		// if r < 0 then
226		// r ← r + 2s - 1
227		// s ← s - 1
228		//
229		// but to avoid negatives, we compare and adjust before subtraction,
230		// and in this case we don't care about the actual remainder.
231	0	if ((u << 32) \| a0) < q * q {
232	0	s -= 1;
233	0	}
234	0	s
235	0	}
236
237		macro_rules! unsigned_roots {
238		($T:ident) => {
239		impl Roots for $T {
240		#[inline]
241	0	fn nth_root(&self, n: u32) -> Self {
242	0	fn go(a: $T, n: u32) -> $T {
243		// Specialize small roots
244	0	match n {
245	0	0 => panic!("can't find a root of degree 0!"),
246	0	1 => return a,
247	0	2 => return a.sqrt(),
248	0	3 => return a.cbrt(),
249	0	_ => (),
250		}
251
252		// The root of values less than 2ⁿ can only be 0 or 1.
253	0	if bits::<$T>() <= n \|\| a < (1 << n) {
254	0	return (a > 0) as $T;
255	0	}
256
257	0	if bits::<$T>() > 64 {
258		// 128-bit division is slow, so do a bitwise `nth_root` until it's small enough.
259	0	return if a <= core::u64::MAX as $T {
260	0	(a as u64).nth_root(n) as $T
261		} else {
262	0	let lo = (a >> n).nth_root(n) << 1;
263	0	let hi = lo + 1;
264		// 128-bit `checked_mul` also involves division, but we can't always
265		// compute `hiⁿ` without risking overflow. Try to avoid it though...
266	0	if hi.next_power_of_two().trailing_zeros() * n >= bits::<$T>() {
267	0	match checked_pow(hi, n as usize) {
268	0	Some(x) if x <= a => hi,
269	0	_ => lo,
270		}
271		} else {
272	0	if hi.pow(n) <= a {
273	0	hi
274		} else {
275	0	lo
276		}
277		}
278		};
279	0	}
280
281		#[cfg(feature = "std")]
282		#[inline]
283	0	fn guess(x: $T, n: u32) -> $T {
284		// for smaller inputs, `f64` doesn't justify its cost.
285	0	if bits::<$T>() <= 32 \|\| x <= core::u32::MAX as $T {
286	0	1 << ((log2(x) + n - 1) / n)
287		} else {
288	0	((x as f64).ln() / f64::from(n)).exp() as $T
289		}
290	0	} Unexecuted instantiation: <u8 as num_integer::roots::Roots>::nth_root::go::guess Unexecuted instantiation: <u16 as num_integer::roots::Roots>::nth_root::go::guess Unexecuted instantiation: <u32 as num_integer::roots::Roots>::nth_root::go::guess Unexecuted instantiation: <u64 as num_integer::roots::Roots>::nth_root::go::guess Unexecuted instantiation: <u128 as num_integer::roots::Roots>::nth_root::go::guess Unexecuted instantiation: <usize as num_integer::roots::Roots>::nth_root::go::guess
291
292		#[cfg(not(feature = "std"))]
293		#[inline]
294		fn guess(x: $T, n: u32) -> $T {
295		1 << ((log2(x) + n - 1) / n)
296		}
297
298		// https://en.wikipedia.org/wiki/Nth_root_algorithm
299	0	let n1 = n - 1;
300	0	let next = \|x: $T\| {
301	0	let y = match checked_pow(x, n1 as usize) {
302	0	Some(ax) => a / ax,
303	0	None => 0,
304		};
305	0	(y + x * n1 as $T) / n as $T
306	0	}; Unexecuted instantiation: <u8 as num_integer::roots::Roots>::nth_root::go::{closure#0} Unexecuted instantiation: <u16 as num_integer::roots::Roots>::nth_root::go::{closure#0} Unexecuted instantiation: <u32 as num_integer::roots::Roots>::nth_root::go::{closure#0} Unexecuted instantiation: <u64 as num_integer::roots::Roots>::nth_root::go::{closure#0} Unexecuted instantiation: <u128 as num_integer::roots::Roots>::nth_root::go::{closure#0} Unexecuted instantiation: <usize as num_integer::roots::Roots>::nth_root::go::{closure#0}
307	0	fixpoint(guess(a, n), next)
308	0	} Unexecuted instantiation: <u8 as num_integer::roots::Roots>::nth_root::go Unexecuted instantiation: <u16 as num_integer::roots::Roots>::nth_root::go Unexecuted instantiation: <u32 as num_integer::roots::Roots>::nth_root::go Unexecuted instantiation: <u64 as num_integer::roots::Roots>::nth_root::go Unexecuted instantiation: <u128 as num_integer::roots::Roots>::nth_root::go Unexecuted instantiation: <usize as num_integer::roots::Roots>::nth_root::go
309	0	go(*self, n)
310	0	} Unexecuted instantiation: <u64 as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <u8 as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <u16 as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <u32 as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <u64 as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <u128 as num_integer::roots::Roots>::nth_root Unexecuted instantiation: <usize as num_integer::roots::Roots>::nth_root
311
312		#[inline]
313	0	fn sqrt(&self) -> Self {
314	0	fn go(a: $T) -> $T {
315	0	if bits::<$T>() > 64 {
316		// 128-bit division is slow in the Babylonian method,
317		// so use 64-bit sqrt and Karatsuba if needed.
318	0	return if a <= core::u64::MAX as $T {
319	0	(a as u64).sqrt() as $T
320		} else {
321	0	let shift = a.leading_zeros() / 2;
322	0	let n = a << (shift * 2);
323	0	(karatsuba_sqrt(n as u128) >> shift) as $T
324		};
325	0	}
326
327	0	if a < 4 {
328	0	return (a > 0) as $T;
329	0	}
330
331		#[cfg(feature = "std")]
332		#[inline]
333	0	fn guess(x: $T) -> $T {
334	0	(x as f64).sqrt() as $T
335	0	} Unexecuted instantiation: <u8 as num_integer::roots::Roots>::sqrt::go::guess Unexecuted instantiation: <u16 as num_integer::roots::Roots>::sqrt::go::guess Unexecuted instantiation: <u32 as num_integer::roots::Roots>::sqrt::go::guess Unexecuted instantiation: <u64 as num_integer::roots::Roots>::sqrt::go::guess Unexecuted instantiation: <u128 as num_integer::roots::Roots>::sqrt::go::guess Unexecuted instantiation: <usize as num_integer::roots::Roots>::sqrt::go::guess
336
337		#[cfg(not(feature = "std"))]
338		#[inline]
339		fn guess(x: $T) -> $T {
340		1 << ((log2(x) + 1) / 2)
341		}
342
343		// https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
344	0	let next = \|x: $T\| (a / x + x) >> 1; Unexecuted instantiation: <u8 as num_integer::roots::Roots>::sqrt::go::{closure#0} Unexecuted instantiation: <u16 as num_integer::roots::Roots>::sqrt::go::{closure#0} Unexecuted instantiation: <u32 as num_integer::roots::Roots>::sqrt::go::{closure#0} Unexecuted instantiation: <u64 as num_integer::roots::Roots>::sqrt::go::{closure#0} Unexecuted instantiation: <u128 as num_integer::roots::Roots>::sqrt::go::{closure#0} Unexecuted instantiation: <usize as num_integer::roots::Roots>::sqrt::go::{closure#0}
345	0	fixpoint(guess(a), next)
346	0	} Unexecuted instantiation: <u8 as num_integer::roots::Roots>::sqrt::go Unexecuted instantiation: <u16 as num_integer::roots::Roots>::sqrt::go Unexecuted instantiation: <u32 as num_integer::roots::Roots>::sqrt::go Unexecuted instantiation: <u64 as num_integer::roots::Roots>::sqrt::go Unexecuted instantiation: <u128 as num_integer::roots::Roots>::sqrt::go Unexecuted instantiation: <usize as num_integer::roots::Roots>::sqrt::go
347	0	go(*self)
348	0	} Unexecuted instantiation: <u64 as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <u8 as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <u16 as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <u32 as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <u64 as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <u128 as num_integer::roots::Roots>::sqrt Unexecuted instantiation: <usize as num_integer::roots::Roots>::sqrt
349
350		#[inline]
351	0	fn cbrt(&self) -> Self {
352	0	fn go(a: $T) -> $T {
353	0	if bits::<$T>() > 64 {
354		// 128-bit division is slow, so do a bitwise `cbrt` until it's small enough.
355	0	return if a <= core::u64::MAX as $T {
356	0	(a as u64).cbrt() as $T
357		} else {
358	0	let lo = (a >> 3u32).cbrt() << 1;
359	0	let hi = lo + 1;
360	0	if hi * hi * hi <= a {
361	0	hi
362		} else {
363	0	lo
364		}
365		};
366	0	}
367
368	0	if bits::<$T>() <= 32 {
369		// Implementation based on Hacker's Delight `icbrt2`
370	0	let mut x = a;
371	0	let mut y2 = 0;
372	0	let mut y = 0;
373	0	let smax = bits::<$T>() / 3;
374	0	for s in (0..smax + 1).rev() {
375	0	let s = s * 3;
376	0	y2 *= 4;
377	0	y *= 2;
378	0	let b = 3 * (y2 + y) + 1;
379	0	if x >> s >= b {
380	0	x -= b << s;
381	0	y2 += 2 * y + 1;
382	0	y += 1;
383	0	}
384		}
385	0	return y;
386	0	}
387
388	0	if a < 8 {
389	0	return (a > 0) as $T;
390	0	}
391	0	if a <= core::u32::MAX as $T {
392	0	return (a as u32).cbrt() as $T;
393	0	}
394
395		#[cfg(feature = "std")]
396		#[inline]
397	0	fn guess(x: $T) -> $T {
398	0	(x as f64).cbrt() as $T
399	0	} Unexecuted instantiation: <u8 as num_integer::roots::Roots>::cbrt::go::guess Unexecuted instantiation: <u16 as num_integer::roots::Roots>::cbrt::go::guess Unexecuted instantiation: <u32 as num_integer::roots::Roots>::cbrt::go::guess Unexecuted instantiation: <u64 as num_integer::roots::Roots>::cbrt::go::guess Unexecuted instantiation: <u128 as num_integer::roots::Roots>::cbrt::go::guess Unexecuted instantiation: <usize as num_integer::roots::Roots>::cbrt::go::guess
400
401		#[cfg(not(feature = "std"))]
402		#[inline]
403		fn guess(x: $T) -> $T {
404		1 << ((log2(x) + 2) / 3)
405		}
406
407		// https://en.wikipedia.org/wiki/Cube_root#Numerical_methods
408	0	let next = \|x: $T\| (a / (x * x) + x * 2) / 3; Unexecuted instantiation: <u8 as num_integer::roots::Roots>::cbrt::go::{closure#0} Unexecuted instantiation: <u16 as num_integer::roots::Roots>::cbrt::go::{closure#0} Unexecuted instantiation: <u32 as num_integer::roots::Roots>::cbrt::go::{closure#0} Unexecuted instantiation: <u64 as num_integer::roots::Roots>::cbrt::go::{closure#0} Unexecuted instantiation: <u128 as num_integer::roots::Roots>::cbrt::go::{closure#0} Unexecuted instantiation: <usize as num_integer::roots::Roots>::cbrt::go::{closure#0}
409	0	fixpoint(guess(a), next)
410	0	} Unexecuted instantiation: <u8 as num_integer::roots::Roots>::cbrt::go Unexecuted instantiation: <u16 as num_integer::roots::Roots>::cbrt::go Unexecuted instantiation: <u32 as num_integer::roots::Roots>::cbrt::go Unexecuted instantiation: <u64 as num_integer::roots::Roots>::cbrt::go Unexecuted instantiation: <u128 as num_integer::roots::Roots>::cbrt::go Unexecuted instantiation: <usize as num_integer::roots::Roots>::cbrt::go
411	0	go(*self)
412	0	} Unexecuted instantiation: <u64 as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <u8 as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <u16 as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <u32 as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <u64 as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <u128 as num_integer::roots::Roots>::cbrt Unexecuted instantiation: <usize as num_integer::roots::Roots>::cbrt
413		}
414		};
415		}
416
417		unsigned_roots!(u8);
418		unsigned_roots!(u16);
419		unsigned_roots!(u32);
420		unsigned_roots!(u64);
421		unsigned_roots!(u128);
422		unsigned_roots!(usize);