#[inline]
pub(crate) fn sqrt(value: f32) -> f32 {
if value == 2.0 {
core::f32::consts::SQRT_2
} else {
libm::sqrtf(value)
}
}
pub(crate) const LANES: usize = 8;
#[inline(always)]
pub(crate) fn sqrt8(values: [f32; LANES]) -> [f32; LANES] {
if !values
.iter()
.all(|v| v.to_bits().wrapping_sub(0x0080_0000) < 0x7f00_0000)
{
return values.map(sqrt);
}
let mut operand = [0f64; LANES];
let mut root = [0f64; LANES];
for i in 0..LANES {
operand[i] = values[i] as f64;
root[i] = f64::from_bits((operand[i].to_bits() >> 1) + 0x1ff8_0000_0000_0000);
}
for _ in 0..3 {
for i in 0..LANES {
root[i] = 0.5 * (root[i] + operand[i] / root[i]);
}
}
let mut result = [0f32; LANES];
for i in 0..LANES {
let rounded = root[i] as f32;
let bits = rounded.to_bits();
let r = rounded as f64;
let up = (f32::from_bits(bits + 1) as f64 + r) * 0.5;
let down = (f32::from_bits(bits - 1) as f64 + r) * 0.5;
let bits = bits + u32::from(operand[i] > up * up) - u32::from(operand[i] < down * down);
result[i] = f32::from_bits(bits);
}
result
}
#[derive(Clone, Copy)]
pub(crate) struct RootEstimate {
pub(crate) value: f32,
pub(crate) estimate: f32,
}
pub(crate) const NEWTON_LOW: f32 = 0.998;
pub(crate) const NEWTON_HIGH: f32 = 1.000_001;
const fn table_root(x: f64) -> f64 {
let mut r = 2.0;
let mut i = 0;
while i < 64 {
r = 0.5 * (r + x / r);
i += 1;
}
r
}
const fn root_table(high: bool) -> [f32; 256] {
let mut table = [0f32; 256];
let mut i = 0;
while i < 256 {
let scale = if i >= 128 { 2.0 } else { 1.0 };
let j = (i % 128) as f64;
table[i] = if high {
(table_root(scale * (1.0 + (j + 1.0) / 128.0)) * (1.0 + 1e-6)) as f32
} else {
(table_root(scale * (1.0 + j / 128.0)) * (1.0 - 1e-6)) as f32
};
i += 1;
}
table
}
static ROOT_LOW: [f32; 256] = root_table(false);
static ROOT_HIGH: [f32; 256] = root_table(true);
const fn inverse_root_table(high: bool) -> [f32; 256] {
let mut table = [0f32; 256];
let mut i = 0;
while i < 256 {
let scale = if i >= 128 { 2.0 } else { 1.0 };
let j = (i % 128) as f64;
table[i] = if high {
(1.0 / table_root(scale * (1.0 + j / 128.0)) * (1.0 + 1e-6)) as f32
} else {
(1.0 / table_root(scale * (1.0 + (j + 1.0) / 128.0)) * (1.0 - 1e-6)) as f32
};
i += 1;
}
table
}
static INVERSE_LOW: [f32; 256] = inverse_root_table(false);
static INVERSE_HIGH: [f32; 256] = inverse_root_table(true);
impl RootEstimate {
#[inline(always)]
pub(crate) fn new(value: f32) -> Option<Self> {
let bits = value.to_bits();
if !(0x0d80_0000..0x7f80_0000).contains(&bits) {
return None;
}
Some(Self {
value,
estimate: f32::from_bits((bits >> 1) + 0x1fc0_0000),
})
}
#[inline(always)]
pub(crate) fn table(self) -> (f32, f32) {
let bits = self.value.to_bits();
let biased = bits >> 23;
let p = (biased & 1) ^ 1;
let k = (biased as i32 - 127 - p as i32) >> 1;
let index = (p << 7 | (bits >> 16) & 127) as usize;
let scale = f32::from_bits(((k + 127) as u32) << 23);
(ROOT_LOW[index] * scale, ROOT_HIGH[index] * scale)
}
#[inline(always)]
pub(crate) fn inverse_table(self) -> (f32, f32) {
let bits = self.value.to_bits();
let biased = bits >> 23;
let p = (biased & 1) ^ 1;
let k = (biased as i32 - 127 - p as i32) >> 1;
let index = (p << 7 | (bits >> 16) & 127) as usize;
let scale = f32::from_bits(((127 - k) as u32) << 23);
(INVERSE_LOW[index] * scale, INVERSE_HIGH[index] * scale)
}
#[inline(always)]
pub(crate) fn newton(self) -> f32 {
0.5 * (self.estimate + self.value / self.estimate)
}
#[inline(always)]
pub(crate) fn bounds(self) -> (f32, f32) {
let newton = self.newton();
(newton * NEWTON_LOW, newton * NEWTON_HIGH)
}
}
#[inline(always)]
pub(crate) fn root_at_least(square: f32, limit: f32) -> bool {
match RootEstimate::new(square) {
Some(root) => root.table().0 >= limit || root.bounds().0 >= limit,
None => false,
}
}
pub(crate) struct SqrtCache {
entries: [(u32, f32); 512],
}
impl SqrtCache {
pub(crate) const fn new() -> Self {
Self {
entries: [(0, 0.0); 512],
}
}
#[inline(always)]
pub(crate) fn sqrt(&mut self, value: f32) -> f32 {
let bits = value.to_bits();
let bucket = (bits.wrapping_mul(0x9e3779b9) >> 23) as usize;
let entry = &mut self.entries[bucket];
if entry.0 != bits {
*entry = (bits, sqrt(value));
}
entry.1
}
}
#[cfg(test)]
mod tests {
#[test]
fn constant_normalization_root_matches_pinned_backend() {
assert_eq!(super::sqrt(2.0).to_bits(), libm::sqrtf(2.0).to_bits());
}
use super::*;
#[test]
fn sqrt8_matches_backend() {
let mut values = alloc::vec::Vec::new();
for exponent in 0u32..512 {
for mantissa in (0u32..1 << 23).step_by(8191).chain([1, 0x7fffff]) {
values.push(f32::from_bits(exponent << 23 | mantissa));
}
}
values.extend([0.0, -0.0, f32::INFINITY, f32::NAN, f32::MIN_POSITIVE, 1.0]);
for chunk in values.chunks(LANES) {
let mut lanes = [1.0f32; LANES];
lanes[..chunk.len()].copy_from_slice(chunk);
for (root, value) in sqrt8(lanes).iter().zip(lanes) {
assert_eq!(
root.to_bits(),
sqrt(value).to_bits(),
"{:08x}",
value.to_bits()
);
}
}
}
#[test]
fn bounds_hold_for_every_operand_class() {
let mut checked = 0;
for exponent in 0u32..256 {
for mantissa in (0u32..1 << 23).step_by(4093).chain([0x7fffff]) {
let bits = exponent << 23 | mantissa;
let value = f32::from_bits(bits);
let Some(root) = RootEstimate::new(value) else {
assert!(!(0x0d80_0000..0x7f80_0000).contains(&bits));
continue;
};
let s = sqrt(value);
let (low, high) = root.bounds();
let (table_low, table_high) = root.table();
assert!(table_low <= s && s <= table_high, "{bits:08x}");
let (inverse_low, inverse_high) = root.inverse_table();
let inverse = 1. / s;
assert!(
inverse_low <= inverse && inverse <= inverse_high,
"{bits:08x}"
);
assert!(low <= s && s <= high, "{bits:08x}");
checked += 1;
}
}
assert!(checked > 400_000);
assert!(RootEstimate::new(0.0).is_none() && RootEstimate::new(-1.0).is_none());
assert!(RootEstimate::new(f32::INFINITY).is_none());
}
#[test]
fn cache_preserves_full_bits_through_collisions_and_special_values() {
let mut cache = SqrtCache::new();
let mut compare = |bits| {
let value = f32::from_bits(bits);
let expected = sqrt(value).to_bits();
assert_eq!(cache.sqrt(value).to_bits(), expected);
assert_eq!(cache.sqrt(value).to_bits(), expected);
};
for bits in [
0, 0x80000000, 1, 0x7fffff, 0x800000, 0x7f7fffff, 0x7f800000, 0xff800000, 0x7fc00123,
0x3f800000,
] {
compare(bits);
}
let mut previous = [None; 512];
let mut collisions = 0;
for bits in 0x3f000000u32..0x3f001000 {
let bucket = (bits.wrapping_mul(0x9e3779b9) >> 23) as usize;
if let Some(old) = previous[bucket] {
compare(old);
compare(bits);
collisions += 1;
}
previous[bucket] = Some(bits);
}
assert!(collisions > 3000);
let mut bits = 0x12345678u32;
for _ in 0..65536 {
bits = bits.wrapping_mul(1664525).wrapping_add(1013904223);
compare(bits);
}
}
}