Polynomial evaluation
\frac{p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + p_3 ⋅ x^3 + p_4 ⋅ x^4 + p_5 ⋅ x^5} {q_0 + q_1 ⋅ x + q_2 ⋅ x^2 + q_3 ⋅ x^3 + q_4 ⋅ x^4 + q_5 ⋅ x^5 + x^6}
Basic algorithms
Horners rule
For Monomial basis
=
= * +
= * +
= * +
= * +
= * +
= +
= * +
= * +
= * +
= * +
= * +
= /
Clenshaw algorithm
Generalization, specifically for Chebyshev basis.
https://en.wikipedia.org/wiki/Clenshaw_algorithm
De Castlejau's algorithm
For Bernstein basis
https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm
https://en.wikipedia.org/wiki/De_Boor%27s_algorithm
Easy polynomials
https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity
https://en.wikipedia.org/wiki/Exponentiation_by_squaring
https://en.wikipedia.org/wiki/Addition-chain_exponentiation
https://en.wikipedia.org/wiki/Vectorial_addition_chain
WNAF, Pippenger's algorithm, etc.
Preprocessing
y = p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + p_3 ⋅ x^3 + x^4
would take three multiplications to evaluate
= +
= * +
= * +
= * +
but can also be evaluated using only two by
\begin{aligned} a &= (x + β_0) ⋅ x + β_1 & y &= (a + β_2) ⋅ a + β_3 \end{aligned}
with
\begin{aligned} β_0 &= \frac12\p{a_3 - 1} & z &= a_2 - β_0 ⋅ \p{β_0 + 1} & β_1 &= a_1 - β_0 ⋅ z \\ β_2 &= z - 2 ⋅ β_1 & β_3 &= a_0 - β_1 ⋅ \p{β_1 + β_2} \end{aligned}
= +
= ⋅ +
= +
= ⋅ +
Pan's scheme for one polynomial
See §3.3 of the Pan's 1966 paper.
Assuming p monic
= *
= +
= +
= * +
= * +
= * +
= * +
# Output formulas
=
= * +
= * +
= * +
=
= * +
= * +
= * +
=
= * +
= * +
= * +
(6,7)-term rat scheme: 4 + 5 muls.
p5 & p6
= *
= +
= +
= * +
= * +
= +
= * +
= * +
= * +
above: 1 + 2 + 3 = 6 muls.
knuth explicits: 3 + 3 = 6 muls
p(x) = p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + p_3 ⋅ x^3 + p_4 ⋅ x^4 + x^5
q(x) = q_0 + q_1 ⋅ x + q_2 ⋅ x^2 + q_3 ⋅ x^3 + q_4 ⋅ x^4 + q_5 ⋅ x^5 + x^6
Paterson-Stockmeyer
Consider the n-term monic polynomial where n = 2 ⋅ k
p(x) = p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + \cdots + p_{n-2} ⋅ x^{n-2} + x^{n-1}
We can rewrite it using two k-term monic polynomial p_1 and p_2:
p(x) = p_1(x) + (x^k + a) ⋅ p_2(x)
Where a = p_{k-1} -1 and p_2 the top half of p and p_1 is the lower half of p with a ⋅ p_2 subtracted.
x^2 = x ⋅ x
x^4 = x^2 ⋅ x^2
p(x) = p_0(x) + (x^4 + a_0) ⋅ p_1(x) with p_0 = c_0 + c_1 ⋅ x + c_2 ⋅ x^2 + c_3 ⋅ x^3
p_0(x) = p_2(x) + (x^2 + a_0) ⋅ p_3(x)
Random
Schwartz–Zippel lemma
https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma
Vieta's formula
https://en.wikipedia.org/wiki/Vieta%27s_formulas
Frobenius Endomorphism
https://en.wikipedia.org/wiki/Frobenius_endomorphism
Abert method
https://en.wikipedia.org/wiki/Durand%E2%80%93Kerner_method
https://en.wikipedia.org/wiki/Aberth_method
Reference
https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity
- V.Ya. Pan (1966). "Methods of Computing Values of Polynomials" doi
- S. Winograd (1970). "On the number of multiplications necessary to compute certain functions" doi
- M.O. Rabin & S. Winograd (1972). "Fast Evaluation of Polynomials by Rational Preparation" doi
- D. Knuth (2011). "The Art of Computer Programming – Volume 2: Seminumerical Algorithms" isbn
http://eprints.maths.manchester.ac.uk/2700/3/fasi19.pdf
https://epubs.siam.org/doi/10.1137/0202007
https://onlinelibrary.wiley.com/doi/10.1002/cpa.3160250405
https://ethresear.ch/t/simple-guide-to-fast-linear-combinations-aka-multiexponentiations/7238
