# Paterson-Stockmeyer an algorithm for evaluating a polynomial at a point that uses $\sqrt{n}$ non scalar multiplications. This is more efficient than Horner's method that uses $n$ non scalar multiplications. It uses giant-baby steps to compute $P(x)=\sum_{i=0}^n a_i x^i$ : choose block size $m\approx \sqrt{n}$ , then $P(x)=\sum_{j=0}^{m-1}\Bigg(\bigg( \sum_{i=0}^{m-1}a_{i+jm}x^i\bigg)x^{jm}\Bigg)=\sum_{j=0}^{m-1}\Bigg(\bigg( \sum_{i=0}^{m-1}a_{i+jm}x^i\bigg)(x^{m})^j\Bigg)$ - precompute $x^2,x^3,...,x^m$ (i.e., $\sqrt{n}$ non-scalar multiplications) - compute the inner sums. It does not use non-scalar multiplication - compute the outer sum using [[Horner's method]] w.r.t polynomial in $X^m$ that uses $m$ non-constant multiplications i.e., for $q_j(x)=\sum_{i=0}^{m-1}a_{i+jm}x^i$ , we have $P(x)=\sum_{j=0}^{m-1} q_j(x)\cdot(x^m)^j$ and $ P(x)=\bigg(\cdots \big(q_{m-1}(x)\cdot x^m + q_{m-2}(x)\big)x^m\cdots\bigg)x^m+q_0(x) $ - DO NOT precompute $x^m,(x^m)^2,...$ as we use Horner method to compute the outer sum. - total computation requires $2\sqrt{n}$ non-scalar multiplications. ## Recursive refined version The following is based on the algorithm in [^1] . It is different from the BSGS algorithm above. It has close to optimal non-constant multiplications of $\sqrt{n/2}$ compared to $2\sqrt n$ in the above. Assume first that you want to evaluate $P(u)$ where $P(x)$ has degree $k(2p-1)$ , $p$ is a 2-power and $k\in\mathbb{Z}^+$. Precompute $u^2,...,u^k$ and $u^{2k},u^{4k},...,u^{2^{m-1}k}$. Divide $P(x)$ by $X^{kp}$, we get $Q(X),R(X)$ s.t. $(1)\ \ P(X)=X^{kp}Q(X)+R(X)$, $deg(Q)=k(p-1)$ and $deg(R)<kp$. Divide $R(X)-X^{kp-1}$ by $Q(X)$, we get $C(X),S(X)$ s.t., $R(X)-X^{kp-1}=Q(X)C(X)+S(X)$ , $deg(C)\le k-1$ and $deg(S)<k(p-1)$. Substituting $R$ in (1), $P(X)=\big(X^{kp}+C(X)\big)Q(X)+\big(X^{k(p-1)}+S(X)\big)$ note that $u^{kp}$ was already precomputed and $C(u)$ can be computed from the precomputed values without computing new powers of $u$. We need to compute recursively $Q(X)$ and $\big(X^{k(p-1)}+S(X)\big)$ where both have degree $k(p-1)$ which fits the initial constraints of $P$. If the original degree of $P$ is not $k(2p-1)$ then we repeat the above for $\hat{P}(X)=X^{k(2^m-1)}+P(X)$ where $k=\sqrt{n/2}$ and $m=\log_2(n/k+1)$. References: 1. [Paterson-Stockmeyer paper](https://www.researchgate.net/profile/Mike-Paterson/publication/220617048_On_the_Number_of_Nonscalar_Multiplications_Necessary_to_Evaluate_Polynomials/links/5630d22408aef3349c29f8c1/On-the-Number-of-Nonscalar-Multiplications-Necessary-to-Evaluate-Polynomials.pdf) 2. [[@my presentation on Paterson-Stockmeyer]] Related: [[Exponentiation by squaring]] ## Created 2022-02-22 11:21