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 5:32 AM


Glen Low wrote (snipped): > 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?)
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.
These methods require some precomputation to generate the coefficients to be used, but since the coefficients are constant in your case, that should not be a problem.



