//! Integer roots — isqrt and iroot, by digit-recurrence and bracketed search.

/// The integer square root of `n`: the unique `r` with `r*r <= n < (r+1)*(r+1)`,
/// i.e. `r = ⌊√n⌋`. Total over every `u64`; the result is always `<= 2^32 - 1`.
///
/// Computed by the division-free binary digit-recurrence — one result bit per
/// step, most-significant first, walking the perfect-square place values
/// `4^31, 4^30, …, 1`. No multiplication, no division, no `u128`: every
/// intermediate is bounded by `n` or by a place value, and the subtraction is
/// guarded so it never underflows. (The fully symbolic version is the Kani proof.)
///
/// # Examples
///
/// ```
/// use coprime::number::isqrt;
///
/// assert_eq!(isqrt(0), 0);
/// assert_eq!(isqrt(15), 3); // 3² = 9 ≤ 15 < 16 = 4²
/// assert_eq!(isqrt(16), 4);
/// assert_eq!(isqrt(u64::MAX), 4_294_967_295); // 2^32 - 1
/// ```
#[must_use]
pub fn isqrt(n: u64) -> u64 {
    let mut bit: u64 = 1 << 62; // 4^31, the largest perfect-square place ≤ u64::MAX
    let mut x = n; // residual: n minus the square accumulated so far
    let mut r: u64 = 0; // result accumulator
    while bit != 0 {
        let t = r + bit; // candidate contribution (2*r_old + bit)*bit, encoded
        r >>= 1; // shift the running result down one binary place
        if x >= t {
            x -= t; // guarded: never underflows
            r += bit; // set this result bit
        }
        bit >>= 2; // next lower place value (÷4)
    }
    r
}

/// The integer `k`-th root of `n`: the unique `r` with `r^k <= n < (r+1)^k`, i.e.
/// `r = ⌊n^(1/k)⌋`.
/// `iroot(n, 2)` agrees with [`isqrt`]; `iroot(n, 3)` is the integer cube root.
/// Degenerate `k <= 1` returns `n`. Total and overflow-safe: each candidate is
/// tested with `checked_pow`, so a too-large `r^k` counts as `> n` rather than
/// wrapping.
///
/// # Examples
///
/// ```
/// use coprime::number::iroot;
///
/// assert_eq!(iroot(27, 3), 3); // 3³ = 27
/// assert_eq!(iroot(28, 3), 3); // 3³ = 27 ≤ 28 < 64 = 4³
/// assert_eq!(iroot(1_000_000, 3), 100);
/// assert_eq!(iroot(u64::MAX, 2), 4_294_967_295); // = isqrt(u64::MAX)
/// ```
#[must_use]
pub fn iroot(n: u64, k: u32) -> u64 {
    if k <= 1 || n <= 1 {
        return n; // the 1st root is n; 0 and 1 are their own k-th roots
    }
    // `r^k <= n`, overflow as "too big": an overflowing power counts as `> n`.
    let fits = |cand: u64| cand.checked_pow(k).is_some_and(|pk| pk <= n);
    // Bracket the root: grow a power of two until `hi^k > n`, so `(hi/2)^k <= n`.
    // `hi` never reaches `2^63` — the root is `<= 2^(64/k) <= 2^32` for `k >= 2`.
    let mut hi = 1u64;
    while fits(hi) {
        hi *= 2;
    }
    // Binary search `[lo, hi)` for the largest `r` with `r^k <= n`.
    let mut lo = hi / 2;
    while hi - lo > 1 {
        let mid = lo + (hi - lo) / 2;
        if fits(mid) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    lo
}
