dashu_float/

exp.rs

use core::convert::TryInto;

use crate::{
    error::{assert_finite, assert_limited_precision, FpError, FpResult},
    fbig::FBig,
    math::cache::{reborrow_cache, ConstCache},
    repr::{Context, Repr, Word},
    round::Round,
    utils::ceil_usize,
};
use dashu_base::{AbsOrd, Approximation::*, BitTest, DivRemEuclid, EstimatedLog2, Sign};
use dashu_int::IBig;

impl<R: Round, const B: Word> FBig<R, B> {
    /// Raise the floating point number to an integer power.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_base::ParseError;
    /// # use dashu_float::DBig;
    /// # use core::str::FromStr;
    /// let a = DBig::from_str("-1.234")?;
    /// assert_eq!(a.powi(10.into()), DBig::from_str("8.188")?);
    /// # Ok::<(), ParseError>(())
    /// ```
    #[inline]
    pub fn powi(&self, exp: IBig) -> FBig<R, B> {
        self.context.unwrap_fp(self.context.powi(&self.repr, exp))
    }

    /// Raise the floating point number to an floating point power.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_base::ParseError;
    /// # use dashu_float::DBig;
    /// # use core::str::FromStr;
    /// let x = DBig::from_str("1.23")?;
    /// let y = DBig::from_str("-4.56")?;
    /// assert_eq!(x.powf(&y), DBig::from_str("0.389")?);
    /// # Ok::<(), ParseError>(())
    /// ```
    #[inline]
    pub fn powf(&self, exp: &Self) -> Self {
        let context = Context::max(self.context, exp.context);
        context.unwrap_fp(context.powf(&self.repr, &exp.repr, None))
    }

    /// Calculate the exponential function (`eˣ`) on the floating point number.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_base::ParseError;
    /// # use dashu_float::DBig;
    /// # use core::str::FromStr;
    /// let a = DBig::from_str("-1.234")?;
    /// assert_eq!(a.exp(), DBig::from_str("0.2911")?);
    /// # Ok::<(), ParseError>(())
    /// ```
    #[inline]
    pub fn exp(&self) -> FBig<R, B> {
        self.context.unwrap_fp(self.context.exp(&self.repr, None))
    }

    /// Calculate the exponential minus one function (`eˣ-1`) on the floating point number.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_base::ParseError;
    /// # use dashu_float::DBig;
    /// # use core::str::FromStr;
    /// let a = DBig::from_str("-0.1234")?;
    /// assert_eq!(a.exp_m1(), DBig::from_str("-0.11609")?);
    /// # Ok::<(), ParseError>(())
    /// ```
    #[inline]
    pub fn exp_m1(&self) -> FBig<R, B> {
        self.context
            .unwrap_fp(self.context.exp_m1(&self.repr, None))
    }
}

// TODO: give the exact formulation of required guard bits

