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 crate, using the integer square root algorithm provided by the integer-sqrt crate.

Documentation

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