Horner's method for evaluation of polynomials is one of the most commonly used algorithms for this purpose, and unlike Estrin's scheme it is optimal in the sense that it minimizes the number of multiplications and additions required to evaluate an arbitrary polynomial. On a modern processor, instructions that do not depend on each other's results may run in parallel. Horner's method contains a series of multiplications and additions that each depend on the previous instruction and so cannot execute in parallel. Estrin's scheme is one method that attempts to overcome this serialization while still being reasonably close to optimal.
Estrin's scheme operates recursively, converting a degree-n polynomial in x (for n≥2) to a degree-⌊n/2⌋ polynomial in x2 using ⌈n/2⌉ independent operations (plus one to compute x2).
Given an arbitrary polynomial P(x) = C0 + C1x + C2x2 + C3x3 + ⋯ + Cnxn, one can group adjacent terms into sub-expressions of the form (A + Bx) and rewrite it as a polynomial in x2: P(x) = (C0 + C1x) + (C2 + C3x)x2 + (C4 + C5x)x4 + ⋯ = Q(x2).
Each of these sub-expressions, and x2, may be computed in parallel. They may also be evaluated using a native multiply–accumulate instruction on some architectures, an advantage that is shared with Horner's method.
This grouping can then be repeated to get a polynomial in x4: P(x) = Q(x2) = ((C0 + C1x) + (C2 + C3x)x2) + ((C4 + C5x) + (C6 + C7x)x2)x4 + ⋯ = R(x4).
Repeating this ⌊log2n⌋+1 times, one arrives at Estrin's scheme for parallel evaluation of a polynomial:
Compute Di = C2i + C2i+1x for all 0 ≤ i ≤ ⌊n/2⌋. (If n is even, then Cn+1 = 0 and Dn/2 = Cn.)
If n ≤ 1, the computation is complete and D0 is the final answer.
Otherwise, compute y = x2 (in parallel with the computation of Di).
This performs a total of n multiply-accumulate operations (the same as Horner's method) in line 1, and an additional ⌊log2n⌋ squarings in line 3. In exchange for those extra squarings, all of the operations in each level of the scheme are independent and may be computed in parallel; the longest dependency path is ⌊log2n⌋+1 operations long.
Examplesedit
Take Pn(x) to mean the nth order polynomial of the form: Pn(x) = C0 + C1x + C2x2 + C3x3 + ⋯ + Cnxn
Estrin, Gerald (May 1960). "Organization of computer systems—The fixed plus variable structure computer" (PDF). Proc. Western Joint Comput. Conf. San Francisco: 33–40. doi:10.1145/1460361.1460365. S2CID 16384320.
Muller, Jean-Michel (2005). Elementary Functions: Algorithms and Implementation (2nd ed.). Birkhäuser. p. 58. ISBN0-8176-4372-9.
Further readingedit
fast_polynomial, a Sage library using an improved scheme (extended abstract).
April 11, 2024
estrin, scheme, numerical, analysis, after, gerald, estrin, also, known, estrin, method, algorithm, numerical, evaluation, polynomials, horner, method, evaluation, polynomials, most, commonly, used, algorithms, this, purpose, unlike, optimal, sense, that, mini. In numerical analysis Estrin s scheme after Gerald Estrin also known as Estrin s method is an algorithm for numerical evaluation of polynomials Horner s method for evaluation of polynomials is one of the most commonly used algorithms for this purpose and unlike Estrin s scheme it is optimal in the sense that it minimizes the number of multiplications and additions required to evaluate an arbitrary polynomial On a modern processor instructions that do not depend on each other s results may run in parallel Horner s method contains a series of multiplications and additions that each depend on the previous instruction and so cannot execute in parallel Estrin s scheme is one method that attempts to overcome this serialization while still being reasonably close to optimal Contents 1 Description of the algorithm 2 Examples 3 References 4 Further readingDescription of the algorithm editEstrin s scheme operates recursively converting a degree n polynomial in x for n 2 to a degree n 2 polynomial in x2 using n 2 independent operations plus one to compute x2 Given an arbitrary polynomial P x C0 C1x C2x2 C3x3 Cnxn one can group adjacent terms into sub expressions of the form A Bx and rewrite it as a polynomial in x2 P x C0 C1x C2 C3x x2 C4 C5x x4 Q x2 Each of these sub expressions and x2 may be computed in parallel They may also be evaluated using a native multiply accumulate instruction on some architectures an advantage that is shared with Horner s method This grouping can then be repeated to get a polynomial in x4 P x Q x2 C0 C1x C2 C3x x2 C4 C5x C6 C7x x2 x4 R x4 Repeating this log2n 1 times one arrives at Estrin s scheme for parallel evaluation of a polynomial Compute Di C2i C2i 1x for all 0 i n 2 If n is even then Cn 1 0 and Dn 2 Cn If n 1 the computation is complete and D0 is the final answer Otherwise compute y x2 in parallel with the computation of Di Evaluate Q y D0 D1y D2y2 D n 2 y n 2 using Estrin s scheme This performs a total of n multiply accumulate operations the same as Horner s method in line 1 and an additional log2n squarings in line 3 In exchange for those extra squarings all of the operations in each level of the scheme are independent and may be computed in parallel the longest dependency path is log2n 1 operations long Examples editTake Pn x to mean the nth order polynomial of the form Pn x C0 C1x C2x2 C3x3 CnxnWritten with Estrin s scheme we have P3 x C0 C1x C2 C3x x2 P4 x C0 C1x C2 C3x x2 C4x4 P5 x C0 C1x C2 C3x x2 C4 C5x x4 P6 x C0 C1x C2 C3x x2 C4 C5x C6x2 x4 P7 x C0 C1x C2 C3x x2 C4 C5x C6 C7x x2 x4 P8 x C0 C1x C2 C3x x2 C4 C5x C6 C7x x2 x4 C8x8 P9 x C0 C1x C2 C3x x2 C4 C5x C6 C7x x2 x4 C8 C9x x8 In full detail consider the evaluation of P15 x Inputs x C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 C15 Step 1 x2 C0 C1x C2 C3x C4 C5x C6 C7x C8 C9x C10 C11x C12 C13x C14 C15x Step 2 x4 C0 C1x C2 C3x x2 C4 C5x C6 C7x x2 C8 C9x C10 C11x x2 C12 C13x C14 C15x x2 Step 3 x8 C0 C1x C2 C3x x2 C4 C5x C6 C7x x2 x4 C8 C9x C10 C11x x2 C12 C13x C14 C15x x2 x4 Step 4 C0 C1x C2 C3x x2 C4 C5x C6 C7x x2 x4 C8 C9x C10 C11x x2 C12 C13x C14 C15x x2 x4 x8References editEstrin Gerald May 1960 Organization of computer systems The fixed plus variable structure computer PDF Proc Western Joint Comput Conf San Francisco 33 40 doi 10 1145 1460361 1460365 S2CID 16384320 Muller Jean Michel 2005 Elementary Functions Algorithms and Implementation 2nd ed Birkhauser p 58 ISBN 0 8176 4372 9 Further reading editfast polynomial a Sage library using an improved scheme extended abstract Retrieved from https en wikipedia org w index php title Estrin 27s scheme amp oldid 1169109732, wikipedia, wiki, book, books, library,
