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 ]
Gert Van den Eynde

Posts: 77
Registered: 12/8/04
Re: Fast exponent and logarithm, given initial estimate
Posted: Oct 21, 2004 3:01 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


Glen Low wrote:

>> just my 2 cents
>>
>> be X the number you want the exp(X) for
>> the idea is to reduce the interval for X to [0,ln(2)]
>>
>> 1) rewrite exp(X) as 2^p * exp(x)
>> do this by multiplying X by log_2(e)
>> the integer part of this is p. Calculate x by x = X - p ln(2)
>>
>> so the problem is reduced to an approximation for x in [0,ln(2)] and once
>> we have this, multiply by 2^p which can be done quite quickly and without
>> error.
>
> Yes I figured that out already. The Altivec exp estimate can calculate
> the 2^p accurately for me.
>
>> 2) approximate exp(x) in [0,ln(2)] by a minimax-approximation:
>>
>> the next is a 6th degree polynomial minimax-approximation which has a
>> relative error < 10e-8 in the interval [0,ln(2)]. Coefficients are from
>> a_0 to a_6 where a_i belongs to x**i.
>>
>> 1.000000002644271861135635165803
>> 0.999999630676466160313515392503
>> 0.500008415450545865703228178366
>> 0.166594937239279108432157593360
>> 0.041956255273539448094181805064
>> 0.007740059180886275586488149490
>> 0.001973684356346945984956068724
>
> That was brilliant! I plugged in the coefficients into the polynomial,
> and the results were within 5 ulps of the library exp. (I had weird
> rounding errors when I used squaring reduction and Taylor polynomials
> and straightforward Horner-style factoring, so you've saved me tearing
> the last bits of my hair out.) All within 9 multiplies.
>

Some advice: try to eliminate the link in your head between "approximation"
and "taylor expansion" and replace it by "approximation" and "orthogonal
polynomials" :-) Taylor is good in a small neighbourhood around the point
of interest. Orthogonal polynomials are good in quite a large interval to
which you can almost always reduce your initial interval to.

> Now to slice off one more multiply by using the Knuthean polynomial
> transform suggested by a post in a different part of this thread...
>
> Qn: what tool did you use to generate the minimax polynomial?
>
Maple 9.51. The numapprox package, minimax function. The classical algorithm
associated with minimax approximations is the Remez algorithm (2nd version
of 1934, I don't have the exact reference at hand).

Be carefull with these "addition for multiplication" type of cost reduction.
Don't just implement the formula Knuth describes, but also read his error
analysis (actually, try reading the whole book The Art of Computer
Programming Volume 2 Semi-numerical algorithms, good read and very rich on
detailed analysis). I would stick to Horner. The one extra multiply isn't
worth the risk of "unexpected" rounding errors.

have fun,
gert



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.