Author mark.dickinson
Recipients mark.dickinson, rhettinger, steven.daprano
Date 2021-11-23.18:25:47
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
Here's the float-and-Fraction-based code that I'm using to compare the integer-based code against:

def sqrt_frac2(n, m):
    Square root of n/m as a float, correctly rounded.
    f = fractions.Fraction(n, m)

    # First approximation.
    x = math.sqrt(n / m)

    # Use the approximation to find a pair of floats bracketing the actual sqrt
    if fractions.Fraction(x)**2 >= f:
        x_lo, x_hi = math.nextafter(x, 0.0), x
        x_lo, x_hi = x, math.nextafter(x, math.inf)

    # Check the bracketing. If math.sqrt is correctly rounded (as it will be on a
    # typical machine), then the assert can't fail. But we can't rely on math.sqrt being
    # correctly rounded in general, so would need some fallback.
    fx_lo, fx_hi = fractions.Fraction(x_lo), fractions.Fraction(x_hi)
    assert fx_lo**2 <= f <= fx_hi**2

    # Compare true square root with the value halfway between the two floats.
    mid = (fx_lo + fx_hi) / 2
    if mid**2 < f:
        return x_hi
    elif mid**2 > f:
        return x_lo
        # Tricky case: mid**2 == f, so we need to choose the "even" endpoint.
        # Cheap trick: the addition in 0.5 * (x_lo + x_hi) will round to even.
        return 0.5 * (x_lo + x_hi)
Date User Action Args
2021-11-23 18:25:47mark.dickinsonsetrecipients: + mark.dickinson, rhettinger, steven.daprano
2021-11-23 18:25:47mark.dickinsonsetmessageid: <>
2021-11-23 18:25:47mark.dickinsonlinkissue45876 messages
2021-11-23 18:25:47mark.dickinsoncreate