thruput_u256/sqrt.rs
1//! Integer square root.
2
3use crate::U256;
4
5impl U256 {
6 /// The largest `r` such that `r * r <= self`.
7 ///
8 /// Digit-by-digit (binary restoring): shifts, comparisons and subtractions,
9 /// no division. Newton's method costs a full 256-bit divide per iteration
10 /// that LLVM inlines into the loop -- `uint`'s Newton-based version
11 /// measured 12,732 bytes of rv32 text, for a square root.
12 pub const fn integer_sqrt(self) -> Self {
13 let len = self.bit_len();
14 if len <= 1 {
15 // 0 and 1 are their own square roots.
16 return self;
17 }
18
19 let mut x = self;
20 let mut res = Self::ZERO;
21
22 // The largest power of four not exceeding `self`: `1 << 2k` for the
23 // largest even `2k <= bit_len - 1`.
24 let mut bit = Self::ONE.wrapping_shl((len - 1) & !1);
25
26 while !bit.is_zero() {
27 let t = res.wrapping_add(bit);
28 if x.const_ge(t) {
29 x = x.wrapping_sub(t);
30 res = res.wrapping_shr(1).wrapping_add(bit);
31 } else {
32 res = res.wrapping_shr(1);
33 }
34 bit = bit.wrapping_shr(2);
35 }
36
37 res
38 }
39}