Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

An efficient algorith to evaluate exp(A)

  1. Nov 1, 2006 #1
    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:
  2. jcsd
  3. Nov 1, 2006 #2


    User Avatar
    Science Advisor

    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.
  4. Nov 1, 2006 #3


    User Avatar
    Science Advisor
    Homework Helper

    has approximately

    Hence, the best you can do is going to be O(A).
  5. Nov 1, 2006 #4


    User Avatar
    Science Advisor
    Homework Helper

    The RSA thing only works for modular arithmetic.
  6. Nov 1, 2006 #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
  7. Nov 1, 2006 #6


    User Avatar
    Science Advisor

    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.
  8. Nov 1, 2006 #7


    User Avatar
    Science Advisor
    Homework Helper

    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.
  9. Nov 1, 2006 #8


    User Avatar
    Science Advisor

    Yes, that's it. It's called "square and multiply" exponentiation.
  10. Nov 1, 2006 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The goal, of course, is to get that "few minutes" down to "few milliseconds". :smile:

    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: Nov 1, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: An efficient algorith to evaluate exp(A)
  1. Complex Exp. (Replies: 5)

  2. Exp in calculator (Replies: 3)

  3. Graph of exp^(a+ib) (Replies: 7)

  4. Ln and exp (Replies: 20)

  5. Exp of a matrix (Replies: 2)