Estrin's Scheme - Description of The Algorithm

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.

Read more about this topic:  Estrin's Scheme

Famous quotes containing the words description of the, description of and/or description:

    “The next Augustan age will dawn on the other side of the Atlantic. There will, perhaps, be a Thucydides at Boston, a Xenophon at New York, and, in time, a Virgil at Mexico, and a Newton at Peru. At last, some curious traveller from Lima will visit England and give a description of the ruins of St Paul’s, like the editions of Balbec and Palmyra.”
    —Horace Walpole (1717–1797)

    “Do not require a description of the countries towards which you sail. The description does not describe them to you, and to- morrow you arrive there, and know them by inhabiting them.”
    —Ralph Waldo Emerson (1803–1882)

    “An intentional object is given by a word or a phrase which gives a description under which.”
    —Gertrude Elizabeth Margaret Anscombe (b. 1919)