bounded_rand_prob.rs

//! Calculates the probabilities of acceptance for various methods of random uniform sampling from 
//! integer ranges.

use std::num::Wrapping;
use std::ops::Neg;

fn wmul(x: u8, y: u8) -> (u8, u8) {
    let m = x as u16 * y as u16;
    let hi = (m >> 8) as u8;
    let lo = m as u8;
    (hi, lo)
}

fn calc_prob(f: impl Fn(u8, u8) -> bool) {
    let mut probs = [0.0; 256];
    for range in 1..=u8::max_value() {
        let mut accept = 0;
        for r in 0..=u8::max_value() {
            if f(r, range) { accept += 1; }
        }
        probs[range as usize] = accept as f64 / 256.0;
    }
    println!("{:?}", probs.to_vec());
}

fn modulo(r: u8, range: u8) -> bool {
    let zone = !0 - Wrapping(range).neg().0 % range;
    let (_, lo) = wmul(r, range);
    lo <= zone
}

fn bitmask(r: u8, mut range: u8) -> bool {
    range -= 1;
    let mask = !0 >> (range | 1).leading_zeros();
    r & mask <= range
}

fn lz_approx(r: u8, range: u8) -> bool {
    let zone = (range << range.leading_zeros()).wrapping_sub(1);
    let (_, lo) = wmul(r, range);
    lo <= zone
}

fn main() {
    calc_prob(modulo);
    calc_prob(bitmask);
    calc_prob(lz_approx);
}