// implementing mystical rand5() using existing library
fn rand5() -> u64 {
    rand::random::<u64>() % 5
}

#[macro_use]
extern crate lazy_static;
// static global array of 1, 5, 25, 125, ...
lazy_static! {
    static ref DANGER : u64 = std::u64::MAX / 5;
    static ref POWER5: Vec<u64> = {
        let mut v = Vec::<u64>::with_capacity(30);
        let mut x = 1;
        loop {
            v.push(x);
            if x > *DANGER {
                v.shrink_to_fit();
                return v;
            }
            x *= 5;
        }
    };
}

struct Generator {
    a : u64,
    b : u64,
    p : usize, // denominator is 5^p = POWER5[p]
    // just statistics...
    entropy_input : f64,
    entropy_output : f64,
}

impl Generator {
    fn new() -> Generator {
        Generator{
            a : 0,
            b : 1,
            p : 0,
            entropy_input : 0.0,
            entropy_output : 0.0,
        }
    }

    fn rand(&mut self, n : u32) -> u32 {
        let n = n as u64;
        if (self.b as f64) * (n as f64) > (std::u64::MAX as f64) {
            self.cool_down();
        }
        // now drill down
        loop {
            let res_before_a = self.a * n / POWER5[self.p]; // can optimize this division out
            let res_before_b = self.b * n / POWER5[self.p];
            if res_before_a == res_before_b {
                // our [a/5^p; b/5^p) interval is inside [i/n; (i+1)/n) interval
                self.a = self.a * n - res_before_a * POWER5[self.p];
                self.b = self.b * n - res_before_b * POWER5[self.p];
                self.entropy_output += (n as f64).log(2.0);
                return res_before_b as u32;
            } else {
                // we need go deeper
                if self.b * n > *DANGER {
                    self.cool_down();
                }
                let r5 = rand5();
                self.entropy_input += 5f64.log(2.0);
                let b_a = self.b - self.a;
                self.b = self.a * 5 + (r5 + 1) * b_a;
                self.a = self.a * 5 + r5 * b_a;
                self.p += 1;
            }
        }
    }

    fn cool_down(&mut self) {
        self.a = 0;
        self.b = 1;
        self.p = 0;
        print!("*");
    }
}

fn main() {
    let mut gen = Generator::new();
    for _i in 0..1000 {
        print!("{} ", gen.rand(rand::random::<u32>() % 1000 + 2));
    }
    println!("");
    println!("Entropy consumed: {} bits", gen.entropy_input);
    println!("Entropy produced: {} bits", gen.entropy_output);
}