dahl_salso/
log2cache.rs

1use crate::*;
2
3#[derive(Debug, Clone)]
4pub struct Log2Cache {
5    log2n: Vec<f64>,
6    nlog2n: Vec<f64>,
7    nlog2n_difference: Vec<f64>,
8}
9
10impl Log2Cache {
11    pub fn new(n: usize) -> Self {
12        let mut log2n = Vec::with_capacity(n + 1);
13        let mut nlog2n = Vec::with_capacity(n + 1);
14        let mut nlog2n_difference = Vec::with_capacity(n + 1);
15        log2n.push(0.0);
16        nlog2n.push(0.0);
17        for i in 1..=n {
18            let i = i as f64;
19            let log2i = i.log2();
20            log2n.push(log2i);
21            let ilog2i = i * log2i;
22            let ilog2i_last = *nlog2n.last().unwrap();
23            nlog2n.push(ilog2i);
24            nlog2n_difference.push(ilog2i - ilog2i_last);
25        }
26        // Like the other tables, nlog2n_difference covers 0..=n.
27        let i = (n + 1) as f64;
28        nlog2n_difference.push(i * i.log2() - *nlog2n.last().unwrap());
29        Self {
30            log2n,
31            nlog2n,
32            nlog2n_difference,
33        }
34    }
35
36    pub fn plog2p(&self, x: CountType, n: CountType) -> f64 {
37        let p = (x as f64) / (n as f64);
38        let log2p = self.log2n[x as usize] - self.log2n[n as usize];
39        p * log2p
40    }
41
42    pub fn nlog2n(&self, n: CountType) -> f64 {
43        self.nlog2n[n as usize]
44    }
45
46    pub fn nlog2n_difference(&self, n: CountType) -> f64 {
47        self.nlog2n_difference[n as usize]
48    }
49}
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn tables_cover_zero_through_n() {
57        let n = 5;
58        let cache = Log2Cache::new(n);
59        let f = |k: f64| if k == 0.0 { 0.0 } else { k * k.log2() };
60        for k in 0..=n {
61            let x = k as f64;
62            assert_ulps_eq!(cache.nlog2n(k as CountType), f(x));
63            assert_ulps_eq!(cache.nlog2n_difference(k as CountType), f(x + 1.0) - f(x));
64        }
65        assert_ulps_eq!(cache.plog2p(2, 4), -0.5);
66    }
67
68    #[test]
69    #[should_panic(expected = "index out of bounds")]
70    fn nlog2n_rejects_count_beyond_cache() {
71        let _ = Log2Cache::new(4).nlog2n(60000);
72    }
73
74    #[test]
75    #[should_panic(expected = "index out of bounds")]
76    fn nlog2n_difference_rejects_count_beyond_cache() {
77        let _ = Log2Cache::new(4).nlog2n_difference(5);
78    }
79
80    #[test]
81    #[should_panic(expected = "index out of bounds")]
82    fn plog2p_rejects_count_beyond_cache() {
83        let _ = Log2Cache::new(4).plog2p(1, 5);
84    }
85}
dahl_salso/log2cache.rs

dahl_salso/
log2cache.rs
