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 19, 2004 10:38 PM


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



