## fixed-sqrt

Square root for fixed-point numbers

### 6 releases

 0.2.5 May 21, 2022 Aug 2, 2020 Jun 8, 2020 Feb 4, 2020

#2015 in Algorithms

Used in 7 crates (3 directly)

Apache-2.0

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.

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

~2.5MB
~48K SLoC