The Math Forum



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

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 19, 2004 10:38 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


> 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 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
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]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.