# `fixed-sqrt`

> Square root functions for fixed-point numbers using integer square root
> algorithm.

This crate implements `sqrt()` as trait methods for fixed point number types
defined in the [`fixed`](https://crates.io/crates/fixed) crate, using the
integer square root algorithm provided by the
[`integer-sqrt`](https://crates.io/crates/integer-sqrt) crate.

[Documentation](https://docs.rs/fixed-sqrt)

## Implementation

**Even fractional bits**

`FixedSqrt` is implemented for all *unsigned* fixed-point types with an *even*
number of bits.

`FixedSqrt` is implemented for all *signed* fixed-point types with an even
number of fractional bits, *except* for the case of *zero integer* bits (i.e.
fractional bits equal to the total bit size of the type). This is because the
range for these types is *[-0.5, 0.5)*, and square roots of numbers in the range
*[0.25, 0.5)* will be *>= 0.5*, outside of the range of representable values for
that type.

**Odd fractional bits**

Computing the square root with an *odd* number of fractional bits requires one
extra bit to shift before performing the square root.

In the case of *signed* fixed-point numbers, since square root is defined only
for positive input values, all signed fixed-point numbers (up to and including
`FixedI128`) can compute the square root *in-place* utilizing the sign bit for
the overflow.

For *unsigned* fixed-point numbers with odd fractional bits, if an extra bit is
needed (i.e. if the most significant bit is 1), this requires a scalar cast to
the next larger unsigned primitive type before computing the square root. As a
result, the square root trait is *not* implemented for `FixedU128` types with an
odd number fractional bits since that would require 256-bit unsigned integers,
or else the domain would have to be restricted to the lower half of u128 values.

## Accuracy

The `errors` example can be run to see exhaustive error stats for 8-bit and
16-bit fixed-point types. The worst-case absolute error is shown to occur at
the largest values, where the percentage error is small, and the worst-case
percentage error occurs at the smallest values where the absolute error is
small.

CSV files suitable for graphing with gnuplot can also be generated by
running the `errors` example with the `-p` flag.

Generally the square root will be within 1.0 of (and usually no greater than)
the `f64` square root, except in the case of large 128-bit numbers where the
accuracy of the fixed-point numbers are better than `f64`, in which case the
floating-point error may be greater than 1.0.

## Panics

- Panics if called on a negative signed number