Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

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

 Messages: [ Previous | Next ]
 Christer Ericson Posts: 34 Registered: 12/6/04
Re: Fast exponent and logarithm, given initial estimate
Posted: Oct 21, 2004 3:31 AM

glenlow@pixelglow.com says...
&gt; [...]
&gt; On second thought, it would probably be slower on an Altivec (or other
&gt; modern pipelined) machine. Here's why:
&gt;
&gt; A 6-degree polynomial using the standard Horner's rule takes exactly 5
&gt; fused multiply-adds to run. On a G5, that would take 5 x 8 cyles = 40
&gt; 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

Date Subject Author
10/18/04 Glen Low
10/18/04 Jeremy Watts
10/19/04 Peter Spellucci
10/19/04 Glen Low
10/18/04 bv
10/19/04 Glen Low
10/19/04 George Russell
10/19/04 Glen Low
10/20/04 George Russell
10/20/04 Glen Low
10/21/04 Christer Ericson
10/21/04 Glen Low
10/22/04 Christer Ericson
10/19/04 Martin Brown
10/19/04 Glen Low
10/19/04 Richard Mathar
10/19/04 Glen Low
10/20/04 Gert Van den Eynde
10/20/04 Glen Low
10/20/04 Richard Mathar
10/21/04 Gert Van den Eynde
10/21/04 bv
10/22/04 Glen Low
10/22/04 Peter Spellucci
10/22/04 Glen Low
10/23/04 bv
10/24/04 Gert Van den Eynde
10/25/04 Peter Spellucci
10/20/04 Gert Van den Eynde
11/8/04 Glen Low