haar_lib/math/fps/
log.rs

1//! 形式的冪級数の対数
2use crate::math::fps::inv::*;
3use crate::math::polynomial::Polynomial;
4use crate::math::prime_mod::PrimeMod;
5use crate::num::ff::*;
6
7/// 形式的冪級数の対数
8pub trait FpsLog {
9    /// 戻り値の型
10    type Output;
11
12    /// $f(x) = \sum_0^{n-1} a_ix^i$について、$\log (f(x))$の先頭$n$項を求める。
13    fn fps_log(self) -> Result<Self::Output, &'static str>;
14}
15
16impl<P: PrimeMod> FpsLog for Polynomial<P> {
17    type Output = Self;
18
19    fn fps_log(self) -> Result<Self::Output, &'static str> {
20        assert_eq!(self.coeff_of(0).value(), 1);
21        let n = self.len();
22        let mut a = self.clone();
23        a.differentiate();
24        let b = self.fps_inv()?;
25        let mut ret = a * b;
26        ret.integrate();
27        ret.as_mut().resize(n, 0.into());
28        Ok(ret)
29    }
30}
haar_lib/math/fps/log.rs

haar_lib/math/fps/
log.rs
