6 releases
0.2.5 | May 21, 2022 |
---|---|
0.2.4 | Aug 2, 2020 |
0.2.1 | Jun 8, 2020 |
0.2.0 | Feb 4, 2020 |
#3 in #fractional
477 downloads per month
Used in 7 crates
(3 directly)
30KB
541 lines
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.
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
Dependencies
~2.5MB
~47K SLoC