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 4:43 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


> > Newton-Raphson seems of no use since I can't use the inverse function.
>
> It may be of more use than you think. For y = ln(x), the recursion
>
> y = y - (1 - x*exp(-y))
>
> will work quickly since you can (probably) work with normalized numbers
> for which the series approx for exp(-y) won't need many terms to get the
> precision you want. With decent estimates this will take only a few
> iterations.

That is the approach I'm leaning toward. Broadly:

1. Get a good exponentiation algorithm going. Probably split integer
and fraction parts, then apply a squared Taylor expansion on the
fractional part. For 24 bits of accuracy, probably end up with about 7
multiplies. (I read some stuff about binary splitting, binary
reduction and other esoteric algorithms, but I fail to see how they
would reduce the number of multiplies -- anyone care to explain?)

2. Given the log estimate, apply either Newton Raphson or a Halley
iteration using the exponentiation above:

y = y - 2 * (exp(y)-x)/(exp(y)+x)

The Halley iteration is supposed to be cubically convergent i.e. 3x
the number of bits of accuracy of the original, which according to
Altivec was 5 bits. (Using NR would get 10 bits, then 20, then 40 i.e.
3 iteration; using H would get 15 bits, then 45 bits i.e. 2
iterations.) I'd estimate something like 18 multiplies.

If 2. is too slow, might have to consider some other plan...

This seems like a pretty good reference:

<a href="http://yacas.sourceforge.net/Algochapter5.html">http://yacas.sourceforge.net/Algochapter5.html</a>

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.