Crate fixed_sqrt
source · [−]Expand description
Square root trait for fixed-point numbers using integer square root algorithm.
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.
Panics
- Panics if called on a negative signed number
Modules
Additional traits
Traits
Square root algorithm for fixed-point numbers