Getting the square root of a rational

[LoganDark]

Is there a way to get the square root of a Rational?

Of course, some square roots are irrational, so there may not be a way to get the result as a Rational, but is there a way to get it as e.g. a decimal like to_string(size_t)?

[LoganDark]

I ended up using integer square root (ipow is Integer exponentiation):

/**
 * Gets the square root of a [[math::Rational]].
 *
 * @param rational
 * @param precision
 * @return
 */
math::Rational getRationalSqrt(
	const math::Rational & rational, const math::Integer & precision
) {
	math::Integer pow10 = ipow(10, precision);

	return math::Rational(
		intSqrt(rational.numerator() * pow10),
		intSqrt(rational.denominator() * pow10)
	);
}

[possibly-wrong]

If you just want to approximate to a given precision as in your example, then the given implementation won't provide the requested precision (consider getRationalSqrt(Rational(1, 3), 10), for example, which is only correct to 6 digits). A simple approach would be to use Newton's method, something like this:

Rational abs(const Rational& x)
{
    return (x < 0 ? -x : x);
}

Rational sqrt(const Rational& x, const Rational& tol)
{
    // assert(x >= 0 && tol > 0);
    if (x == 0)
    {
        return 0;
    }
    else
    {
        Rational y = x;
        while (true)
        {
            Rational t = y;
            y = (y + x / y) / 2;
            if (abs(y - t) < tol)
            {
                break;
            }
        }
        return y;
    }
}

Note that this yields a result to within the specified absolute (vs. relative) error.

[LoganDark]

precision in my example isn't digits. It's actually some magic number I crank up to about double the digit precision I want. Would you mind adding your function to the library?

Ty~

[possibly-wrong]

I think this either requires more work, or belongs in application code. That is, the quick-and-dirty example above bounds the absolute error, but it seems reasonable to have the result be exact when possible, which this implementation doesn't do. More generally, since sqrt:Rational->Rational is not guaranteed to be exact (if the result is irrational), I can think of at least three different reasonable ways to implement it, and it isn't clear which is best: bound the absolute error (similar to my example above), bound the relative error (similar to converting to double and computing the sqrt there), or bound the denominator (which is probably the most desirable if you plan to apply square root operations repeatedly). If you have a specific one of these in mind, it's probably best to include it in your code.

[LoganDark]

Are you saying that some arbitrary-precision symbolic library would work better?

[possibly-wrong]

More that it's not clear exactly what your requirements are (e.g., what exactly is the desired behavior of the "magic number" argument in your original implementation?). The intent here is to provide exact arbitrary-precision operations. If you're looking for approximations, then it sounds like you want an arbitrary-precision floating point library. See here and here for example, neither of which implement a square root operation, but the latter does also have a bigfloat type that does.

[LoganDark]

Exact operations are good - I was only looking to do that for calculating the distance between two points to display to the user. I'm glad you're staying with the idea of keeping this library precise.

The "magic number" indicates to some extent the relative precision of the operation - higher numbers calculate closer to the actual square root, but never actually get there for real irrational square roots. I'm not sure exactly how to express how it works or what the limits are, but since it works by integer square root, a higher number means it gets closer to its target since it takes the sqrt of a larger integer.

Anyway, my use case was satisfied by my own implementation. I'm not hoping for irrational stuff or anything, it is called a Rational after all :P