多项式牛顿迭代
描述
给定多项式
求出模
Newton's Method
考虑倍增。
首先当
假设现在已经得到了模
将
因为
则:
例题
多项式求逆
设给定函数为
应用 Newton's Method 可得:
时间复杂度
多项式开方
设给定函数为
应用 Newton's Method 可得:
时间复杂度
多项式 exp
设给定函数为
应用 Newton's Method 可得:
时间复杂度
最后更新: April 16, 2023
创建日期: March 1, 2019
创建日期: March 1, 2019