Page 5 of 37

exp(5) = [$]e^5[$]

Posted: September 15th, 2011, 5:24 am
by Cuchulainn
QuoteOriginally posted by: CuchulainnYou can use the fact that exp(x+y) = exp(x)exp(y) (school A level?) and induction to show exp(5) = exp(1)^5 = exp(2)^2*exp(1) == exp(2)*exp(2)*exp(1)Looks like a special case of algos from Pingala's Chandah-sutra.

exp(5) = [$]e^5[$]

Posted: September 16th, 2011, 12:35 pm
by SierpinskyJanitor
this way?

exp(5) = [$]e^5[$]

Posted: September 16th, 2011, 4:01 pm
by Cuchulainn
QuoteOriginally posted by: outrunQuoteOriginally posted by: CuchulainnQuoteOriginally posted by: CuchulainnYou can use the fact that exp(x+y) = exp(x)exp(y) (school A level?) and induction to show exp(5) = exp(1)^5 = exp(2)^2*exp(1) == exp(2)*exp(2)*exp(1)Looks like a special case of algos from Pingala's Chandah-sutra.thats binary expansion used in exponentiation by squaringYes Sir, that's it. A similar and common variation is to compute exp(f(x))) where f(x) is an integral f(x) = Integral([0,x], g) where g is a function. Typically, the x vars are monotonic increasing mesh points. But instead of 'exponent' decomposition we get some interval decomposition?

exp(5) = [$]e^5[$]

Posted: September 18th, 2011, 7:44 am
by Cuchulainn
A good example is when you remove lower-order terms in an ODE. Then "wlog"a(x)dv/dx + b(x)v = f(x)can be reduced to the formA(x)d(B(x)v)/dx = F(x)by a suitable integrating factor which in general is the exponential of some integral. Sometimes you can evaluate it exactly, e.g. when a(X) = x^2, b(x) = x. But in general, we get exponential of a sum of discretre function values, many of which can be reused. I could use STL algo partial_sum().For 2nd order ODE it is nice when we can use the same technique and remove the convection term.au_xx + bu_x = f==>av_x + bv = fu_x = v

exp(5) = [$]e^5[$]

Posted: September 23rd, 2011, 9:43 am
by supernova
(1+5/n)^n, take n enough to achieve the desired decimal accuracy

exp(5) = [$]e^5[$]

Posted: September 26th, 2011, 2:21 pm
by katastrofa
I would multiply (e*e)^2*e in columns like in primary school - it goes very fast (but my husband told me not to admit to people how many digits of Euler's number I know by heart ;-/)2.71828 will do :-)BTW, there's a similar problem with convergence of the exp function in physics, when one wants to calculate the exponent of a matrix (e.g. the evolution operator). What's usually done is first calculating B = exp(A/n) and then B^n... or using a Padé approximant.a

exp(5) = [$]e^5[$]

Posted: September 26th, 2011, 7:39 pm
by Cuchulainn
QuoteOriginally posted by: katastrofaI would multiply (e*e)^2*e in columns like in primary school - it goes very fast (but my husband told me not to admit to people how many digits of Euler's number I know by heart ;-/)2.71828 will do :-)BTW, there's a similar problem with convergence of the exp function in physics, when one wants to calculate the exponent of a matrix (e.g. the evolution operator). What's usually done is first calculating B = exp(A/n) and then B^n... or using a Padé approximant.a19 dubious ways to calculate exp(A)

exp(5) = [$]e^5[$]

Posted: September 26th, 2011, 10:28 pm
by katastrofa
QuoteOriginally posted by: Cuchulainn19 dubious ways to calculate exp(A)Yup, p.10, Method 3. Scaling and squaring: exp(A/m) -> Taylor expansion/Padé approximant -> (.)^m usually works best - at least for me (or A is normal and can be diagonalised). Sorry, I hijacked the thread :-)a

exp(5) = [$]e^5[$]

Posted: September 27th, 2011, 4:33 am
by Cuchulainn
QuoteOriginally posted by: katastrofaQuoteOriginally posted by: Cuchulainn19 dubious ways to calculate exp(A)Yup, p.10, Method 3. Scaling and squaring: exp(A/m) -> Taylor expansion/Padé approximant -> (.)^m usually works best - at least for me (or A is normal and can be diagonalised). Sorry, I hijacked the thread :-)aGreat! Thanks for the input

exp(5) = [$]e^5[$]

Posted: September 27th, 2011, 4:37 am
by Cuchulainn
QuoteOriginally posted by: supernova(1+5/n)^n, take n enough to achieve the desired decimal accuracyIs there a fast way to compute (1+1/n)^nto a given accuracy? (using a Cauchy sequence?). Then we can use the Pingala's Chandah-sutra technique already alluded to.The interview allows 5 minutes.

exp(5) = [$]e^5[$]

Posted: September 27th, 2011, 9:11 pm
by DevonFangs
QuoteOriginally posted by: katastrofaBTW, there's a similar problem with convergence of the exp function in physics, when one wants to calculate the exponent of a matrix (e.g. the evolution operator). What's usually done is first calculating B = exp(A/n) and then B^n... or using a Padé approximant.aNot that it's really relevant, but this reminds me of the Lie Trotter formula. One can construct a naturally time ordered evolution operator and integrate Schroedinger eqn efficiently from there in a fancy way.

exp(5) = [$]e^5[$]

Posted: September 27th, 2011, 10:59 pm
by Polter
QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: supernova(1+5/n)^n, take n enough to achieve the desired decimal accuracyIs there a fast way to compute (1+1/n)^nto a given accuracy? (using a Cauchy sequence?). Then we can use the Pingala's Chandah-sutra technique already alluded to.The interview allows 5 minutes.Rough idea:Denote our ErrorOfApproximation function by f(x; n) := Power series expansion of the above, accurate to order x^3 (that's not very high, but it's probably a good idea to sacrifice some accuracy and settle for lower order in an interview setting ;]), gives:So, for our x=1 the error-of-approximation behaves roughly like:From this one can see that to reduce the order of approximation error by magnitude "m" we have to increase "n" roughly by the same "m" (a nice inverse relationship).Some numerical illustration of the above:f(1; 10) = 0.124539f(1; 100) = 0.013468f(1; 1000) = 0.0013579(and we have to stop right here).