FCP WIP

[ChaiTRex]

Stabilization report

API summary

• i*: n.isqrt() (panics if n is negative) and n.checked_isqrt() (None if n is negative) (accepted by @dtolnay without ACP)
• u*: n.isqrt() (accepted by @dtolnay without ACP)
• NonZeroU*: n.isqrt() (ACP accepted)
• all added methods are const fn
• fairly speedy implementations of those methods (available in the latest nightly compiler)

const fn concerns

If a better implementation comes along that can't be const fn, const_eval_select can be used to combine the better implementation with the current implementation to maintain const fn.

Experience report

These projects use the isqrt feature (note that only five pages of results are allowed, so there may be more uses):

• Uses of #![feature(isqrt)]
• Uses of .isqrt()
• Uses of .checked_isqrt() (right now, there appear to be very few uses that aren't rust-lang/rust forks)

Standard libraries of programming languages

The following languages have an integer square root function in the standard library: Chapel, Common Lisp, Crystal, Julia, Maple, Python 3, Racket, Ruby, SageMath, Scheme, and Tcl.

Rust crates

integer-sqrt (6.3 million downloads of all versions; GitHub search)
num-bigint (133 million downloads of all versions)
rug (590 thousand downloads of all versions)

Other languages

GMP library

Implementation history

• Enhancement request made during Rust 1.55: [ER] isqrt() function for integral values rust-lang/rust#89273
• isqrt and checked_isqrt methods added to primitive types during 1.74 nightly: Add "integer square root" method to integer primitive types rust-lang/rust#116176
• ACP accepted for isqrt method on unsigned NonZero types during 1.80 nightly: ACP: isqrt for NonZero<uN> rust-lang/libs-team#391
• isqrt method added to unsigned NonZero types during 1.81 nightly: Add isqrt to NonZero<uN> rust-lang/rust#126199
• Sped up all relevant methods during 1.82 nightly: Improved checked_isqrt and isqrt methods rust-lang/rust#128166

Performance

The current implementation is based on a lookup table for 8-bit integers and "unrolled" recursive Karatsuba square root for larger types. The performance is decent, but it can be beaten with f32::sqrt and f64::sqrt for 16-bit through 64-bit integers (64 bit needs a slight adjustment to correct for imprecision). Even 128-bit integers could be sped up by using Karatsuba square root combined with the 64-bit floating point-based algorithm.

It isn't done that way because:

• Rust has no runtime detection of fast floating point hardware square root instructions (software-based floating point square roots are likely to be slower than the current implementation).
• Rust has no way to allow the Linux kernel and similar projects to forbid floating point arithmetic and to communicate that to core library code via a cfg setting or similar.

Ignoring floating point implementations, there are also faster algorithms that use only integer operations (for example the GMP library has faster implementations). I'm not a lawyer, but I believe that porting those to Rust would be considered a derivative work, and thus require adherence to the original code's license. Since the Rust standard library appears to be dual licensed under Apache 2.0 and MIT and since GMP is licensed under both LGPL 2 and LGPL 3, we'd have to complicate our licensing situation to port the GMP code.

---

Is there anything else that needs to be taken care of before the isqrt feature is stabilized?

[ChaiTRex]

Submitted at rust-lang#116226 (comment).