impl<R: Round> Context<R> {
    /// Raise the floating point number to an integer power under this context.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_base::ParseError;
    /// # use dashu_float::DBig;
    /// # use core::str::FromStr;
    /// use dashu_base::Approximation::*;
    /// use dashu_float::{Context, round::{mode::HalfAway, Rounding::*}};
    ///
    /// let context = Context::<HalfAway>::new(2);
    /// let a = DBig::from_str("-1.234")?;
    /// assert_eq!(context.powi(&a.repr(), 10.into()), Ok(Inexact(DBig::from_str("8.2")?, AddOne)));
    /// # Ok::<(), ParseError>(())
    /// ```
    ///
    /// # Panics
    ///
    /// Panics if the precision is unlimited and the exponent is negative. In this case, the exact
    /// result is likely to have infinite digits.
    pub fn powi<const B: Word>(&self, base: &Repr<B>, exp: IBig) -> FpResult<FBig<R, B>> {
        // TODO: range handling has three known limitations at the exponent extremes:
        // (1) the overflow guard below estimates the result magnitude with an f64 and misclassifies
        // representable boundaries near 2^63; (2) genuine Overflow/Underflow is unwrapped mode-blindly
        // to ±inf / signed zero; (3) the negative-exponent reciprocal path can panic. None affects
        // ordinary inputs; fixing requires mode-aware range saturation.
        if base.is_infinite() {
            return Err(FpError::InfiniteInput);
        }

        let (exp_sign, exp) = exp.into_parts();
        if exp_sign == Sign::Negative {
            // if the exponent is negative, then negate the exponent
            // note that do the inverse at last requires less guard bits
            assert_limited_precision(self.precision); // TODO: we can allow this if the inverse is exact (only when significand is one?)

            let guard_bits = self.precision.bit_len() * 2; // heuristic
            let rev_context = Context::<R::Reverse>::new(self.precision + guard_bits);
            let pow = rev_context.unwrap_fp(rev_context.powi(base, exp.into()));
            let inv = rev_context.unwrap_fp_repr(rev_context.repr_div(Repr::one(), pow.repr));
            let repr = self.repr_round(inv);
            return Ok(repr.map(|v| FBig::new(v, *self)));
        }
        if exp.is_zero() {
            return Ok(Exact(FBig::ONE));
        } else if exp.is_one() {
            let repr = self.repr_round_ref(base);
            return Ok(repr.map(|v| FBig::new(v, *self)));
        }

        // Guard against exponent overflow/underflow for astronomically large results.
        // The result magnitude has log2 ≈ exp·log2(base); if that leaves the isize
        // exponent range, return ±inf (|base|>1) or signed 0 (|base|<1) instead of
        // overflowing the exponent mid-computation.
        //
        // Use the *bounds* of log2(base), never the point estimate `log2_est`: when
        // base is very close to 1 (a large significand with a large negative exponent),
        // log2(base) is the difference of two ~1e3-magnitude terms and suffers
        // catastrophic cancellation — `log2_est` returns ~1e-4 of f32 noise rather than
        // ~0. Scaled by a large exponent that noise crosses the overflow threshold,
        // which on 32-bit is only isize::MAX·log2(B) ≈ 7e9 (vs ≈3e19 on 64-bit), so the
        // guard fires spuriously and returns ±inf — see issue #95. The bounds are
        // derived from the exact significand bit length, so they don't cancel. Declare
        // overflow only on the lower bound (no false positives) and underflow only on
        // the upper bound (no false underflows); anything in between is computed.
        let (base_log2_lb, base_log2_ub) = base.log2_bounds();
        let base_log2_lb = base_log2_lb as f64;
        let base_log2_ub = base_log2_ub as f64;
        let threshold = (isize::MAX as f64) * (B.log2_est() as f64);
        let exp_f64 = i64::try_from(&exp).ok().map(|e| e as f64);
        let overflows = match exp_f64 {
            Some(e) => e * base_log2_lb > threshold,
            None => base_log2_lb > 0.0, // exp doesn't fit i64: overflows iff base > 1
        };
        if overflows {
            return Err(FpError::Overflow(if base.sign() == Sign::Negative {
                Sign::Negative
            } else {
                Sign::Positive
            }));
        }
        let underflows = !base.significand.is_zero()
            && match exp_f64 {
                Some(e) => e * base_log2_ub < -threshold,
                None => base_log2_ub < 0.0, // exp doesn't fit i64: underflows iff base < 1
            };
        if underflows {
            // |base| < 1 and exponent huge → underflow to signed zero
            let underflow_sign = if base.sign() == Sign::Negative && exp.bit(0) {
                Sign::Negative
            } else {
                Sign::Positive
            };
            return Err(FpError::Underflow(underflow_sign));
        }

        let work_context = if self.is_limited() {
            // increase working precision when the exponent is large
            let guard_digits = exp.bit_len() + self.precision.bit_len(); // heuristic
            Context::<R>::new(self.precision + guard_digits)
        } else {
            Context::<R>::new(0)
        };

        // binary exponentiation from left to right
        let mut p = exp.bit_len() - 2;
        let mut res = work_context.unwrap_fp(work_context.sqr(base));
        loop {
            if exp.bit(p) {
                res = work_context.unwrap_fp(work_context.mul(res.repr(), base));
            }
            if p == 0 {
                break;
            }
            p -= 1;
            res = work_context.unwrap_fp(work_context.sqr(res.repr()));
        }

        Ok(res.with_precision(self.precision))
    }

