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 Pauls, like the editions of Balbec and Palmyra.”
—Horace Walpole (17171797)
“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 (18031882)
“An intentional object is given by a word or a phrase which gives a description under which.”
—Gertrude Elizabeth Margaret Anscombe (b. 1919)