Skip to content

Instantly share code, notes, and snippets.

@KeenS
Created October 28, 2020 11:35
Show Gist options
  • Save KeenS/17a1580577a860593ca75f681e0bfda8 to your computer and use it in GitHub Desktop.
Save KeenS/17a1580577a860593ca75f681e0bfda8 to your computer and use it in GitHub Desktop.
fn extract_sqrt(mut n: u64) -> (u64, u64) {
let mut blocks = [0u8; 32];
let mut i = 0;
let mut ret = 0u64;
while n != 0 {
blocks[i] = (n & 0b11) as u8;
n >>= 2;
i += 1;
}
let mut q = 0;
let mut a = 0;
let mut r = 0;
let mut z = 0u64;
while i != 0 {
i -= 1;
z = (z - r) * 4 + (blocks[i] as u64);
q = (q * 2 + a) + a;
for a_ in 0..0b11 {
if z < (q * 2 + a_) * a_ {
a = a_ - 1;
break;
}
}
r = (q * 2 + a) * a;
ret = ret * 2 + a;
}
(ret, z - r)
}
fn main() {
assert_eq!(extract_sqrt(5), (2, 1));
assert_eq!(extract_sqrt(10), (3, 1));
assert_eq!(extract_sqrt(25), (5, 0));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment