### 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 |

#**2015** in Algorithms

**796** downloads per month

Used in **7** crates
(3 directly)

**Apache-2.0**

30KB

541 lines

`fixed-sqrt`

`fixed-sqrt`

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

This crate implements

as trait methods for fixed point number types
defined in the `sqrt``(``)`

crate, using the
integer square root algorithm provided by the
`fixed`

crate.`integer-sqrt`

## Implementation

**Even fractional bits**

is implemented for all `FixedSqrt`*unsigned* fixed-point types with an *even*
number of bits.

is implemented for all `FixedSqrt`*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

) can compute the square root `FixedI128`*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

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.`FixedU128`

## Accuracy

The

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.`errors`

CSV files suitable for graphing with gnuplot can also be generated by
running the

example with the `errors`

flag.`-`p

Generally the square root will be within 1.0 of (and usually no greater than)
the

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.`f64`

## Panics

- Panics if called on a negative signed number

#### Dependencies

~2.5MB

~48K SLoC