    /// Raise the floating point number to an floating point power under this context.
    ///
    /// Note that this method will not rely on [FBig::powi] even if the `exp` is actually an integer.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_base::ParseError;
    /// # use dashu_float::DBig;
    /// # use core::str::FromStr;
    /// use dashu_base::Approximation::*;
    /// use dashu_float::{Context, round::{mode::HalfAway, Rounding::*}};
    ///
    /// let context = Context::<HalfAway>::new(2);
    /// let x = DBig::from_str("1.23")?;
    /// let y = DBig::from_str("-4.56")?;
    /// assert_eq!(context.powf(&x.repr(), &y.repr(), None), Ok(Inexact(DBig::from_str("0.39")?, AddOne)));
    /// # Ok::<(), ParseError>(())
    /// ```
    ///
    /// # Panics
    ///
    /// Panics if the precision is unlimited.
    pub fn powf<const B: Word>(
        &self,
        base: &Repr<B>,
        exp: &Repr<B>,
        mut cache: Option<&mut ConstCache>,
    ) -> FpResult<FBig<R, B>> {
        if base.is_infinite() || exp.is_infinite() {
            return Err(FpError::InfiniteInput);
        }
        assert_limited_precision(self.precision); // TODO: we can allow it if exp is integer

        // shortcuts
        if exp.is_pos_zero() || exp.is_neg_zero() {
            // pow(x, ±0) = 1 for any base (IEEE 754 §9.2.1); `-0` is numerically zero, so it
            // must take the same shortcut as `+0` (otherwise a negative base falls through to
            // the OutOfDomain path below).
            return Ok(Exact(FBig::ONE));
        } else if exp.is_one() {
            let repr = self.repr_round_ref(base);
            return Ok(repr.map(|v| FBig::new(v, *self)));
        } else if base.significand.is_zero() {
            // With a *float* exponent the result on a zero base is the positive one — this
            // matches the common float-pow convention (e.g. CPython: `(-0.0) ** y == 0.0`),
            // which doesn't track the parity of the exponent:
            //   pow(±0, y > 0) = +0,    pow(±0, y < 0) = +inf.
            // For the sign-correct result (e.g. `pow(-0, odd) = -0`), use the integer-exponent
            // [`powi`](Context::powi). Short-circuiting here also avoids the negative-base path.
            return Ok(Exact(if exp.sign() == Sign::Negative {
                FBig::new(Repr::infinity(), *self)
            } else {
                FBig::ZERO
            }));
        }
        if base.sign() == Sign::Negative {
            // TODO: we should allow negative base when exp is an integer
            return Err(FpError::OutOfDomain);
        }

        // x^y = exp(y*ln(x)), use a simple rule for guard bits
        let guard_digits = 10 + ceil_usize(self.precision.log2_est());
        let work_context = Context::<R>::new(self.precision + guard_digits);

        // ln and exp each consult/extend the shared cache; reborrows are sequential.
        let ln_val = work_context.unwrap_fp(work_context.ln(base, reborrow_cache(&mut cache)));
        let mul_val = work_context.unwrap_fp(work_context.mul(ln_val.repr(), exp));
        let exp_val =
            work_context.unwrap_fp(work_context.exp(mul_val.repr(), reborrow_cache(&mut cache)));
        Ok(exp_val.with_precision(self.precision))
    }

    /// Calculate the exponential function (`eˣ`) on the floating point number under this context.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_base::ParseError;
    /// # use dashu_float::DBig;
    /// # use core::str::FromStr;
    /// use dashu_base::Approximation::*;
    /// use dashu_float::{Context, round::{mode::HalfAway, Rounding::*}};
    ///
    /// let context = Context::<HalfAway>::new(2);
    /// let a = DBig::from_str("-1.234")?;
    /// assert_eq!(context.exp(&a.repr(), None), Ok(Inexact(DBig::from_str("0.29")?, NoOp)));
    /// # Ok::<(), ParseError>(())
    /// ```
    #[inline]
    pub fn exp<const B: Word>(
        &self,
        x: &Repr<B>,
        cache: Option<&mut ConstCache>,
    ) -> FpResult<FBig<R, B>> {
        if x.is_infinite() {
            return Ok(Exact(FBig::new(
                match x.sign() {
                    Sign::Positive => Repr::infinity(),
                    Sign::Negative => Repr::zero(),
                },
                *self,
            )));
        }
        self.exp_internal(x, false, cache)
    }

