malachite-float 0.13.0

// Copyright © 2026 Mikhail Hogrefe
//
// Uses code adopted from the GNU MPFR Library.
//
//      Copyright © 1999-2024 Free Software Foundation, Inc.
//
//      Contributed by the AriC and Caramba projects, INRIA.
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.

use crate::Float;
use crate::InnerFloat::{Finite, Infinity, NaN, Zero};
use crate::float::conversion::string::get_str_data::MPFR_L2B;
use crate::floor_and_ceiling;
use alloc::vec;
use alloc::vec::Vec;
use core::cmp::Ordering::{self, Equal};
use malachite_base::fail_on_untested_path;
use malachite_base::num::arithmetic::traits::{CeilingLogBase2, CheckedLogBase2, NegAssign, Sign};
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::conversion::traits::{ExactFrom, RoundingFrom};
use malachite_base::rounding_modes::RoundingMode::{self, *};
use malachite_nz::natural::Natural;
use malachite_nz::natural::arithmetic::float::get_str::{limbs_get_str, limbs_get_str_power_of_2};

// Returns `ceil(e * log2(beta) ^ ((-1) ^ i))`, or that plus 1. For `i == 0` it uses a 23-bit upper
// approximation to `log(beta) / log(2)`; for `i == 1` a 77-bit upper approximation to `log(2) /
// log(beta)`. Both approximations are entries of `MPFR_L2B`.
//
// This is `mpfr_ceil_mul` from `get_str.c`, MPFR 4.2.2.
crate_test_fn! {ceil_mul(e: i64, beta: u64, i: usize) -> i64 {
    const WIDTH_MINUS_1: u64 = i64::WIDTH - 1;
    // p = mantissa * 2 ^ (exp - 128): the l2b approximation as an exact `Float`.
    let (mantissa, exp) = MPFR_L2B[usize::exact_from(beta) - 2][i];
    let p = Float::from_natural_prec(Natural::from(mantissa), 128).0
        >> u64::exact_from(128 - i64::from(exp));
    // t = e * p, with e as a `Float` with the precision of an `mpfr_exp_t` minus one, both
    // roundings up.
    let t = Float::from_signed_prec_round(e, WIDTH_MINUS_1, Ceiling)
        .0
        .mul_prec_round(p, WIDTH_MINUS_1, Ceiling)
        .0;
    // ceil(t).
    i64::rounding_from(&t, Ceiling).0
}}

/// Returns the number of significant digits that suffice to losslessly represent any [`Float`] of
/// precision `prec` in base `base`: printing such a [`Float`] to this many digits with rounding to
/// nearest (for example with [`get_str`]), then reading the digits back at precision `prec`, again
/// rounding to nearest, recovers the original value exactly.
///
/// The count is $1 + \lceil p \log 2 / \log b \rceil$, except that for a power-of-2 base $b = 2^k$
/// it is $1 + \lceil (p - 1) / k \rceil$.
///
/// This function depends only on the precision, not on any particular [`Float`] value. It is the
/// digit count [`get_str`] uses when its `digit_len` argument is 0, and the number of significant
/// digits `Display` shows for a [`Float`] of precision `prec`.
///
/// # Worst-case complexity
/// Constant time and additional memory.
///
/// # Panics
/// Panics if `base` is less than 2 or greater than 62, or if `prec` is 0.
///
/// # Examples
/// ```
/// use malachite_float::float::conversion::string::get_str::get_str_digit_count;
///
/// // 17 significant decimal digits distinguish every double-precision (53-bit) value...
/// assert_eq!(get_str_digit_count(10, 53), 17);
/// // ...and 9 suffice for single precision (24 bits)
/// assert_eq!(get_str_digit_count(10, 24), 9);
/// // in base 16, 14 digits: 1 + ceil(52 / 4)
/// assert_eq!(get_str_digit_count(16, 53), 14);
/// // in base 2 the digits are just the bits
/// assert_eq!(get_str_digit_count(2, 53), 53);
/// ```
///
/// This is `mpfr_get_str_ndigits` from `get_str.c`, MPFR 4.2.2.
pub fn get_str_digit_count(base: u64, prec: u64) -> usize {
    assert!((2..=62).contains(&base));
    assert_ne!(prec, 0);
    // Deal first with power-of-two bases, since even for those, `ceil_mul` might return a value too
    // large by 1. For `base = 2 ^ k`, this is `1 + ceil((prec - 1) / k) = 2 + floor((prec - 2) /
    // k)`.
    if let Some(k) = base.checked_log_base_2() {
        return usize::exact_from(1 + (prec + k - 2) / k);
    }
    // `ceil_mul` is guaranteed to give `1 + ceil(prec * log(2) / log(base))` for `prec` below this
    // bound (for `prec = 186564318007` and `base = 7` or `49` it returns one more).
    let ret = if prec < 186_564_318_007 {
        u64::exact_from(ceil_mul(i64::exact_from(prec), base, 1))
    } else {
        // `prec` is large and `base` is not a power of two, so `prec * log(2) / log(base)` cannot
        // be an integer and Ziv's loop terminates. `w` is the working precision; `ceil_mul` used a
        // 77-bit upper approximation to `log(2) / log(base)`. Reaching here needs a mantissa of at
        // least ~1.86e11 bits, far beyond any `Float` the test suite builds.
        fail_on_untested_path("get_str_digit_count, Ziv loop for huge prec");
        let mut w = 77;
        loop {
            w <<= 1;
            // lower (rounding down) and upper (rounding up) approximations to `log2(base)`
            let (log_lo, log_hi) =
                floor_and_ceiling(Float::from_unsigned_prec(base, w).0.log_base_2_round(Floor));
            // lower (`prec / log_hi`, rounding down) and upper (`prec / log_lo`, rounding up)
            // bounds on `prec * log(2) / log(base)`, each rounded up to an integer
            let pf = Float::from_unsigned_prec(prec, w).0;
            let lo = u64::rounding_from(&pf.div_round_ref_val(log_hi, Floor).0, Ceiling).0;
            let hi = u64::rounding_from(&pf.div_round(log_lo, Ceiling).0, Ceiling).0;
            if lo == hi {
                break lo;
            }
        }
    };
    usize::exact_from(1 + ret)
}

