haar_lib/math/factorial/
bernoulli.rs

1//! ベルヌーイ数
2use crate::math::factorial::FactorialTable;
3use crate::num::ff::*;
4
5/// ベルヌーイ数
6pub trait BernoulliNumber {
7    /// 計算結果の型
8    type Output;
9    /// ベルヌーイ数$B_0 \ldots B_n$を計算する。
10    fn bernoulli_number(&self, n: usize) -> Vec<Self::Output>;
11}
12
13impl<Modulo: FF> BernoulliNumber for FactorialTable<Modulo>
14where
15    Modulo::Element: FFElem + Copy,
16{
17    type Output = Modulo::Element;
18
19    fn bernoulli_number(&self, n: usize) -> Vec<Self::Output> {
20        let mut ret = vec![self.modulo.from_u64(0); n + 1];
21
22        ret[0] = self.modulo.from_u64(1);
23
24        for i in 1..=n {
25            for k in 0..i {
26                let t = ret[k];
27                ret[i] += self.comb(i + 1, k) * t;
28            }
29
30            ret[i] /= self.modulo.from_u64(i as u64 + 1);
31            ret[i] = -ret[i];
32        }
33
34        ret
35    }
36}
37
38#[cfg(test)]
39mod tests {
40    use super::*;
41    use crate::num::const_modint::*;
42
43    #[test]
44    fn test() {
45        let modulo = ConstModIntBuilder::<1000000007>;
46        let ft = FactorialTable::new(100, modulo);
47
48        assert_eq!(
49            ft.bernoulli_number(5),
50            [
51                modulo.from_u64(1),
52                modulo.frac(-1, 2),
53                modulo.frac(1, 6),
54                modulo.from_u64(0),
55                modulo.frac(-1, 30),
56                modulo.from_u64(0)
57            ]
58        );
59    }
60}
haar_lib/math/factorial/bernoulli.rs

haar_lib/math/factorial/
bernoulli.rs
