An efficient algorith to evaluate exp(A)

  • Thread starter Karlisbad
  • Start date
In summary, there are various techniques for efficiently evaluating e^A, such as taking the logarithm for an order-of-magnitude approximation and using the "square and multiply" exponentiation method to reduce the number of multiplications needed in an exact answer. However, due to the irrational nature of e^x and the desired accuracy, the computation time can range from a few minutes to milliseconds. There is also a similar method for computing trigonometric functions, but it may not be more numerically stable.
  • #1
Karlisbad
131
0
let be "A" a big number, my question is, is there an efficient algorith (with only a few steps) to evaluate [tex] e^{A} [/tex] :confused:
 
Mathematics news on Phys.org
  • #2
I'm certainly no expert on this, but you could get an order-of-magnitude approximation by taking the logarithm. Also, you could reduce the number of multiplications used in an exact answer to only log A by using the same technique used in RSA fast exponentiation.
 
  • #3
[tex]e^A[/tex]
has approximately
[tex]\frac{A}{3}[/tex]
digits.

Hence, the best you can do is going to be O(A).
 
  • #4
0rthodontist said:
I'm certainly no expert on this, but you could get an order-of-magnitude approximation by taking the logarithm. Also, you could reduce the number of multiplications used in an exact answer to only log A by using the same technique used in RSA fast exponentiation.

The RSA thing only works for modular arithmetic.
 
  • #5
do you mean using a computer on a program, or using your head?

how big do you want A to be?

just for ref, i quickly wrote a c++ program that can get you values of e^A where A is in the order of a million in less than a min, although i cheated and gave it a starting value of e

but you need to know a few things first if you are writing a program for this

* e^x is an irrational number just like for example pie, so getting it exact is impossible,

* thus you need to limit yourself to some sort of accuracy

* what order of A do you want to calculate to

* if your accuracy is only to a few sig figures , perhaps upto 10sig fig, then you can write a computer program to give you e^x where x is any number, the program if written well will not take very long to run, probably in the order of a few min max

* the accuracy and value of a will be the main factors in the time to compute
 
  • #6
NateTG said:
The RSA thing only works for modular arithmetic.
No, not that technique, the one that splits up the exponent. It would take me some time to remember it but the basic idea is that if you have an exponent like 2n, it computes x^n and then squares it.
 
  • #7
0rthodontist said:
No, not that technique, the one that splits up the exponent. It would take me some time to remember it but the basic idea is that if you have an exponent like 2n, it computes x^n and then squares it.

I think you mean the repeated squaring idea for finding exponents? To find x^n you first find x^1, x^2, x^(2^2), x^(2^3), x^(2^m) where 2^(m+1)>n. this takes some log(n) squaring operations. Then write n in binary and multiply the appropriate numbers from your list to get x^n, another log(n) multiplications in the worst case. For example x^11=(x^1)*(x^2)*(x^(2^3)).

I don't think this has a standard name, and it's not an rsa specific thing of course.
 
  • #8
Yes, that's it. It's called "square and multiply" exponentiation.
 
  • #9
cells said:
* if your accuracy is only to a few sig figures , perhaps upto 10sig fig, then you can write a computer program to give you e^x where x is any number, the program if written well will not take very long to run, probably in the order of a few min max
The goal, of course, is to get that "few minutes" down to "few milliseconds". :smile:


0rthodontist said:
Yes, that's it. It's called "square and multiply" exponentiation.
If your exponent is a C integer, then there's a nice optimization you can do; you can simply precompute

e^1, e^2, e^4, e^8, ..., e^(2^31)

and then you don't have to bother with squaring. :smile:


I think a similar method is good for any floating point exponent. (Though you might want to choose a different class of precomputed values)



On a related note, the same sort of "shift-and-add" algorithm works for trig functions... in particular, sinh x and cosh x. (use the addition and double-angle identities) I wonder if that version is more numerically stable than repeatedly squaring & multiplying e? Probably not, but worth a look.
 
Last edited:

Related to An efficient algorith to evaluate exp(A)

1. What is an efficient algorithm to evaluate exp(A)?

The most efficient algorithm to evaluate exp(A) is the Taylor series expansion method, which involves breaking down the exponential function into a series of polynomial terms.

2. How does the Taylor series expansion method work?

The Taylor series expansion method works by using the fact that the exponential function can be expressed as an infinite sum of power series, which can then be evaluated using the coefficients of the series.

3. What is the time complexity of the Taylor series expansion method?

The time complexity of the Taylor series expansion method is O(n), where n is the number of terms used in the series. This makes it a very efficient algorithm for evaluating exp(A) compared to other methods.

4. Are there any drawbacks to using the Taylor series expansion method?

One drawback of the Taylor series expansion method is that it may not be accurate enough for certain values of A, especially when the number of terms used in the series is limited. In such cases, other methods such as exponential approximation may be more suitable.

5. Can the Taylor series expansion method be used to evaluate exp(A) for complex numbers?

Yes, the Taylor series expansion method can be used to evaluate exp(A) for complex numbers as well. However, the number of terms used in the series may need to be increased to achieve the desired accuracy.

Similar threads

Replies
1
Views
815
Replies
1
Views
996
Replies
6
Views
1K
Replies
0
Views
258
  • General Math
Replies
2
Views
1K
  • Introductory Physics Homework Help
Replies
5
Views
1K
Replies
3
Views
1K
  • General Math
Replies
2
Views
1K
Replies
4
Views
890
Back
Top