Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Fast exponent and logarithm, given initial estimate
Replies:
29
Last Post:
Nov 8, 2004 2:31 AM




Re: Fast exponent and logarithm, given initial estimate
Posted:
Oct 21, 2004 3:31 AM


In article <9215d7ac.0410201951.2d5f07f6@posting.google.com>, glenlow@pixelglow.com says... > [...] > On second thought, it would probably be slower on an Altivec (or other > modern pipelined) machine. Here's why: > > A 6degree polynomial using the standard Horner's rule takes exactly 5 > fused multiplyadds to run. On a G5, that would take 5 x 8 cyles = 40 > cyles, since each fma depends on the last.
Yes. Horner's method is, somewhat contrary to popular opinion, not the best way of evaluating polynomials (on a computer). Horner's method creates an expression tree that is deep, rather than wide, so you fall victim to instruction latencies in evaluating the expression.
On modern architectures you want a wide expression tree so that subtrees can be evaluated in parallel (without stalling due to latency dependencies).
A method that improves on Horner's method in this aspect is Estrin's method. It rewrites the polynomial as a (mostly balanced) binary tree using x^2 and A*x+B terms (where A and B are different subexpressions).
Christer Ericson Sony Computer Entertainment, Santa Monica



