- Cuchulainn
**Posts:**61075**Joined:****Location:**Amsterdam-
**Contact:**

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.

http://www.datasimfinancial.com

http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself

Jean Piaget

http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself

Jean Piaget

- SierpinskyJanitor
**Posts:**1069**Joined:**

this way?

Last edited by SierpinskyJanitor on September 15th, 2011, 10:00 pm, edited 1 time in total.

- Cuchulainn
**Posts:**61075**Joined:****Location:**Amsterdam-
**Contact:**

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?

Last edited by Cuchulainn on September 15th, 2011, 10:00 pm, edited 1 time in total.

http://www.datasimfinancial.com

http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself

Jean Piaget

http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself

Jean Piaget

- Cuchulainn
**Posts:**61075**Joined:****Location:**Amsterdam-
**Contact:**

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

Last edited by Cuchulainn on September 17th, 2011, 10:00 pm, edited 1 time in total.

http://www.datasimfinancial.com

http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself

Jean Piaget

http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself

Jean Piaget

(1+5/n)^n, take n enough to achieve the desired decimal accuracy

- katastrofa
**Posts:**8726**Joined:****Location:**Alpha Centauri

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

Last edited by katastrofa on September 25th, 2011, 10:00 pm, edited 1 time in total.

- Cuchulainn
**Posts:**61075**Joined:****Location:**Amsterdam-
**Contact:**

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)

http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself

Jean Piaget

- katastrofa
**Posts:**8726**Joined:****Location:**Alpha Centauri

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

Last edited by katastrofa on September 26th, 2011, 10:00 pm, edited 1 time in total.

- Cuchulainn
**Posts:**61075**Joined:****Location:**Amsterdam-
**Contact:**

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

http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself

Jean Piaget

- Cuchulainn
**Posts:**61075**Joined:****Location:**Amsterdam-
**Contact:**

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.

Last edited by Cuchulainn on September 26th, 2011, 10:00 pm, edited 1 time in total.

http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself

Jean Piaget

- DevonFangs
**Posts:**3004**Joined:**

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.

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).

Last edited by Polter on September 27th, 2011, 10:00 pm, edited 1 time in total.

GZIP: On