最近学习了多项式的牛顿迭代法,在尝试推 exp 的时候用了一个比较奇怪的操作:
假设需要求 A 的 exp,设 B=eA,那么就有 lnB−A≡0 ( mod xn)。假设现在已经求出了 lnB0−A≡0 ( mod x2n),考虑用 B0 推出 B。
对 lnB 牛顿迭代,那么就有 lnB=lnB0+ln′B0⋅(B−B0)+2ln′′B0⋅(B−B0)2...,然后对 xn 取模,就有 lnB≡lnB0+ln′B0⋅(B−B0) ( mod xn),带回原式,就有 lnB0+ln′B0⋅(B−B0)−A≡ ( mod xn)。因为 ln′x=x1,所以就得到了 B≡B0⋅(A+1−lnB0) ( mod xn)
然后就这样得到了 exp 的递推式,而且还是对的……
并且在这样得到正确的递推式之后,尝试着把它用去求逆,也就是设 B=A−1,那么 B1−A=0,然后求出 B0 后对 B1 进行牛顿迭代,最后也可以得到多项式求逆的正确递推式。
虽然这样可以得到正确结果,但是感觉很奇怪,因为好像网上大多是对 lnB−A=0 这个整体进行牛顿迭代的,也不知道我的做法的正确性,故向各位神犇求助。
感激不尽!!!