Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

Topic: Fast exponent and logarithm, given initial estimate
Replies: 29   Last Post: Nov 8, 2004 2:31 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Glen Low

Posts: 41
Registered: 12/13/04
Re: Fast exponent and logarithm, given initial estimate
Posted: Oct 20, 2004 11:51 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


> For degree 6, you can evaluate a real polynomial in x using 4 multiplications and
> 7 additions with the code
>
> z = (x + a0)*x + a1
> w = (x + a2)*z + a3
> the value of the polynomial = ((w + z + a4)*w + a5) * a6
>
> You need to solve a cubic equation to work out the constants a0-a6 given the initial
> coefficients; however there will always be a real solution.
>
> You mentioned fused multiply-adds. This algorithm requires
> 4 multiplies/fused multiply-adds and just 4 additions. I don't know if you can
> get the number of additions down even further.

On second thought, it would probably be slower on an Altivec (or other
modern pipelined) machine. Here's why:

A 6-degree polynomial using the standard Horner's rule takes exactly 5
fused multiply-adds to run. On a G5, that would take 5 x 8 cyles = 40
cyles, since each fma depends on the last.

A 6-degree polynomial using the Knuth method above uses 4 fused
multiply-adds and 4 additions. Unfortunately each addition also takes
8 cycles, so it comes out to around 8 x 8 cyles = 64 cycles, minus one
or two since the initial x + a0 doesn't depend on x + a2 and can be
pipelined. Unless some of the coefficients are zero or the same, or I
can do more of the operations in parallel... I have to a bit more
analysis on that.

Cheers,
Glen Low, Pixelglow Software
www.pixelglow.com



Date Subject Author
10/18/04
Read Fast exponent and logarithm, given initial estimate
Glen Low
10/18/04
Read Re: Fast exponent and logarithm, given initial estimate
Jeremy Watts
10/19/04
Read Re: Fast exponent and logarithm, given initial estimate
Peter Spellucci
10/19/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low
10/18/04
Read Re: Fast exponent and logarithm, given initial estimate
bv
10/19/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low
10/19/04
Read Re: Fast exponent and logarithm, given initial estimate
George Russell
10/19/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low
10/20/04
Read Re: Fast exponent and logarithm, given initial estimate
George Russell
10/20/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low
10/21/04
Read Re: Fast exponent and logarithm, given initial estimate
Christer Ericson
10/21/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low
10/22/04
Read Re: Fast exponent and logarithm, given initial estimate
Christer Ericson
10/19/04
Read Re: Fast exponent and logarithm, given initial estimate
Martin Brown
10/19/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low
10/19/04
Read Re: Fast exponent and logarithm, given initial estimate
Richard Mathar
10/19/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low
10/20/04
Read Re: Fast exponent and logarithm, given initial estimate
Gert Van den Eynde
10/20/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low
10/20/04
Read Re: Fast exponent and logarithm, given initial estimate
Richard Mathar
10/21/04
Read Re: Fast exponent and logarithm, given initial estimate
Gert Van den Eynde
10/21/04
Read Re: Fast exponent and logarithm, given initial estimate
bv
10/22/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low
10/22/04
Read Re: Fast exponent and logarithm, given initial estimate
Peter Spellucci
10/22/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low
10/23/04
Read Re: Fast exponent and logarithm, given initial estimate
bv
10/24/04
Read Re: Fast exponent and logarithm, given initial estimate
Gert Van den Eynde
10/25/04
Read Re: Fast exponent and logarithm, given initial estimate
Peter Spellucci
10/20/04
Read Re: Fast exponent and logarithm, given initial estimate
Gert Van den Eynde
11/8/04
Read Re: Fast exponent and logarithm, given initial estimate
Glen Low

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.