    /// Calculate the exponential minus one function (`eˣ-1`) on the floating point number under this context.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_base::ParseError;
    /// # use dashu_float::DBig;
    /// # use core::str::FromStr;
    /// use dashu_base::Approximation::*;
    /// use dashu_float::{Context, round::{mode::HalfAway, Rounding::*}};
    ///
    /// let context = Context::<HalfAway>::new(2);
    /// let a = DBig::from_str("-0.1234")?;
    /// assert_eq!(context.exp_m1(&a.repr(), None), Ok(Inexact(DBig::from_str("-0.12")?, SubOne)));
    /// # Ok::<(), ParseError>(())
    /// ```
    #[inline]
    pub fn exp_m1<const B: Word>(
        &self,
        x: &Repr<B>,
        cache: Option<&mut ConstCache>,
    ) -> FpResult<FBig<R, B>> {
        if x.is_infinite() {
            return match x.sign() {
                Sign::Positive => Ok(Exact(FBig::new(Repr::infinity(), *self))),
                Sign::Negative => Ok(Exact(-FBig::ONE)), // exp_m1(−∞) = −1
            };
        }
        self.exp_internal(x, true, cache)
    }

    // TODO: change reduction to (x - s log2) / 2ⁿ, so that the final powering is always base 2, and doesn't depends on powi.
    //       the powering exp(r)^(2ⁿ) could be optimized by noticing (1+x)^2 - 1 = x^2 + 2x
    //       consider this change after having a benchmark

