use xingo_sparse::Real;
use crate::real::{le_exact, lt};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum Sketch {
#[default]
Gaussian,
Rademacher,
}
const SPLITMIX_GAMMA: u64 = 0x9e37_79b9_7f4a_7c15;
const SPLITMIX_M1: u64 = 0xbf58_476d_1ce4_e5b9;
const SPLITMIX_M2: u64 = 0x94d0_49bb_1331_11eb;
const LN2_A: f64 = f64::from_bits(0x3fe6_2e42_fefa_3800);
const LN2_B: f64 = f64::from_bits(0x3d2e_f357_93c7_6730);
const LN2_C: f64 = f64::from_bits(0x398f_97b5_7a07_9a19);
const W_BAR: f64 = 0.029_437_251_522_859_417;
const EXPONENT_MASK: u64 = 0x7ff0_0000_0000_0000;
const TWO_54: f64 = 18_014_398_509_481_984.0;
#[derive(Clone, Debug)]
pub(crate) struct Rng {
s: [u64; 4],
}
impl Rng {
pub(crate) fn new(seed: u64) -> Self {
let mut x = seed;
let mut s = [0; 4];
for w in &mut s {
x = x.wrapping_add(SPLITMIX_GAMMA);
let mut z = x;
z = (z ^ (z >> 30)).wrapping_mul(SPLITMIX_M1);
z = (z ^ (z >> 27)).wrapping_mul(SPLITMIX_M2);
*w = z ^ (z >> 31);
}
debug_assert_ne!(s, [0; 4], "(G1) SplitMix64 never gives four zeros");
Self { s }
}
pub(crate) fn next_u64(&mut self) -> u64 {
let s = &mut self.s;
let out = s[0].wrapping_add(s[3]).rotate_left(23).wrapping_add(s[0]);
let t = s[1] << 17;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = s[3].rotate_left(45);
out
}
#[allow(clippy::cast_precision_loss)] pub(crate) fn uniform(&mut self) -> f64 {
const TWO_M53: f64 = 1.0 / 9_007_199_254_740_992.0;
(self.next_u64() >> 11) as f64 * TWO_M53
}
pub(crate) fn gaussian(&mut self) -> f64 {
loop {
let u = 2.0 * self.uniform() - 1.0;
let v = 2.0 * self.uniform() - 1.0;
let s = u * u + v * v;
if lt(0.0, s) && lt(s, 1.0) {
return u * ((-2.0 * ln(s)) / s).sqrt();
}
}
}
pub(crate) fn rademacher(&mut self) -> f64 {
if self.next_u64() >> 63 == 1 {
-1.0
} else {
1.0
}
}
pub(crate) fn deviate(&mut self, sketch: Sketch) -> f64 {
match sketch {
Sketch::Rademacher => self.rademacher(),
Sketch::Gaussian => self.gaussian(),
}
}
pub(crate) fn fill<T: Real>(&mut self, sketch: Sketch, data: &mut [T]) {
for v in data {
*v = T::from_f64(self.deviate(sketch));
}
}
}
#[allow(clippy::cast_sign_loss)] fn pow2(k: i32) -> f64 {
debug_assert!((-1022..=1023).contains(&k));
f64::from_bits(((k + 1023) as u64) << 52)
}
fn series_degree<T: Real>() -> usize {
let target = T::EPSILON.to_f64() / 8.0;
let mut wp = W_BAR; let mut n = 0usize;
loop {
#[allow(clippy::cast_precision_loss)]
let den = (2 * n + 3) as f64 * (1.0 - W_BAR);
if le_exact(wp / den, target) {
return n;
}
wp *= W_BAR;
n += 1;
}
}
pub(crate) fn ln<T: Real>(x: T) -> T {
debug_assert!(x.is_finite() && lt(T::ZERO, x), "Algorithm L needs x > 0");
let mut x = x;
let mut e_adj = 0i32;
let mut bits = x.to_f64().to_bits();
if bits & EXPONENT_MASK == 0 {
x *= T::from_f64(TWO_54);
e_adj = -54;
bits = x.to_f64().to_bits();
}
#[allow(clippy::cast_possible_truncation, clippy::cast_possible_wrap)]
let mut e = ((bits & EXPONENT_MASK) >> 52) as i32 - 1023;
let half = -e / 2;
let mut m = x * T::from_f64(pow2(half)) * T::from_f64(pow2(-e - half));
if lt(T::from_f64(core::f64::consts::SQRT_2), m) {
m *= T::from_f64(0.5);
e += 1;
}
e += e_adj;
let z = (m - T::ONE) / (m + T::ONE);
let w = z * z;
let n = series_degree::<T>();
let coef = |i: usize| {
#[allow(clippy::cast_precision_loss)]
let d = (2 * i + 1) as f64;
T::ONE / T::from_f64(d)
};
let mut p = coef(n);
for i in (0..n).rev() {
p = p * w + coef(i);
}
let l = T::from_f64(2.0) * z * p;
if e == 0 {
return l;
}
let ef = T::from_f64(f64::from(e));
let t = ef * T::from_f64(LN2_B) + ef * T::from_f64(LN2_C);
ef * T::from_f64(LN2_A) + (l + t)
}
#[cfg(test)]
#[allow(
clippy::float_cmp,
clippy::cast_precision_loss,
clippy::unreadable_literal // frozen bit patterns
)]
mod tests {
use super::*;
use xingo_extprec::DoubleDouble as Dd;
#[test]
fn xoshiro_matches_the_reference_outputs() {
let mut r = Rng { s: [1, 2, 3, 4] };
let expected: [u64; 10] = [
41_943_041,
58_720_359,
3_588_806_011_781_223,
3_591_011_842_654_386,
9_228_616_714_210_784_205,
9_973_669_472_204_895_162,
14_011_001_112_246_962_877,
12_406_186_145_184_390_807,
15_849_039_046_786_891_736,
10_450_023_813_501_588_000,
];
for e in expected {
assert_eq!(r.next_u64(), e);
}
}
#[test]
fn sequence_of_seed_zero_is_frozen() {
let mut r = Rng::new(0);
assert_eq!(r.s, FROZEN_STATE_0);
let mut r1 = Rng::new(1);
let raw: Vec<u64> = (0..4).map(|_| r1.next_u64()).collect();
assert_eq!(raw, FROZEN_RAW_1);
let g: Vec<u64> = (0..64).map(|_| r.gaussian().to_bits()).collect();
assert_eq!(g, FROZEN_GAUSS_0);
let mut rr = Rng::new(0);
let signs: Vec<f64> = (0..16).map(|_| rr.rademacher()).collect();
assert_eq!(signs, FROZEN_RADEMACHER_0);
}
const FROZEN_STATE_0: [u64; 4] = [
16294208416658607535,
7960286522194355700,
487617019471545679,
17909611376780542444,
];
const FROZEN_RAW_1: [u64; 4] = [
14971601782005023387,
13781649495232077965,
1847458086238483744,
13765271635752736470,
];
const FROZEN_GAUSS_0: [u64; 64] = [
0xbff8a8af17f2fe67,
0xbf708d7cb6a3955d,
0x3fbc958a80b0b8e6,
0xbfca60c5aa96ee22,
0xbfc8321083be657e,
0xbfe53100de8d3b86,
0x3fd233ab345f0647,
0xbffada9d88a0b370,
0xbfd9624e017442d8,
0xbff12f999b7f0784,
0xbfed1aaaa24ca640,
0xbff6a4ba59fafe1d,
0xbfd81899a654bd69,
0x3fd5e96343423eec,
0x3fa70d7e06e38361,
0x3fe258602afb1018,
0x3fe1c8af537e33dd,
0xbfc534af346ec048,
0xbfdde34fc2b742fa,
0xbff88db52ac5488e,
0x40046727b91817bf,
0x3fd57ba2329c55b9,
0x3ffc30ea6e625005,
0xbff651eca0888b18,
0x3fe399d771a6dede,
0xbfc8ae207ae66069,
0xbfe511bbf0d3868f,
0x3fd1e2d26a847ade,
0x3fe67e6ce7ea2ca3,
0x3ff3fd13aa3ae25f,
0x3ff9b1584aa24b3e,
0x3fe83534195628a4,
0x3fefa20547b88b13,
0x3ffdb0421ff79616,
0x3fdc9c2a580e3862,
0x3fdaa737134ed9c0,
0xbfe7774cdecdb232,
0x3fbcb2cf25eb1719,
0xbff3ae5d8e9d3e80,
0xbf59230c30a61bfa,
0x3ff1a35b827f0a06,
0x3fe33bceec22e0af,
0xbff62602652954ec,
0x3fee65bff8eaacf1,
0xbff1604ce70bb525,
0xbff2a3b0ab926856,
0xbfce454bf4ff4b01,
0x3fec727727057ace,
0x3ff08305cdbc9f80,
0x3ff501fe9e282575,
0x3fc786802bf04146,
0xbff77ee7a0537b14,
0x3fe1ae9378cd2d2a,
0xbfeec1282ba1af9d,
0x3ff34afa4b3870ba,
0x3ff205d8dc9f3a5f,
0xbff08d8b20cb5b2e,
0xbfede4e70a407787,
0xbfe7399116c7218a,
0x3fe6b38b58b12210,
0x3fe39f58ac2a7984,
0x3fe10b5b38bf6349,
0x3ffa0c12c6765728,
0x3ff5b042b55ceec0,
];
const FROZEN_RADEMACHER_0: [f64; 16] = [
1.0, 1.0, 1.0, 1.0, 1.0, 1.0, -1.0, -1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
];
#[test]
fn deviates_have_the_moments_of_a_standard_gaussian() {
let mut r = Rng::new(42);
let n = 200_000;
let (mut s1, mut s2, mut s4) = (0.0, 0.0, 0.0);
for _ in 0..n {
let g = r.gaussian();
s1 += g;
s2 += g * g;
s4 += g * g * g * g;
}
let n = f64::from(n);
assert!((s1 / n).abs() < 0.01, "mean {}", s1 / n);
assert!((s2 / n - 1.0).abs() < 0.015, "variance {}", s2 / n);
assert!((s4 / n - 3.0).abs() < 0.08, "fourth moment {}", s4 / n);
let mut rr = Rng::new(42);
let plus = (0..10_000).filter(|_| rr.rademacher() > 0.0).count();
assert!((4800..5200).contains(&plus));
let u: f64 = (0..10_000).map(|_| rr.uniform()).sum::<f64>() / 10_000.0;
assert!((u - 0.5).abs() < 0.01);
}
fn ln_arguments() -> Vec<f64> {
let mut r = Rng::new(7);
let mut xs = vec![1.0, 2.0, 0.5, core::f64::consts::SQRT_2, f64::MIN_POSITIVE];
xs.push(f64::MAX);
for k in 1..53 {
let d = pow2(-k);
xs.extend([1.0 + d, 1.0 - d / 2.0]);
}
for e in -1022..1024 {
for _ in 0..40 {
xs.push((1.0 + r.uniform()) * pow2(e.min(1023)));
}
}
for _ in 0..100_000 {
let s = r.uniform();
if s > 0.0 {
xs.push(s);
}
}
xs
}
fn rel_err_u(own: Dd, oracle: Dd, u: f64) -> f64 {
if oracle == Dd::ZERO {
return if own == Dd::ZERO { 0.0 } else { f64::INFINITY };
}
((own - oracle) / oracle).abs().to_f64() / u
}
#[test]
fn ln_in_f64_is_within_the_proven_bound() {
let u = f64::EPSILON / 2.0;
let mut worst = 0.0f64;
for x in ln_arguments() {
let e = rel_err_u(Dd::from_f64(ln(x)), Dd::from_f64(x).ln(), u);
assert!(e <= 6.4, "ln({x:e}): {e} u");
worst = worst.max(e);
}
assert_eq!(ln(1.0), 0.0);
assert_eq!(series_degree::<f64>(), 9);
eprintln!("ln f64: max relative error {worst:.3} u");
}
#[test]
fn ln_in_double_double_is_within_a_few_units() {
let u = Dd::EPSILON.to_f64() / 2.0;
let mut worst = 0.0f64;
let mut r = Rng::new(9);
for x in ln_arguments().into_iter().step_by(4) {
let xd = Dd::from_f64(x) * (Dd::ONE + Dd::from_f64(r.uniform() * f64::EPSILON));
if !(xd.to_f64() > 0.0 && xd.is_finite()) {
continue;
}
let e = rel_err_u(ln(xd), xd.ln(), u);
assert!(e <= 16.0, "ln({x:e}) in dd: {e} u");
worst = worst.max(e);
}
assert_eq!(series_degree::<Dd>(), 19);
eprintln!("ln dd: max relative error {worst:.3} u (oracle error included)");
}
#[test]
fn ln2_split_and_subnormal_reduction() {
let ln2 = Dd::from_f64(2.0).ln();
let split = Dd::from_f64(LN2_A) + Dd::from_f64(LN2_B) + Dd::from_f64(LN2_C);
assert!(((split - ln2) / ln2).abs().to_f64() < 1e-31);
assert_eq!(LN2_A.to_bits() & 0x7ff, 0, "A has 42 significant bits");
let w = ((2f64.sqrt() - 1.0) / (2f64.sqrt() + 1.0)).powi(2);
assert!((W_BAR - w).abs() < 1e-16);
for x in [f64::MIN_POSITIVE / 3.0, 5e-324, 1e-310] {
let e = rel_err_u(
Dd::from_f64(ln(x)),
Dd::from_f64(x).ln(),
f64::EPSILON / 2.0,
);
assert!(e <= 6.4, "{x:e}: {e}");
}
}
}