// ---------------------------------------------------------------------------
// Correctly-rounded integer kernels for the mathematical functions
// (sqrt / exp / ln / log10 / power).
//
// They work on the `BigInt` coefficient directly — rather
// than threading a variable-precision `Decimal` through a Taylor loop — gives
// results that are correctly rounded to the requested number of places. The
// transcendental kernels compute with an error of at most 1 in the last
// computed digit and handle operands of any magnitude in O(1) range reduction
// (the exponent enters as `e * log(10)`, never as a halving/doubling loop).
//
// MoonBit's `BigInt` `>>` is an arithmetic (floor) shift and `land` is
// two's-complement bitwise-and, which is what these routines need; only `/`
// and `%` need care (they truncate toward zero, while the fixed-point algebra
// below assumes floor semantics), which `floor_div` / `div_nearest` correct for.
// Iteration is written
// with MoonBit's tail-recursive `for`-binder loops rather than mutable state.
// ---------------------------------------------------------------------------

///|
/// Absolute value of a `BigInt`.
fn abs_big(b : BigInt) -> BigInt {
  if b < 0N {
    -b
  } else {
    b
  }
}

///|
/// Number of decimal digits in the magnitude `|b|` (zero counts as one digit).
fn bigint_digits(b : BigInt) -> Int32 {
  digit_count(abs_big(b))
}

///|
/// Bit length of the magnitude `|n|` (zero -> 0).
fn nbits(n : BigInt) -> Int32 {
  n.bit_length()
}

///|
/// Floor division `floor(a / b)` for `b > 0`. MoonBit's `/` truncates toward
/// zero, so it differs from the floor only when `a < 0`, which this corrects.
fn floor_div(a : BigInt, b : BigInt) -> BigInt {
  let q = a / b
  // Reuse the quotient to recover the truncated remainder (a - q*b) rather
  // than running a second full division for `a % b`.
  if a - q * b < 0N {
    q - 1N
  } else {
    q
  }
}

///|
/// Closest integer to `a / b` for `b > 0`, rounding to even on a tie.
fn div_nearest(a : BigInt, b : BigInt) -> BigInt {
  let q = floor_div(a, b)
  let r = a - q * b // floor remainder, 0 <= r < b
  if ((r << 1) + q.land(1N)).compare(b) > 0 {
    q + 1N
  } else {
    q
  }
}

///|
/// Closest integer to `x / 2^shift` (shift >= 0), rounding to even on a tie.
fn rshift_nearest(x : BigInt, shift : Int32) -> BigInt {
  let b = 1N << shift
  let q = x >> shift
  if ((x.land(b - 1N) << 1) + q.land(1N)).compare(b) > 0 {
    q + 1N
  } else {
    q
  }
}

///|
/// GDA `sqrt` / IEEE-754 squareRoot.
///
/// * sqrt(NaN): propagates.
/// * sqrt(+Inf): +Inf.
/// * sqrt(-Inf), sqrt(-x) for non-zero finite x: NaN + Invalid_operation.
/// * sqrt(±0): ±0 with the GDA "ideal exponent" `floor(x.exponent / 2)`.
/// * sqrt(finite positive): Newton-style integer sqrt, half-even rounded
///   to `precision` digits.
pub fn Decimal::sqrt(self : Decimal, ctx : Context) -> (Decimal, Flags) {
  let ctx = { ..ctx, flags: Flags::new(), }
  (self.sqrt_raw(ctx), ctx.flags)
}

///|
/// Internal worker for `sqrt`: returns the value, raising into `ctx.flags`.
fn Decimal::sqrt_raw(self : Decimal, ctx : Context) -> Decimal {
  match self.class {
    SNaN => quiet_snan(self, ctx)
    QNaN => self
    Infinity => if self.negative { invalid_nan(ctx) } else { self }
    Finite =>
      if self.coefficient.is_zero() {
        let ideal = floor_div2(self.exponent)
        ({ ..self, exponent: ideal, } : Decimal).finalize_raw(ctx)
      } else if self.negative {
        invalid_nan(ctx)
      } else {
        sqrt_finite(self, ctx)
      }
  }
}

