Module fraction::approx::sqrt

Implements an arbitrary-precision square-root approximation algorithm.

This module extends GenericFraction with eight (8) methods:

• sqrt
• sqrt_raw
• sqrt_with_accuracy
• sqrt_with_accuracy_raw
• sqrt_abs
• sqrt_abs_raw
• sqrt_abs_with_accuracy
• sqrt_abs_with_accuracy_raw

All of these methods return some form of an approximation for the square root, and they all use the same algorithm but behave slightly differently.

A note on performance: These methods are designed to be fast in release builds. An unfortunate side effect of this is that performance is significantly degraded when compiler optimisations are disabled. Please consider enabling compiler optimisations in your project if you wish to use these methods.

Accuracy of the output

The behaviour detailed in this section is common to all methods.

The algorithm in use is iterative: an initial estimate is generated, and this is repeatedly refined until it is suitably accurate. Of course, it is not possible to check the approximation against the true square root value, because we don’t know it. (If we did, we’d just return that instead.) Because of this, the “closeness” must be determined by squaring the approximation to see how close it comes to the original value.

For example, let’s say we wanted to find the square root of 0.0152399025 (6095961/400000000). We might guess 0.1. To check how close we are, we square our guess of 0.1 and get 0.01. This square is accurate to 2 decimal places (0, 1). We might guess again, this time with 0.12. This gives us 0.0144, so we’re still only accurate to 2 decimal places. Guessing 0.123 yields a square of 0.015129, which is now accurate to 3 decimal places.

The above is the checking process that happens when you call any of the methods defined in this module. You must supply a value denoting how accurate you want the square of the approximation to be. It is very important to realise that this is not the same as the accuracy of the square root! However, for x > 1, x.sqrt(n) where n is the number of decimal places that the square must be accurate to will actually produce a square root which is accurate to more than n decimal places. In other words: as long as you aren’t using small numbers, you can consider n to be a lower bound on the accuracy of the square root itself. When you are working with numbers less than 1, this is no longer the case, and the square root may be less accurate than the square (although this is still not typically the case). In all cases, the square of the result you get will be accurate to the level of accuracy you gave to the method.

Due to the nature of the algorithm, most outputs will actually be vastly more accurate than requested. This should not be relied on, and is subject to change. In some instances, the result will actually be exactly correct (e.g. for small square numbers like 4, 9, 16, 25, etc.).

Method variants

raw

raw methods return the approximation in unsimplified form via RawApprox, which can (in most cases; see its documentation for more details) be destructured into a Ratio. These methods are typically faster than non-raw ones by an order of magnitude or more, especially for extreme inputs (very large or very small). Do not use raw methods unless you are writing very performance-critical code: most arithmetic operations on Ratio and GenericFraction will automatically simplify the result so although the sqrt_raw method will still be faster than the non-raw version, you will still incur the overhead of simplification, just somewhere else instead.

// We save time here by using `raw`...
match x.sqrt_raw(10_000) {
    RawApprox::Rational(ratio) => {
        // ...but we lose the time again here, because the `+` simplifies the ratio.
        let _ = ratio + Ratio::<BigUint>::zero();
    },

    _ => (),
}

Be aware that unsimplified values can take up excessive amounts of memory (100 KB and beyond, particularly when high levels of accuracy are used).

For a few (limited) examples of how you can write performance-critical code with Ratio and GenericFraction, see this module’s own implementation.

with_accuracy

These methods accept an Accuracy value instead of a u32 representing a number of decimal places. It is recommended that you use with_accuracy whenever you need to approximate more than one square root to the same level of accuracy. This avoids unnecessary heap allocations.

// Don't do this! `sqrt` allocates a new `Accuracy` each time.
for n in 0..100 {
    let x: GenericFraction<u8> = n.into();
    some_fn(x.sqrt(1_000));
}

// Instead, do this:
let accuracy = Accuracy::decimal_places(1_000_u32);

for n in 0..100 {
    let x: GenericFraction<u8> = n.into();
    some_fn(x.sqrt_with_accuracy(&accuracy));
}

If you only perform one sqrt computation, there is no benefit to using sqrt_with_accuracy.

Keep in mind that Accuracy has some pre-allocated values which you may wish to use.

abs

These methods ignore the sign of the value and instead approximate the square root of the magnitude only.

The default behaviour is as follows:

let something_positive: GenericFraction<u8> = 2.into();
let something_negative: GenericFraction<u8> = (-2).into();

// Calling `sqrt` on a negative number will return `NaN`.
assert_eq!(something_negative.sqrt(100), GenericFraction::NaN);

// Calling `sqrt_abs` on a negative number will not return `NaN`.
assert_ne!(something_negative.sqrt_abs(100), GenericFraction::NaN);

// `sqrt +2` is equal to `sqrt_abs -2`.
assert_eq!(something_positive.sqrt(100), something_negative.sqrt_abs(100));

The following are guaranteed to hold for any pair of abs and non-abs methods:

// When `x` is positive:
assert_eq!(x.sqrt(100), (-x).sqrt_abs(100));

// When `x` is negative:
assert_eq!((-x).sqrt(100), x.sqrt_abs(100));

Enums

• RawApprox
  An unsimplified approximation of a square root.