Expand description

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

Repository

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