///|
/// Finite positive sqrt body:
///
/// 1. Scale the coefficient so the integer square root lands at exactly
///    `precision + 1` digits — multiply by `10^(2·shift)` (or divide, noting
///    whether anything was lost) and halve the exponent. The parity dance on
///    the input exponent keeps the result exponent an integer.
/// 2. Take the integer square root of the scaled coefficient.
/// 3. If the result is exact, scale it straight back to the ideal exponent
///    `floor(x.exp / 2)`. Otherwise nudge an integer-sqrt that lands on a
///    multiple of 5 up by one — this guarantees the subsequent half-even
///    round can never be fooled by a false tie (the true root is never
///    exactly halfway, so a residue digit of 0 or 5 must round up).
/// 4. `finalize` under half-even (sqrt always rounds half-even, regardless of
///    the context's rounding mode) to drop the guard digit and raise
///    `Inexact` / `Rounded`.
fn sqrt_finite(x : Decimal, ctx : Context) -> Decimal {
  if ctx.precision <= 0 {
    // sqrt at unbounded precision is generally inexact (sqrt(2), sqrt(3),
    // ...) — declare Invalid_operation rather than spin forever. Callers
    // that want exact sqrt must specify precision.
    return invalid_nan(ctx)
  }
  let prec = ctx.precision + 1
  let exp = x.exponent
  let coef = x.coefficient
  let mut e = floor_div2(exp)
  // Odd exponent: fold one factor of 10 into the coefficient so the remaining
  // exponent is even and `e = exp / 2` exactly. The digit-length estimate `l`
  // is then half the (padded) coefficient width.
  let mut c = coef
  let l = if exp % 2 != 0 {
    c = c * 10N
    digit_count(coef) / 2 + 1
  } else {
    (digit_count(coef) + 1) / 2
  }
  let shift = prec - l
  let exact_pre = if shift >= 0 {
    c = c * pow10(2 * shift)
    true
  } else {
    let divisor = pow10(-2 * shift)
    let r = c % divisor
    c = c / divisor
    r.is_zero()
  }
  e = e - shift
  let mut n = isqrt(c)
  let exact = exact_pre && n * n == c
  if exact {
    n = if shift >= 0 { n / pow10(shift) } else { n * pow10(-shift) }
    e = e + shift
  } else if (n % 5N).is_zero() {
    n = n + 1N
  }
  // sqrt always rounds half-even; finalize applies precision + exponent-range
  // rules and raises Inexact / Rounded. Flags accumulate into the shared
  // Flags object, so they still surface on the caller's context.
  let he_ctx = { ..ctx, rounding: HalfEven, }
  Decimal::finalize_raw(
    { class: Finite, negative: false, coefficient: n, exponent: e, },
    he_ctx,
  )
}

///|
/// Integer square root via Newton's method, returning `floor(sqrt(n))`.
/// Convergence is quadratic, so even for thousand-digit inputs the loop
/// terminates in a few dozen iterations.
fn isqrt(n : BigInt) -> BigInt {
  if n < 2N {
    return n
  }
  // Newton from the overestimate 10^ceil(digit_count(n)/2): the iterates
  // decrease monotonically to floor(sqrt(n)), so we stop once a step no
  // longer decreases. (A too-large start is safe; an undershoot would
  // oscillate.)
  let d = digit_count(n)
  for x = pow10(d / 2 + 1) {
    let y = (x + n / x) >> 1
    if y >= x {
      break x
    } else {
      continue y
    }
  }
}

///|
/// `floor(n / 2)` on a possibly-negative `Int`. The built-in `/` truncates
/// toward zero, which gives the wrong result for negative odd inputs; we
/// adjust by one when needed so the GDA "ideal exponent"
/// (`floor(x.exponent / 2)`) is computed correctly even for `sqrt(0E-3)`.
fn floor_div2(n : Int32) -> Int32 {
  if n >= 0 {
    n / 2
  } else {
    -((-n + 1) / 2)
  }
}

///|
/// Closest integer to `sqrt(n)` (n > 0), Newton-refined from `a0 > 0`.
fn sqrt_nearest(n : BigInt, a0 : BigInt) -> BigInt {
  for a = a0, b = 0N {
    if a != b {
      continue (a - floor_div(-n, a)) >> 1, a
    } else {
      break a
    }
  }
}

///|
/// Number of terms for the fixed-point Taylor series at precision `M` (with
/// `digits = len(str(M))`) and reduction parameter `L`: `ceil(10*digits/(3L))`.
fn taylor_terms(digits : Int32, l : Int32) -> Int32 {
  (10 * digits + 3 * l - 1) / (3 * l)
}

