haar_lib/math/fps/
exp.rs

1//! 形式的冪級数の指数関数
2use crate::math::fps::log::*;
3use crate::math::polynomial::{Polynomial, PolynomialOperator};
4
5/// 形式的冪級数の指数関数
6pub trait FpsExp {
7    /// 多項式の型
8    type Poly;
9
10    /// $f(x) = \sum_0^{n-1} a_ix^i$について、$\exp (f(x))$の先頭$n$項を求める。
11    fn fps_exp(&self, f: Self::Poly) -> Self::Poly;
12}
13
14impl<const P: u32, const PR: u32> FpsExp for PolynomialOperator<'_, P, PR> {
15    type Poly = Polynomial<P>;
16
17    fn fps_exp(&self, f: Self::Poly) -> Self::Poly {
18        let f: Vec<_> = f.into();
19        let n = f.len();
20
21        let mut t = 1;
22        let mut b = Polynomial::constant(1.into());
23
24        loop {
25            let mut temp: Vec<_> = self.fps_log(b.clone()).into();
26
27            temp.resize(2 * t, 0.into());
28            temp.iter_mut().for_each(|x| *x = -*x);
29            temp[0] += 1.into();
30
31            temp.iter_mut()
32                .zip(f.iter())
33                .for_each(|(temp, f)| *temp += *f);
34
35            b = self.mul(b, temp.into());
36            b.as_mut().resize(2 * t, 0.into());
37
38            if t >= n {
39                break;
40            }
41
42            t <<= 1;
43        }
44
45        b.as_mut().truncate(n);
46        b
47    }
48}
haar_lib/math/fps/exp.rs

haar_lib/math/fps/
exp.rs
