我们使用牛顿迭代法计算多项式函数。
对于函数 ln P ( x ) \ln P(x) lnP(x) 来说：
( ln P ( x ) ) ′ = P ′ ( x ) P ( x ) (\ln P(x))' = \frac{P'(x)}{P(x)} (lnP(x))′=P(x)P′(x)
所以我们能在 O ( n log n ) O(n \log n) O(nlogn) 的时间内计算出 ln P ( x ) \ln P(x) lnP(x) 。
已知 e P ( x ) = Q ( x ) e^{P(x)} = Q(x) eP(x)=Q(x) ，那么 ln Q ( x ) = P ( x ) \ln Q(x) = P(x) lnQ(x)=P(x) 即解 F ( Q ) = ln Q − P = 0 F(Q) = \ln Q - P = 0 F(Q)=lnQ−P=0 。
根据牛顿迭代法 F ( Q ) = ln Q − P F(Q) = \ln Q - P F(Q)=lnQ−P 并且 F ′ ( Q ) = 1 Q F'(Q) = \frac{1}{Q} F′(Q)=Q1 。带入牛顿迭代式得到：
Q k + 1 = Q k − ( ln Q k − P ) Q k = Q k ( 1 + P − ln Q k ) Q_{k+1} = Q_k - (\ln Q_k - P)Q_k = Q_k(1+P-\ln Q_k) Qk+1=Qk−(lnQk−P)Qk=Qk(1+P−lnQk)
已知 P ( x ) = Q ( x ) \sqrt{P(x)} = Q(x) P(x)=Q(x) ，那么 P ( x ) = Q ( x ) 2 P(x) = Q(x)^2 P(x)=Q(x)2 即解 F ( Q ) = Q 2 − P = 0 F(Q) = Q^2 - P = 0 F(Q)=Q2−P=0 。
根据牛顿迭代法 F ( Q ) = Q 2 − P F(Q) = Q^2 - P F(Q)=Q2−P 并且 F ′ ( Q ) = 2 Q F'(Q) = 2Q F′(Q)=2Q 。带入牛顿迭代式得到：
Q k + 1 = Q k − Q k 2 − P 2 Q k Q_{k+1} = Q_k - \frac{Q_k^2 - P}{2Q_k} Qk+1=Qk−2QkQk2−P