/// Converts a [`Float`] to base-`base` mantissa digits and an exponent, rounding to `digit_len`
/// digits with the rounding mode `rm`.
///
/// The digits are returned as ASCII characters (`0`–`9`, then lowercase `a`–`z`, then uppercase
/// `A`–`Z`, supporting a `base` of up to 62; a negative `base` in `-36..=-2` uses base `|base|`
/// with `0`–`9` and uppercase `A`–`Z`), preceded by `-` when `x` is negative. With the returned
/// exponent $e$, the value represented is $0.d_1 d_2 \ldots \times \mathrm{base}^e$, where $d_1 d_2
/// \ldots$ are the digits. If `digit_len` is 0, the fewest digits that round-trip back to `x` are
/// used.
///
/// `base` must be in `2..=62` or `-36..=-2`; any other value returns `None`.
///
/// The returned [`Ordering`] reports whether the rounded result is less than, equal to, or greater
/// than the exact value of `x`. The special values NaN, $\infty$, and $-\infty$ produce the strings
/// `@NaN@`, `@Inf@`, and `-@Inf@`, each with exponent 0 and `Equal`.
///
/// # Worst-case complexity
/// $T(n) = O(n (\log n)^2 \log\log n)$
///
/// $M(n) = O(n \log n)$
///
/// where $T$ is time, $M$ is additional memory, and $n$ is `max(x.complexity(), digit_len)`.
///
/// # Panics
/// Panics if `rm` is `Exact` but `x` cannot be represented exactly in `digit_len` base-`base`
/// digits.
///
/// # Examples
/// ```
/// use core::cmp::Ordering::*;
/// use malachite_base::rounding_modes::RoundingMode::{self, *};
/// use malachite_float::Float;
/// use malachite_float::float::conversion::string::get_str::get_str;
/// use malachite_q::Rational;
///
/// // Render the returned digit bytes as a `String` for readability.
/// let s = |x: &Float, base: i64, n: usize, rm: RoundingMode| {
///     get_str(x, base, n, rm)
///         .map(|(digits, exp, ord)| (String::from_utf8(digits).unwrap(), exp, ord))
/// };
///
/// // 1.25 to 3 digits: 0.125 * 10^1 in base 10, 0.101 * 2^1 in base 2, both exact.
/// assert_eq!(
///     s(&Float::from(1.25), 10, 3, Nearest),
///     Some(("125".to_string(), 1, Equal))
/// );
/// assert_eq!(
///     s(&Float::from(1.25), 2, 3, Nearest),
///     Some(("101".to_string(), 1, Equal))
/// );
///
/// // A negative value gets a leading `-`.
/// assert_eq!(
///     s(&Float::from(-1.25), 10, 3, Nearest),
///     Some(("-125".to_string(), 1, Equal))
/// );
///
/// // 1/3 (to 53 bits) has no finite base-10 expansion, so the result is rounded and the
/// // `Ordering` gives the direction.
/// let third = Float::from_rational_prec(Rational::from_unsigneds(1u32, 3u32), 53).0;
/// assert_eq!(s(&third, 10, 4, Floor), Some(("3333".to_string(), 0, Less)));
/// assert_eq!(
///     s(&third, 10, 4, Ceiling),
///     Some(("3334".to_string(), 0, Greater))
/// );
///
/// // Special values produce fixed strings; an invalid base gives `None`.
/// assert_eq!(
///     s(&Float::from(f64::NAN), 2, 0, Down),
///     Some(("@NaN@".to_string(), 0, Equal))
/// );
/// assert_eq!(
///     s(&Float::from(f64::INFINITY), 2, 0, Down),
///     Some(("@Inf@".to_string(), 0, Equal))
/// );
/// assert_eq!(s(&Float::from(1.25), 100, 0, Nearest), None);
/// ```
///
/// This is mpfr_get_str from get_str.c, MPFR 4.2.2.
pub fn get_str(
    x: &Float,
    base: i64,
    digit_len: usize,
    mut rm: RoundingMode,
) -> Option<(Vec<u8>, i64, Ordering)> {
    // valid bases are -36..=-2 and 2..=62
    if !(-36..=-2).contains(&base) && !(2..=62).contains(&base) {
        return None;
    }
    let b = base.unsigned_abs();
    // `dir` is the direction in which the magnitude of `x` was rounded to the result (-1, 0, or 1).
    let (neg, mut s, e, dir) = match &x.0 {
        NaN => return Some((b"@NaN@".to_vec(), 0, Equal)),
        Infinity { sign } => {
            let s = if *sign {
                b"@Inf@".to_vec()
            } else {
                b"-@Inf@".to_vec()
            };
            return Some((s, 0, Equal));
        }
        Zero { sign } => {
            // Malachite's zero carries no precision, so the digit_len == 0 default
            // (get_str_digit_count) does not apply; use a single digit.
            (
                !*sign,
                vec![b'0'; if digit_len == 0 { 1 } else { digit_len }],
                0,
                0,
            )
        }
        Finite {
            sign,
            exponent,
            precision,
            significand,
        } => {
            let m = if digit_len == 0 {
                get_str_digit_count(b, *precision)
            } else {
                digit_len
            };
            // For a negative x, reduce to the magnitude by inverting the rounding direction (the
            // mpfr_get_str MPFR_INVERT_RND step).
            let neg = !*sign;
            if neg {
                rm.neg_assign();
            }
            // Malachite's `exponent` is MPFR's EXP (the scientific exponent plus one).
            let xp = significand.to_limbs_asc();
            let x_exp = i64::from(*exponent);
            let (s, e, dir) = if b.is_power_of_two() {
                limbs_get_str_power_of_2(&xp, x_exp, *precision, b, base, m, rm)
            } else {
                let g = ceil_mul(x_exp - 1, b, 1);
                let exp = (i64::exact_from(m) - g).unsigned_abs();
                // radix-2 precision needed for m digits in base b, plus guard bits
                let mut prec = u64::exact_from(ceil_mul(i64::exact_from(m), b, 0)) + 1;
                prec += prec.ceiling_log_base_2();
                if exp != 0 {
                    // add the maximal exponentiation error
                    prec += 3 * exp.ceiling_log_base_2();
                }
                limbs_get_str(&xp, x_exp, b, base, m, rm, g, prec, i64::exact_from(exp))
            };
            (neg, s, e, dir)
        }
    };
    // `Exact` demands that the digits represent `x` exactly; a nonzero `dir` means rounding was
    // needed, which violates the contract. (For odd bases this is common, since a dyadic `Float`
    // rarely has a finite expansion there; and `digit_len == 0` picks the round-trip digit count,
    // which is generally fewer than the exact expansion needs.)
    assert!(
        rm != Exact || dir == 0,
        "get_str: Exact rounding was requested, but {x} is not exactly representable in the \
         requested number of base-{base} digits"
    );
    // `dir` orders the result's magnitude against `|x|`; negating both reverses the order.
    let o = dir.sign();
    Some(if neg {
        s.insert(0, b'-');
        (s, e, o.reverse())
    } else {
        (s, e, o)
    })
}