ACP: `isqrt` for `NonZero<uN>`

[ivan-shrimp]

Proposal

Problem statement

Integer primitives now have an integer square root method isqrt. Positive integers always have a positive square root, and it would be natural to directly express this through NonZero.

Motivating examples or use cases

x.pow(2).isqrt() gives x for x: uN, and we can extend that to NonZero<uN>.

Solution sketch

// N = 8/16/32/64/128/size
impl NonZero<uN> {
    const fn isqrt(self) -> Self {
        // should behave as if:
        unsafe { NonZero::new_unchecked(self.get().isqrt()) }
    }
}

Alternatives

• Do nothing, and require users to use the NonZero constructors manually when necessary. This is either unsafe or requires .unwrap(), which is not ideal.
• Halve the size of the returned integer. However, this would be inconsistent with the primitive counterparts and violate the round-tripping property as mentioned above.

Links and related work

Motivation for primitive isqrt: https://github.com/rust-lang/rust/issues/89273 Tracking issue for isqrt: https://github.com/rust-lang/rust/issues/116226 Suggestion for this function: https://github.com/rust-lang/rust/issues/116226#issuecomment-2144225174 Implementation: https://github.com/rust-lang/rust/pull/126199

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[kennytm]

My motivation suggesting NonZero<uN>::isqrt() in https://github.com/rust-lang/rust/issues/116226#issuecomment-2144225174 was that, given a natural number $N > 0$, compute the "middle" value $M = \lfloor\sqrt N\rfloor > 0$ to decompose every number $i \in \mathbb ZN$ into $(a,b) \in \mathbb Z{\lceil N/M\rceil} \times \mathbb Z_M$ with $i = aM+b$. The $(a,b)$ pair is then feed through a Feistel network in order to perform something like format-preserving encryption.

With N: NonZero<u64> we can use NonZero::isqrt() to get M: NonZero<u64> so that (a, b) = (i / M, i % M) are panic-free.

[scottmcm]

(Disclaimer: I'm not libs-api) This seems entirely reasonable to me, under the same "it's helpful compared to .get().isqrt()" that gave us NonZero::count_ones and NonZero::ilog2.

[pitaj]

For the future, the following operations could have the same function signature fn(NonZero<T>) -> NonZero<T>

• reverse_bits
• rotate_left
• rotate_right
• swap_bytes
• to_be
• to_le

[the8472]

We discussed this during today's libs-api meeting and adding isqrt was accepted. Additional methods should go in a separate ACP.