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 ]
 Glen Low Posts: 41 Registered: 12/13/04
Re: Fast exponent and logarithm, given initial estimate
Posted: Oct 19, 2004 10:38 PM

&gt; Once you have take the first few terms of a power series to make a polynomial,
&gt; there are a number of tricks you can use to evaluate that polynomial with
&gt; fewer multiplications, which are outlined in Knuth's Art of Computer Programming,
&gt; section 4.6.4. For example a polynomial over the reals of degree 4 can be
&gt; evaluated with 3 multiplications and 5 additions, of degree 5, with 4 multiplications
&gt; and 5 additions, of degree 6, with 4 multiplications and 7 additions. There is a general
&gt; method for evaluating a real polynomial of degree n&gt;=3 with (floor (n/2) + 2 )

I estimated that using x * 2^-3 in a Taylor polynomial of degree 5
should be sufficient for single precision accuracy, since the 6th term
would have had a coefficient of 1/6! or 1/720, approximately 2^-9, and
thus that term would have a factor of 2^-(3*6)-9 or 2^-27, beyond the
accuracy of a 23 bit float.

I can use the architecture's fused multiply-adds, so reducing the
number of additions isn't a worry for me, only the number of
multiplications. The above would take 4 multiplications using brute
force.

Still, I find it intriguing that you can evaluate a polynomial of
degree 6 with just 4 multiplications (instead of 5)... any sample
code? (It might save me a multiplication if I use x * 2^-2 on a degree
6 polynomial...)

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

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