///|
/// Integer approximation to `M * log(x / M)` (x, M > 0). For `L = 8` and
/// `0.1 <= x/M <= 10` the absolute error is at most 22.
fn ilog(x : BigInt, m : BigInt, l : Int32) -> BigInt {
  // Argument reduction via `log1p(y) = 2*log1p(y/(1+sqrt(1+y)))`, in
  // fixed-point: `y` represents `2^R * y_real * M` after R reductions.
  let (y, r) = for y = x - m, r = 0 {
    if (r <= l && (abs_big(y) << (l - r)).compare(m) >= 0) ||
      (r > l && (abs_big(y) >> (r - l)).compare(m) >= 0) {
      let s = sqrt_nearest(m * (m + rshift_nearest(y, r)), m)
      continue div_nearest((m * y) << 1, m + s), r + 1
    } else {
      break (y, r)
    }
  }
  // Taylor series for log1p, evaluated by Horner over T terms.
  let t = taylor_terms(bigint_digits(m), l)
  let yshift = rshift_nearest(y, r)
  let w = for k = t - 1, w = div_nearest(m, BigInt::from_int(t)) {
    if k > 0 {
      continue k - 1,
        div_nearest(m, BigInt::from_int(k)) - div_nearest(yshift * w, m)
    } else {
      break w
    }
  }
  div_nearest(w * y, m)
}

///|
/// Integer approximation to `M * exp(x / M)` (M > 0, x/M small). For
/// `0 <= x/M <= 2.4` the absolute error is bounded by 60.
fn iexp(x : BigInt, m : BigInt, l : Int32) -> BigInt {
  // Reduce by a power R of 2 so |x/2^R/M| < 2^-L, sum the expm1 Taylor series,
  // then square back up R times via `expm1(2x) = expm1(x)*(expm1(x)+2)`.
  let r = nbits(floor_div(x << l, m))
  let t = taylor_terms(bigint_digits(m), l)
  let mshift0 = m << r
  let y0 = for i = t - 1, y = div_nearest(x, BigInt::from_int(t)) {
    if i > 0 {
      continue i - 1,
        div_nearest(x * (mshift0 + y), mshift0 * BigInt::from_int(i))
    } else {
      break y
    }
  }
  let y = for k = r - 1, y = y0 {
    if k >= 0 {
      let mshift = m << (k + 2)
      continue k - 1, div_nearest(y * (y + mshift), mshift)
    } else {
      break y
    }
  }
  m + y
}

///|
/// True iff the last `count` characters of `s` are all the digit '0'.
fn suffix_all_zeros(s : String, count : Int32) -> Bool {
  let n = s.length()
  for i = n - count {
    if i >= n {
      break true
    } else if i >= 0 && s[i].to_int() != 0x30 {
      break false
    } else {
      continue i + 1
    }
  }
}

///|
/// Cache of reliable leading digits of `log(10) = 2.302585...` (truncated,
/// never rounded). Seeded with 47 digits and grown on demand; mirrors
/// grown on demand. Without it, every `dlog` / `dexp` would recompute
/// `log(10)` from scratch — the dominant cost in `power`.
let log10_cache : Ref[String] = {
  val: "23025850929940456840179914546843642076011014886",
}

///|
/// `floor(10^p * log(10))` for `p >= 0` — the digits of `log(10)` needed by
/// `ln` / `log10` / `power`. Served from `log10_cache`, extending it via `ilog`
/// when more digits are wanted (computing until the truncation point is
/// reliable, i.e. the trailing guard digits are not all zero).
fn log10_digits(p : Int32) -> BigInt {
  let cached = log10_cache.val
  if p + 1 > cached.length() {
    let s = for extra = 3 {
      let m = pow10(p + extra + 2)
      // ~ 10^(p+extra) * log(10), i.e. 2.302585... * 10^(p+extra).
      let cand = div_nearest(ilog(10N * m, m, 8), 100N).to_string()
      if suffix_all_zeros(cand, extra) {
        continue extra + 3
      } else {
        break cand
      }
    }
    // Keep all reliable digits: drop trailing zeros and the next digit.
    log10_cache.val = reliable_prefix(s)
  }
  BigInt::from_string(log10_cache.val[0:p + 1].to_owned())
}

///|
/// Strip trailing '0' characters from `s`, then drop one further digit — the
/// remaining prefix is the part of `s` known to be correct.
fn reliable_prefix(s : String) -> String {
  let end = for i = s.length() {
    if i > 0 && s[i - 1].to_int() == 0x30 {
      continue i - 1
    } else {
      break i
    }
  }
  s[0:if end > 0 { end - 1 } else { 0 }].to_owned()
}

