An efficient algorith to evaluate exp(A)

[Karlisbad]

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]

 

[0rthodontist]

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.

 

[NateTG]

[tex]e^A[/tex]
has approximately
[tex]\frac{A}{3}[/tex]
digits.

Hence, the best you can do is going to be O(A).

 

[NateTG]

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.

 

[cells]

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

 

[0rthodontist]

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.

 

[shmoe]

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.

 

[0rthodontist]

Yes, that's it. It's called "square and multiply" exponentiation.

 

[Hurkyl]

* 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".

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.


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.