1
$\begingroup$

I originally posted this over on Software Engineering, but it was suggested that I repost it here.

I am working on a BCD Floating point library and I'm a bit stuck on the EXP (antilog) functions. The goal is to maintain accuracy for the entire length of the number which could exceed 100 significant digits.

So the requirements are fast and accurate to N digits.

I have been experimenting with the Taylor series and found that it will yield an answer, but requires about 2 iterations per digit. It takes two multiplies and one divide per iteration. Plus I am not satisfied that it is all that accurate because it seems to converge on the correct answer only to drift away.

I would like to know if this can be done with chebyshev polynomials to converge on the correct answer in fewer iterations and clock cycles. I do have a chebyshev example, but it is limited to 8 iterations and about 9 digits of accuracy. I found no explanation as to how to expand it for more significant digits.

Does anybody have a chebyshev, or better, algorithm that can calculate EXP (any base)? Please no complicated math proofs as they are likely over my head.

Improve this question
$\endgroup$
6
  • $\begingroup$ You would benefit from studying the classical paper on this subject by Brent. $\endgroup$ – Emil Jeřábek Jan 19 at 13:45
  • $\begingroup$ To clarify, the paper does not discuss Chebyshev polynomials. Fast algorithms for this kind of functions are generally based on iterative methods such as Newton iteration (this not only converges much faster than power series approximation, but also has the great advantage that it is self-correcting, thus errors do not accumulate). $\endgroup$ – Emil Jeřábek Jan 19 at 13:52
  • $\begingroup$ Use an existing library. Some of them (such as MPFR) come with source code. $\endgroup$ – Yuval Filmus Jan 19 at 14:36
  • $\begingroup$ I see you asked also on Software Engineering: softwareengineering.stackexchange.com/q/421181/34181. We ask that you avoid asking on two questions simultaneously. I see someone there gave you a link that looks like a reasonable resource on Chebyshev polynomials. We prefer that you list in the question what research you've done, what resources you've already found, and whether it did or didn't meet your needs and why. $\endgroup$ – D.W.♦ Jan 19 at 17:33
  • $\begingroup$ Thanks everyone. I do use Newtons method for computing square roots, but every implementation of exp() that uses newtons method requires it to call the log() function. My log function is not approximated and is exact. However, it requires 4 multiplies per digit. Thus, 100 digits = 400 multiplies. If newton's method completes in 5 rounds, that's 2000 multiplies. Not what you want to hear when running on a 80kHz processor. The Brent algorithms and the ones in MPFR look very promising. $\endgroup$ – user264480 Jan 20 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.