[ER] isqrt() function for integral values

[leonardo-m]

As in Python 3:
https://docs.python.org/3/library/math.html#math.isqrt

To the Rust stdlib it could be added a isqrt() function for all u*/i*/usize/isize, that returns the floor of the square root of the nonnegative integral value n, that is the greatest integer a such that a*a <= n.

This in Python shows that the usual trick to pass through f64 isn't precise enough for u128:

>>> from math import sqrt, isqrt
>>> N = (2 ** 128) - 1 # u128::MAX
>>> a = int(sqrt(N))
>>> a
18446744073709551616
>>> b = isqrt(N)
>>> b
18446744073709551615
>>> (a * a) <= N
False

[Nicholas-Baron]

@rustbot label: +Libs-small.

[rustbot]

Error: Label Libs-small can only be set by Rust team members

Please let @rust-lang/release know if you're having trouble with this bot.

[Nicholas-Baron]

1 question I have is what should be the return value of (-1).isqrt()?
There is no NaN, which is what the floating-point versions return.
Python effectively panics when handed a negative number, but I do not know if that is a good thing for Rust.

I think a working implementation would be a good way to push this further. However, I am just some random contributor and a team member (particularly a library team member) may have a better idea of what to do.

[leonardo-m]

Python effectively panics when handed a negative number, but I do not know if that is a good thing for Rust.

In Rust we prefer to return Option (or sometimes Result) for partial functions like sqrt (I don't agree with the design of the recently added integral log of the stdlib: "When the number is negative, zero, or if the base is not at least 2; it panics in debug mode and the return value is 0 in release mode.").

A funny API for this function could be:

const fn u8::isqrt() -> u8; // A nibble.
const fn u16::isqrt() -> u8;
const fn u32::isqrt() -> u16;
const fn u64::isqrt() -> u32;
const fn u128::isqrt() -> u64;

const fn i8::isqrt() -> Option<u8>; // A nibble.
const fn i16::isqrt() -> Option<u8>;
const fn i32::isqrt() -> Option<u16>;
const fn i64::isqrt() -> Option<u32>;
const fn i128::isqrt() -> Option<u64>;

(Unfortunately Rust type system doesn't have ranged integral values yet, so the function for u8 needs to return another u8).

But having Option only for the signed ones seems iffy. So an alternative is to use Result<Ty, !> for the unsigned types.

[LukasKalbertodt]

Regarding returning smaller integers than Self: the feature int_log (#70887) has the same open question. This comment suggested to change the return type from T to u32. This was implemented in #88665. This wouldn't work for isqrt as sqrt(2^128 - 1) does not fit into an u32. Maybe we should figure that out for both, log and sqrt, before stabilizing either to increase API consistency?

That said, I'm not sure whether I like returning the smallest possible integer type. For one, as you said, u8 cannot go smaller, making the API somewhat asymmetric. But also, sqrt is an operation that is likely to be chained with other operations in a more complex expression. And returning a smaller integer type could require more casts into those expressions.

But having Option only for the signed ones seems iffy. So an alternative is to use Result<Ty, !> for the unsigned types.

I don't think the signed and unsigned API really needs to be symmetric here. I would much prefer u32::isqrt returning u32 instead of Option<u32> or Result<u32, !>.

[leonardo-m]

If u32::isqrt returns a u16, and you need a u32 again, you can write u32::from(x.isqrt()) without hard casts and without unwraps. While to go from a u32 result to a u16 you need some kind of hard cast (or try_from). This is one reason why returning types smaller than the input type is nicer.

For usize::isqrt I think it's OK to return another usize.

[wooster0]

I'm not sure if this has been discussed before but I think the name should be sqrt, not isqrt or sqrti because the i doesn't add any value IMO. The same thing has been discussed for {log, log2, log10} in the past and now they are named {log, log2, log10} and not {logi, log2i, log10i} or {ilog, ilog2, ilog10} or {logi, ilogi2, ilogi10}.
And of course {f32, f64}::sqrt isn't called sqrtf or fsqrt either so I don't think it makes sense to call this sqrt variant sqrti or isqrt.

[leonardo-m]

I named those isqrt because 5.isqrt() doesn't return the square root, it returns the integer truncation of the square root. In Python std lib they have chosen the "isqrt" name. But if for Rust stdlib there's consensus to avoid the leading "i", then it's OK.

[LukasKalbertodt]

"Integer square root" (abbreviated as isqrt) is an established term in math with a precise definition: https://en.wikipedia.org/wiki/Integer_square_root
So calling the method isqrt is not (just) a Hungarian notation thing.

However, I'm also fine with just sqrt. The only other integer operation (I can think of) that can have a non-integer result is division. And there it's also the truncated/floored/rounded down semantic and not something else like "round to nearest integer". So I'm not sure if calling the integer square root just sqrt would lead to any surprises where people assume other behavior.

[leonardo-m]

I think it's OK for u8::isqrt to return an u8 plus an assume(result <= 16):

const fn u8::isqrt() -> u8 {
    // ...
    unsafe { assume(result <= 16);
    result
}

Once Rust gains proper well implemented ergonomic ranged integers, that assume() should be removed.

[scottmcm]

Once we have Integer<0..=N>, isqrt on that should give Integer<0..=⌊√N⌋>.

That said, uN::sqrt should return uN. Analogously to what #88665 (comment) pointed our for log2, that way x.pow(2).isqrt() would return the the same type as x.

[leonardo-m]

For ranged integers now I've settled to like a syntax like u16[0 ..= N] similar to slicing. It's natural for a Rust programmer and it's compact.

Regarding the type round-trip, I'm content with using a safe looking "from":

let x: u32 = 100;
u32::from(x.pow(2).isqrt())

Rust doesn't have a typeof, otherwise you could write:

type_of(x)::from(x.pow(2).isqrt())

There are situations where you want to use the smaller type returned by the isqrt. Using a smaller type avoids you some casts.