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 4:43 AM

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