pub const fn isqrt_u64(value: u64) -> u32Expand description
Exact floor(sqrt(value)) across the complete unsigned 64-bit domain,
with 32-bit operations and native multu only (no divide).
The value is shifted left by an even amount until its top word t lies
in [2^30, 2^32). A chord between two of 193 knots seeds
y = 1 / sqrt(t / 2^32) (Q2.30) and one Newton step y = y (3 - t y^2) / 2
brings it to about 29 bits.
t * y is then the root of the shifted value, so shifting it back gives
the root within a couple of units, and multu checks of r^2 <= value < (r + 1)^2 settle it exactly. Six products in all. In a boot-time bench in
Hollow Knight (512 squared lengths of random 3D vectors, Timer2) a call
took 226 cycles against 300 for the table-seeded nibble root it replaced,
loop and call overhead included, with identical results.