use crate::error::{BarracudaError, Result};
pub const MAX_SOBOL_DIM: usize = 40;
static DIRECTION_NUMBERS: &[&[u32]] = &[
&[1],
&[1, 1],
&[1, 3, 1],
&[1, 3, 3],
&[1, 1, 1],
&[1, 1, 3, 3],
&[1, 3, 5, 13],
&[1, 1, 5, 5, 17],
&[1, 1, 5, 5, 5],
&[1, 1, 7, 11, 19],
&[1, 1, 5, 1, 1],
&[1, 1, 1, 3, 11],
&[1, 3, 5, 5, 31],
&[1, 3, 3, 9, 7, 49],
&[1, 1, 1, 15, 21, 21],
&[1, 3, 1, 13, 27, 49],
&[1, 1, 1, 15, 7, 5],
&[1, 3, 1, 15, 13, 25],
&[1, 1, 5, 5, 19, 61],
&[1, 3, 7, 11, 23, 15, 103],
&[1, 3, 7, 13, 13, 15, 69],
&[1, 1, 3, 13, 7, 35, 63],
&[1, 1, 5, 9, 27, 49, 71],
&[1, 1, 5, 11, 15, 33, 107],
&[1, 3, 1, 3, 13, 39, 127],
&[1, 3, 3, 5, 9, 3, 67],
&[1, 3, 5, 11, 21, 45, 111],
&[1, 3, 7, 13, 21, 27, 51],
&[1, 3, 7, 15, 1, 47, 97],
&[1, 3, 7, 9, 15, 35, 117],
&[1, 1, 1, 3, 31, 49, 89],
&[1, 1, 1, 5, 5, 57, 79],
&[1, 1, 1, 11, 13, 57, 67],
&[1, 1, 3, 1, 13, 63, 75],
&[1, 1, 3, 13, 31, 23, 61],
&[1, 1, 5, 9, 1, 57, 111],
&[1, 1, 7, 3, 17, 57, 53],
&[1, 1, 7, 13, 29, 7, 91],
&[1, 1, 7, 15, 9, 37, 107],
&[1, 3, 1, 1, 17, 41, 75],
];
static POLYNOMIALS: &[u32] = &[
0, 1, 1, 2, 1, 4, 2, 4, 4, 3, 2, 3, 2, 5, 4, 4, 4, 4, 4, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, ];
#[derive(Debug, Clone)]
pub struct SobolGenerator {
dim: usize,
v: Vec<Vec<u32>>,
index: u64,
x: Vec<u32>,
}
impl SobolGenerator {
pub fn new(dim: usize) -> Result<Self> {
if dim == 0 || dim > MAX_SOBOL_DIM {
return Err(BarracudaError::InvalidInput {
message: format!("Dimension must be 1..{MAX_SOBOL_DIM}"),
});
}
let mut v = vec![vec![0u32; 32]; dim];
for d in 0..dim {
if d == 0 {
for (i, v0i) in v[0].iter_mut().enumerate() {
*v0i = 1 << (31 - i);
}
} else {
let m_init = &DIRECTION_NUMBERS[d];
let s = m_init.len();
let poly_degree = POLYNOMIALS[d] as usize;
for (i, &m) in m_init.iter().enumerate() {
v[d][i] = m << (31 - i);
}
let poly = 1u32 << poly_degree; for i in s..32 {
let mut vi = v[d][i - s] >> s;
for j in 1..=poly_degree {
if (poly >> (poly_degree - j)) & 1 == 1 {
vi ^= v[d][i - j];
}
}
vi ^= v[d][i - s];
v[d][i] = vi;
}
}
}
Ok(Self {
dim,
v,
index: 0,
x: vec![0; dim],
})
}
pub fn skip_to(&mut self, n: u64) {
self.index = 0;
self.x.fill(0);
for _ in 0..n {
let _ = self.next_point();
}
}
pub fn next_point(&mut self) -> Vec<f64> {
if self.index == 0 {
self.index = 1;
return vec![0.0; self.dim];
}
let mut i = self.index;
let mut c = 0;
while i & 1 == 1 {
i >>= 1;
c += 1;
}
for d in 0..self.dim {
self.x[d] ^= self.v[d][c];
}
self.index += 1;
let scale = 1.0 / (1u64 << 32) as f64;
self.x.iter().map(|&xi| xi as f64 * scale).collect()
}
pub fn generate(&mut self, n: usize) -> Vec<Vec<f64>> {
(0..n).map(|_| self.next_point()).collect()
}
pub fn reset(&mut self) {
self.index = 0;
self.x.fill(0);
}
#[must_use]
pub fn index(&self) -> u64 {
self.index
}
#[must_use]
pub fn dim(&self) -> usize {
self.dim
}
}
pub fn sobol_sequence(n: usize, dim: usize) -> Result<Vec<Vec<f64>>> {
let mut sampler = SobolGenerator::new(dim)?;
Ok(sampler.generate(n))
}
pub fn sobol_scaled(n: usize, bounds: &[(f64, f64)]) -> Result<Vec<Vec<f64>>> {
let dim = bounds.len();
let points = sobol_sequence(n, dim)?;
Ok(points
.into_iter()
.map(|p| {
p.into_iter()
.zip(bounds.iter())
.map(|(xi, (lo, hi))| lo + xi * (hi - lo))
.collect()
})
.collect())
}
pub fn sobol_sequence_from(n: usize, dim: usize, start_index: u64) -> Result<Vec<Vec<f64>>> {
let mut sampler = SobolGenerator::new(dim)?;
sampler.skip_to(start_index);
Ok(sampler.generate(n))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_sobol_1d() {
let points = sobol_sequence(8, 1).unwrap();
assert_eq!(points.len(), 8);
for p in &points {
assert!(p[0] >= 0.0 && p[0] < 1.0, "Point {} out of range", p[0]);
}
assert!(
points[0][0] < 0.1,
"First point should be near 0, got {}",
points[0][0]
);
}
#[test]
fn test_sobol_2d() {
let points = sobol_sequence(16, 2).unwrap();
assert_eq!(points.len(), 16);
assert_eq!(points[0].len(), 2);
for p in &points {
assert!(p[0] >= 0.0 && p[0] < 1.0);
assert!(p[1] >= 0.0 && p[1] < 1.0);
}
}
#[test]
fn test_sobol_uniformity() {
let n = 1024;
let points = sobol_sequence(n, 2).unwrap();
let mut quadrants = [0; 4];
for p in &points {
let q = usize::from(p[0] >= 0.5) + (if p[1] >= 0.5 { 2 } else { 0 });
quadrants[q] += 1;
}
for count in quadrants {
assert!(
(count as f64 - n as f64 / 4.0).abs() < n as f64 / 8.0,
"Quadrant count {} deviates too much from {}",
count,
n / 4
);
}
}
#[test]
fn test_sobol_scaled() {
let bounds = vec![(0.0, 10.0), (-5.0, 5.0), (100.0, 200.0)];
let points = sobol_scaled(100, &bounds).unwrap();
for p in &points {
assert!(p[0] >= 0.0 && p[0] <= 10.0);
assert!(p[1] >= -5.0 && p[1] <= 5.0);
assert!(p[2] >= 100.0 && p[2] <= 200.0);
}
}
#[test]
fn test_sobol_skip_to() {
let mut sampler1 = SobolGenerator::new(3).unwrap();
let mut sampler2 = SobolGenerator::new(3).unwrap();
for _ in 0..100 {
sampler1.next_point();
}
sampler2.skip_to(100);
let p1 = sampler1.next_point();
let p2 = sampler2.next_point();
for (a, b) in p1.iter().zip(p2.iter()) {
assert!((a - b).abs() < 1e-10, "Mismatch after skip: {a} vs {b}");
}
}
#[test]
fn test_sobol_reset() {
let mut sampler = SobolGenerator::new(2).unwrap();
let first_points: Vec<_> = (0..5).map(|_| sampler.next_point()).collect();
sampler.reset();
let second_points: Vec<_> = (0..5).map(|_| sampler.next_point()).collect();
for (p1, p2) in first_points.iter().zip(second_points.iter()) {
for (a, b) in p1.iter().zip(p2.iter()) {
assert!((a - b).abs() < 1e-14);
}
}
}
#[test]
fn test_sobol_high_dim() {
let points = sobol_sequence(100, 40).unwrap();
assert_eq!(points.len(), 100);
assert_eq!(points[0].len(), 40);
for p in &points {
for &xi in p {
assert!((0.0..1.0).contains(&xi));
}
}
}
#[test]
fn test_sobol_error_dim() {
assert!(SobolGenerator::new(0).is_err());
assert!(SobolGenerator::new(41).is_err());
}
#[test]
fn test_sobol_generator_index() {
let mut sampler = SobolGenerator::new(2).unwrap();
assert_eq!(sampler.index(), 0);
sampler.next_point();
assert_eq!(sampler.index(), 1);
sampler.next_point();
assert_eq!(sampler.index(), 2);
}
#[test]
fn test_sobol_deterministic() {
let p1 = sobol_sequence(10, 3).unwrap();
let p2 = sobol_sequence(10, 3).unwrap();
for (a, b) in p1.iter().zip(p2.iter()) {
for (x, y) in a.iter().zip(b.iter()) {
assert!((x - y).abs() < 1e-14);
}
}
}
#[test]
fn test_sobol_sequence_from() {
let points = sobol_sequence_from(10, 2, 50).unwrap();
assert_eq!(points.len(), 10);
let mut sampler = SobolGenerator::new(2).unwrap();
sampler.skip_to(50);
for p in &points {
let expected = sampler.next_point();
for (a, b) in p.iter().zip(expected.iter()) {
assert!((a - b).abs() < 1e-14);
}
}
}
}