///|
/// Integer approximation to `10^p * log(c * 10^e)` (c > 0), error <= 1.
/// Assumes `c * 10^e != 1`. Uses `log(c*10^e) = log(d) + f*log(10)` after
/// writing `c*10^e = d*10^f` with `d` near 1 — so the magnitude `f` is read
/// off directly, never iterated.
fn dlog(c : BigInt, e : Int32, p_in : Int32) -> BigInt {
  let p = p_in + 2
  let l = bigint_digits(c)
  let f = e + l - (if e + l >= 1 { 1 } else { 0 })
  let log_d = if p > 0 {
    let k = e + p - f
    let cc = if k >= 0 { c * pow10(k) } else { div_nearest(c, pow10(-k)) }
    ilog(cc, pow10(p), 8)
  } else {
    0N
  }
  let f_log_ten = if f != 0 {
    let extra = bigint_digits(BigInt::from_int(f)) - 1
    if p + extra >= 0 {
      div_nearest(BigInt::from_int(f) * log10_digits(p + extra), pow10(extra))
    } else {
      0N
    }
  } else {
    0N
  }
  div_nearest(f_log_ten + log_d, 100N)
}

///|
/// Integer approximation to `10^p * log10(c * 10^e)` (c > 0), error <= 1.
/// Assumes `c * 10^e != 1`.
fn dlog10(c : BigInt, e : Int32, p_in : Int32) -> BigInt {
  let p = p_in + 2
  let l = bigint_digits(c)
  let f = e + l - (if e + l >= 1 { 1 } else { 0 })
  if p > 0 {
    let m = pow10(p)
    let k = e + p - f
    let cc = if k >= 0 { c * pow10(k) } else { div_nearest(c, pow10(-k)) }
    let log_d = div_nearest(ilog(cc, m, 8) * m, log10_digits(p))
    let log_tenpower = BigInt::from_int(f) * m
    div_nearest(log_tenpower + log_d, 100N)
  } else {
    div_nearest(div_nearest(BigInt::from_int(f), pow10(-p)), 100N)
  }
}

///|
/// Approximation to `exp(c * 10^e)` with `p` digits of precision. Returns
/// `(d, f)` with `10^(p-1) <= d <= 10^p` and `(d-1)*10^f < exp(c*10^e) <
/// (d+1)*10^f` — i.e. `d` carries an error of at most 1.
fn dexp(c : BigInt, e : Int32, p_in : Int32) -> (BigInt, Int32) {
  let p = p_in + 2
  // extra precision for log(10) = adjusted exponent of c*10^e (if positive).
  let adj = e + bigint_digits(c) - 1
  let extra = if adj > 0 { adj } else { 0 }
  let q = p + extra
  let shift = e + q
  let cshift = if shift >= 0 {
    c * pow10(shift)
  } else {
    floor_div(c, pow10(-shift))
  }
  let logd = log10_digits(q)
  let quot = floor_div(cshift, logd)
  let rem = div_nearest(cshift - quot * logd, pow10(extra))
  let coeff = div_nearest(iexp(rem, pow10(p), 8), 1000N)
  (coeff, quot.to_int() - p + 3)
}

///|
/// Ziv stopping test for a correctly-rounded result: true once `coeff` (a
/// value computed to a few guard digits beyond precision `p`) is far enough
/// from a rounding boundary to round the same way under any mode — i.e. it is
/// not a multiple of half a ulp at `p`. While this is false the caller widens
/// the working precision and recomputes.
fn ziv_roundable(coeff : BigInt, p : Int32) -> Bool {
  !(abs_big(coeff) % (5N * pow10(bigint_digits(coeff) - p - 1))).is_zero()
}

///|
/// Approximation to `x^y` where `x = xc*10^xe > 0` (and != 1) and
/// `y = yc*10^ye != 0`. Returns `(c, e)` with `10^(p-1) <= c <= 10^p` and
/// `(c-1)*10^e < x^y < (c+1)*10^e`.
fn dpower(
  xc : BigInt,
  xe : Int32,
  yc : BigInt,
  ye : Int32,
  p : Int32,
) -> (BigInt, Int32) {
  let b = bigint_digits(yc) + ye
  let lxc = dlog(xc, xe, p + b + 1)
  let shift = ye - b
  let pc = if shift >= 0 {
    lxc * yc * pow10(shift)
  } else {
    div_nearest(lxc * yc, pow10(-shift))
  }
  if pc.is_zero() {
    // Prefer a result that is not exactly 1, so power can round correctly.
    if (bigint_digits(xc) + xe >= 1) == (yc > 0N) {
      (pow10(p - 1) + 1N, 1 - p)
    } else {
      (pow10(p) - 1N, -p)
    }
  } else {
    let (coeff, exp) = dexp(pc, -(p + 1), p + 1)
    (div_nearest(coeff, 10N), exp + 1)
  }
}