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 Sage of Toronto ... spent several decades marveling at the numerous freedoms created by a “global village” instantly and effortlessly accessible to all. Villages, unlike towns, have always been ruled by conformism, isolation, petty surveillance, boredom and repetitive malicious gossip about the same families. Which is a precise enough description of the global spectacle’s present vulgarity.”
—Guy Debord (b. 1931)
“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)
“As they are not seen on their way down the streams, it is thought by fishermen that they never return, but waste away and die, clinging to rocks and stumps of trees for an indefinite period; a tragic feature in the scenery of the river bottoms worthy to be remembered with Shakespeare’s description of the sea-floor.”
—Henry David Thoreau (1817–1862)