    fn exp_internal<const B: Word>(
        &self,
        x: &Repr<B>,
        minus_one: bool,
        mut cache: Option<&mut ConstCache>,
    ) -> FpResult<FBig<R, B>> {
        assert_finite(x);
        let input_sign = x.sign();

        if x.significand.is_zero() {
            // exp(±0) = 1; exp_m1(±0) = ±0 (IEEE 754 §9.2.1 preserves the sign of zero).
            // These exact results need no rounding, so handle them before the
            // limited-precision assertion: a precision-0 (unlimited) FBig such as the
            // one produced by `try_from(0.0)` must still compute exp/exp_m1 exactly.
            return match minus_one {
                false => Ok(Exact(FBig::ONE)),
                true => {
                    let zero = if input_sign == Sign::Negative {
                        FBig::new(Repr::neg_zero(), Context::new(0))
                    } else {
                        FBig::ZERO
                    };
                    Ok(Exact(zero))
                }
            };
        }

        assert_limited_precision(self.precision);

        // A simple algorithm:
        // - let r = (x - s logB) / Bⁿ, where s = floor(x / logB), such that r < B⁻ⁿ.
        // - if the target precision is p digits, then there're only about p/m terms in Tyler series
        // - finally, exp(x) = Bˢ * exp(r)^(Bⁿ)
        // - the optimal n is √p as given by MPFR

        // Maclaurin series: exp(r) = 1 + Σ(rⁱ/i!)
        // There will be about p/log_B(r) summations when calculating the series, to prevent
        // loss of significance, we need about log_B(p) guard digits.
        let series_guard_digits = ceil_usize(self.precision.log2_est() / B.log2_est()) + 2;

        // Reduction power: the series value is later raised to Bⁿ, which amplifies its
        // relative error by a factor of Bⁿ. So the series (and the squarings) must carry
        // about n extra base-B digits for the result to come out correct to p digits. We
        // use 2n for safety — this mirrors MPFR's working precision q = precy + 2·K + …
        // (K ≈ √precy is MPFR's squaring count, the analogue of our n). The log_B(p)
        // summation/squaring rounding terms are already covered by series_guard_digits.
        let n = 1usize << (self.precision.bit_len() / 2);
        let pow_guard_digits = 2 * n;
        let work_precision;

        // When minus_one is true and |x| < 1/B, the input is fed into the Maclaurin series without scaling
        let no_scaling = minus_one && x.log2_est() < -B.log2_est();
        let (s, n, r) = if no_scaling {
            // if minus_one is true and x is already small (x < 1/B),
            // then directly evaluate the Maclaurin series without scaling
            if x.sign() == Sign::Negative {
                // extra digits are required to prevent cancellation during the summation
                work_precision = self.precision + 2 * series_guard_digits;
            } else {
                work_precision = self.precision + series_guard_digits;
            }
            let context = Context::<R>::new(work_precision);
            (0, 0, FBig::new(context.repr_round_ref(x).value(), context))
        } else {
            work_precision = self.precision + series_guard_digits + pow_guard_digits;
            let context = Context::<R>::new(work_precision);
            let x = FBig::new(context.repr_round_ref(x).value(), context);
            let logb = context.ln_base::<B>(reborrow_cache(&mut cache));
            let (s, r) = x.div_rem_euclid(logb);

            let s: isize = match s.try_into() {
                Ok(v) => v,
                Err(_) => {
                    // |floor(x / ln B)| overflows isize — x is astronomically large, so the
                    // result is an infinity (x → +∞) or underflows to the limit (x → −∞).
                    //
                    // TODO: this branch discards the rounding mode. For a huge
                    // *negative* x the true exp(x) is positive but below the exponent range, so
                    // directed Up/Away should return the minimum positive value (and exp_m1 the
                    // value just above -1) rather than +0 / Exact(-1).
                    return if input_sign == Sign::Positive {
                        Err(FpError::Overflow(Sign::Positive))
                    } else if minus_one {
                        Ok(Exact(-FBig::ONE)) // exp_m1(−∞) = −1 (finite)
                    } else {
                        Err(FpError::Underflow(Sign::Positive)) // exp(−∞) = +0
                    };
                }
            };
            (s, n, r)
        };

        let r = r >> n as isize;
        let mut factorial = IBig::ONE;
        let mut pow = r.clone();
        let mut sum = if no_scaling {
            r.clone()
        } else {
            FBig::ONE + &r
        };

        let mut k = 2;
        loop {
            factorial *= k;
            pow *= &r;

            let increase = &pow / &factorial;
            if increase.abs_cmp(&sum.sub_ulp()).is_le() {
                break;
            }
            sum += increase;
            k += 1;
        }

        if no_scaling {
            Ok(sum.with_precision(self.precision))
        } else if minus_one {
            // Power at the series' working precision (it already carries the 2n guard
            // digits that the Bⁿ powering amplifies away). The final "−1" can cancel at
            // most ~1 leading digit here (the |x| < 1/B case is handled by no_scaling),
            // which the same guard digits comfortably absorb.
            let pow_ctx = Context::<R>::new(work_precision);
            let v = pow_ctx.unwrap_fp(pow_ctx.powi(sum.repr(), Repr::<B>::BASE.pow(n).into()));
            Ok(((v << s) - FBig::ONE).with_precision(self.precision))
        } else {
            let pow_ctx = Context::<R>::new(work_precision);
            let v = pow_ctx.unwrap_fp(pow_ctx.powi(sum.repr(), Repr::<B>::BASE.pow(n).into()));
            Ok((v << s).with_precision(self.precision))
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::round::mode;

    #[test]
    fn test_exp_overflow_is_infinity() {
        let ctx = Context::<mode::HalfEven>::new(53);
        // exp(huge) overflows the isize exponent range -> Overflow at Context level.
        // Need x large enough that floor(x/ln2) > isize::MAX, i.e. x > ~2^62.5.
        let huge = Repr::new(IBig::from(1) << 63, 0);
        assert_eq!(ctx.exp::<2>(&huge, None), Err(FpError::Overflow(Sign::Positive)));

        // exp(huge negative) underflows to +0
        let neg = Repr::new(-(IBig::from(1) << 63), 0);
        assert_eq!(ctx.exp::<2>(&neg, None), Err(FpError::Underflow(Sign::Positive)));

        // exp_m1(huge negative) -> -1 (a finite value, not an error)
        let m1 = ctx.exp_m1::<2>(&neg, None).unwrap().value();
        assert_eq!(m1, -FBig::<mode::HalfEven>::ONE);
    }

    // A sharp OOM regression needs an exponent gap large enough that 2^gap exceeds any
    // memory (gap ≳ 1e11), yet with floor(x/ln2) still fitting isize so the overflow
    // branch is not taken. That window only exists where isize is 64-bit: on 32-bit,
    // isize tops out at ~2.1e9 — below any OOM-inducing gap — so the overflow branch
    // always intervenes first. The fix itself (log2_bounds in round_fract) is
    // arch-independent; only this dedicated sharp test is 64-bit-only.
    #[cfg(target_pointer_width = "64")]
    #[test]
    fn test_exp_m1_large_negative_no_oom() {
        // Regression test: exp_m1 of a large-magnitude negative input subtracts
        // 1 from an astronomically small exp(x), so the aligned subtraction hands
        // round_fract a sparse sticky tail whose `precision` equals the exponent gap
        // (~6.6e18 here). The debug assert in round_fract used to materialize B^precision
        // (2^6.6e18 bits → certain OOM); it now uses log2 bounds and must not allocate.
        //
        // x = -2^62: the gap (~6.6e18) dwarfs memory, yet floor(x/ln2) ≈ -6.6e18 still
        // fits 64-bit isize (≈9.2e18), so this does NOT enter the overflow branch.
        let ctx = Context::<mode::Up>::new(2);
        let x = Repr::new(-(IBig::from(1) << 62), 0);
        let r = ctx.exp_m1::<2>(&x, None).unwrap().value();
        // exp_m1(-2^62) = -1 + ε (ε > 0 vanishingly small); under Up it rounds above -1.
        assert!(
            r > -FBig::<mode::Up, 2>::ONE,
            "exp_m1(-2^62) under Up should round above -1, got {r:?}"
        );
    }

    #[test]
    fn test_exact_results_on_unlimited_precision() {
        // Regression test: values carrying precision 0 (unlimited) — produced by
        // `try_from(0.0)` and the `FBig::ONE`/`ZERO` constants — must still compute
        // their exact-result special cases instead of panicking in
        // assert_limited_precision before reaching the shortcut.
        type F = FBig<mode::HalfEven, 2>;

        let zero = F::try_from(0.0_f64).unwrap();
        assert_eq!(zero.exp(), F::ONE);
        assert_eq!(zero.exp_m1(), F::ZERO);
        assert_eq!(zero.sqrt(), F::ZERO);
        assert_eq!(zero.ln_1p(), F::ZERO);

        // -0.0 preserves its sign through exp_m1 and sqrt.
        let neg_zero = F::try_from(-0.0_f64).unwrap();
        assert!(neg_zero.exp_m1().repr().is_neg_zero());
        assert!(neg_zero.sqrt().repr().is_neg_zero());

        // FBig::ONE carries unlimited precision; ln(1) = 0 is exact.
        assert_eq!(F::ONE.ln(), F::ZERO);
    }

    #[test]
    fn test_powf_zero_base() {
        use crate::DBig;
        // powf with a float exponent returns the *positive* result on a zero base
        // (matching the common float-pow convention); use powi for the signed result.
        let ctx = Context::<mode::HalfEven>::new(53);
        // powf(-0, 2.0) = +0 (NOT -0)
        let r = ctx
            .powf::<2>(&Repr::<2>::neg_zero(), &Repr::new(2.into(), 0), None)
            .unwrap()
            .value();
        assert!(r.repr().is_pos_zero(), "expected +0");
        assert!(!r.repr().is_neg_zero(), "powf(-0, x) should be +0, not -0");
        // powf(0, -1) = +inf
        let r = ctx
            .powf::<2>(&Repr::<2>::zero(), &Repr::new((-1i32).into(), 0), None)
            .unwrap()
            .value();
        assert!(r.repr().is_infinite());
        assert_eq!(r.repr().sign(), Sign::Positive);
        // powi(-0, 3) = -0 (the sign-correct, integer-exponent variant)
        let r = ctx
            .powi::<2>(&Repr::<2>::neg_zero(), 3.into())
            .unwrap()
            .value();
        assert!(r.repr().is_neg_zero());
        let _ = DBig::ZERO;
    }
}