Estrin's scheme

Estrin's scheme

In numerical analysis Estrin's scheme (also known as Estrin's method) is an algorithm for numerical evaluation of polynomials.

The Horner scheme 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 addition required to evaluate an arbitrary polynomial. On a modern processor architecture that allows Out-of-order execution, instructions that do not depend on each other's results may run in parallel. The Horner scheme contains a series of multiplications and additions that 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.

Description of the algorithm

Given an arbitrary polynomial Pn(x)= C0 +C1x +C2x2 +C3x3 ... +Cnxn one can isolate sub-expressions of the form (A+Bx) and of the form x2n.

Rewritten using Estrin's scheme we get Pn(x)= (C0 +C1x) + (C2 +C3x) x2 + ((C4 +C5x) + (C6 +C7x) x2))x4...

x2n can be evaluated once and kept until no longer required. As is evident from looking at this expression there are many sub-expression that may be evaluated in parallel.

The sub-expressions of form (A+Bx) can be evaluated using a native multiply-accumulate instruction on some architectures, an advantage that is shared with the Horner scheme.

Examples

Take Pn(x) to mean the nth order polynomial of the form: Pn(x)= C0 +C1x +C2x2 +C3x3 ... +Cnxn

Written 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

...

References

* Jean-Michel Muller, "Elementary Functions: Algorithms And Implementation", 2nd edition, Springer Verlag, page 58.
* Robin Green, Faster Math Functions( [http://www.research.scea.com/gdc2003/fast-math-functions_p2.pdf] )


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Horner scheme — In numerical analysis, the Horner scheme or Horner algorithm, named after William George Horner, is an algorithm for the efficient evaluation of polynomials in monomial form. Horner s method describes a manual process by which one may approximate …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • Reconfigurable computing — is a computer architecture combining some of the flexibility of software with the high performance of hardware by processing with very flexible high speed computing fabrics like field programmable gate arrays (FPGAs). The principal difference… …   Wikipedia

  • Charmed (season 3) — Charmed Season 3 DVD cover art No. of episodes 22 Broadcast …   Wikipedia

  • 1998 Russian financial crisis — The Russian financial crisis (also called Ruble crisis ) hit Russia on 17 August 1998. It was exacerbated by the Asian financial crisis, which started in July 1997. Given the ensuing decline in world commodity prices, countries heavily dependent… …   Wikipedia

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

  • List of Hercules: The Legendary Journeys episodes — The following is a list of episodes from Hercules: The Legendary Journeys, a television series, filmed in New Zealand and the United States, starring Kevin Sorbo as Hercules. It is very loosely based on the tales of the classical Greek culture… …   Wikipedia

  • IPv6 — Internet protocol suite Application layer BGP DHCP DNS FTP …   Wikipedia

  • List of Boston Public episodes — A list of episodes for Fox drama television series Boston Public. Contents 1 Season 1 (2000–2001) 2 Season 2 (2001–2002) 3 Season 3 (2002–2003) …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”