Auto merge of #116176 - FedericoStra:isqrt, r=dtolnay

Add "integer square root" method to integer primitive types

For every suffix `N` among `8`, `16`, `32`, `64`, `128` and `size`, this PR adds the methods

```rust
const fn uN::isqrt() -> uN;
const fn iN::isqrt() -> iN;
const fn iN::checked_isqrt() -> Option<iN>;
```

to compute the [integer square root](https://en.wikipedia.org/wiki/Integer_square_root), addressing issue #89273.

The implementation is based on the [base 2 digit-by-digit algorithm](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_(base_2)) on Wikipedia, which after some benchmarking has proved to be faster than both binary search and Heron's/Newton's method. I haven't had the time to understand and port [this code](http://atoms.alife.co.uk/sqrt/SquareRoot.java) based on lookup tables instead, but I'm not sure whether it's worth complicating such a function this much for relatively little benefit.

0 files changed, 0 insertions, 0 deletions