#low-discrepancy #monte-carlo #quasirandom #sampling #sobol

no-std sobol_burley

A seedable Owen-scrambled Sobol sequence

6 releases (breaking)

0.5.0 Jul 5, 2023
0.4.0 Jul 17, 2022
0.3.1 May 16, 2021
0.2.0 May 12, 2021
0.1.0 May 11, 2021

#181 in Math

Download history 31/week @ 2023-10-19 49/week @ 2023-10-26 63/week @ 2023-11-02 41/week @ 2023-11-09 30/week @ 2023-11-16 56/week @ 2023-11-23 86/week @ 2023-11-30 27/week @ 2023-12-07 32/week @ 2023-12-14 38/week @ 2023-12-21 35/week @ 2023-12-28 31/week @ 2024-01-04 38/week @ 2024-01-11 32/week @ 2024-01-18 42/week @ 2024-01-25 24/week @ 2024-02-01

140 downloads per month
Used in 2 crates

MIT/Apache

43KB
708 lines

Sobol-Burley

Latest Release Documentation

A seedable Owen-scrambled Sobol sequence based on the paper Practical Hash-based Owen Scrambling by Brent Burley, but with an improved hash from Building a Better LK Hash and more dimensions due to Kuo et al.

This crate is geared towards practical graphics applications, and as such has some limitations:

  • The maximum sequence length is 2^16.
  • The maximum number of dimensions is 256 (although this can be worked around with seeding).
  • Only f32 output is supported.

These are all trade-offs for the sake of better performance and a smaller memory footprint.

Expanding this crate to be more suitable for a wider range of applications is a tentative goal for the future. However, efficient execution for graphics applications will always be the top priority.

Basic usage

Basic usage is pretty straightforward:

use sobol_burley::sample;

// Print 1024 3-dimensional points.
for i in 0..1024 {
    let x = sample(i, 0, 0);
    let y = sample(i, 1, 0);
    let z = sample(i, 2, 0);
    println!("({}, {}, {})", x, y, z);
}

The first parameter of sample() is the index of the sample you want, and the second parameter is the index of the dimension you want. The parameters are zero-indexed, and outputs are in the interval [0, 1).

If all you want is a single Owen-scrambled Sobol sequence, then this is all you need. For more advanced usage, see the crate documentation.

Why Owen-scrambled Sobol?

There are other resources that explain this properly and in-depth, including Brent Burley's paper linked above. But here's the short version just to give some intuition:

If you use random points, you get this:

1024 random points

If you use plain Sobol, you get this:

1024 random points

But if you use Owen-scrambled Sobol, you get this:

1024 random points

Random points have an uneven distribution, and plain Sobol exhibits a strong structure that can result in bias and artifacts. But Owen-scrambled Sobol in some sense gets the best of both worlds: the even distribution of Sobol, but randomized to minimize structure.

Unsafe code

This crate uses unsafe code for SIMD acceleration. For 100% safe code, you can disable SIMD support via the simd feature flag (enabled by default).

License

The main code in this project is licensed under either of

at your option.

The Sobol direction numbers under direction_numbers/ and some of the code in build.rs (demarcated by comments) is adapted from work by Stephen Joe and Frances Y. Kuo, and is under the 3-clause BSD license. See licenses/JOE_KUO.txt for details.

Contributing

Contributions are absolutely welcome! Please keep in mind that this crate aims to be:

  • no-std and allocation-free. PRs that use allocation, etc. are very likely to be rejected.
  • As small as it reasonably can be, including transitive dependencies. PRs that pull in dependencies--especially deep dependency trees--are likely to be rejected unless they really pull their weight.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this project by you will be licensed as above (MIT/Apache dual-license), without any additional terms or conditions.

No runtime deps