Re: How to explain these variations in execution speeds?

*To*: mathgroup at smc.vnet.net*Subject*: [mg113174] Re: How to explain these variations in execution speeds?*From*: Vincent <sheeplane at gmail.com>*Date*: Sat, 16 Oct 2010 13:12:52 -0400 (EDT)*References*: <i95tjn$65j$1@smc.vnet.net>

On 14 Okt., 05:32, James Stein <mathgr... at stein.org> wrote: > Stop your kernel; paste the following 14 lines in a notebook cell; then > evaluate the cell. > > (*1*)n=10^6; > (*2*)Timing[Sum[k,{k,n}]] > (*3*)Timing[Sum[k,{k,Evaluate[n]}]] > (*4*)Timing[Sum[k,{k,n+1}]] > (*5*)Timing[Sum[k,{k,n-1}]] > (*6*)Timing[Sum[k,{k,n+2}]] > (*7*)Timing[Sum[k,{k,n-2}]] > (*8*)Timing[Sum[k,{k,n+3}]] > (*9*)Timing[Sum[k,{k,n-3}]] > (*10*)Timing[Sum[k,{k,m}]/.m->n-4] > (*11*)Timing[Sum[k,{k,m}]/.m->Evaluate[n-5]] > (*12*)Timing[Sum[k,{k,m}]/.m->10^6+6] > (*13*)Timing[Sum[k,{k,m}]/.m->10^6-6] > > Each sum represents approximately the same amount of "work", > but some sums are computed significantly faster than others. > What results of previous computations are being used? when? where are the= y > stored? how are they accessed? > Why does the use of 'Rule' (in lines 10-13) speed things up? > Do these examples suggest good ways to speed code in general? > Or are they merely exceptional because 'Sum' is a built-in function? > (If documentation answers these questions, just point me there. I searche= d > w/o success.) > > On my computer, the execution times are approximately: > 0.3500 second: Out lines 2,3,5,7,9 > 0.1000 second: Out lines 4,10 > 0.0044 second: Out lines 6,8 > 0.0003 second: Out lines 11,12,13 > > Some of the puzzle is either explained or compounded (but I'm not sure > which!) by comparing lines 1 and 2 with lines 10 and 11. Why does 'Evalua= te' > speed 11 wrt 10, but not 2 wrt 1? > > My head began to whirl when I compared these two pairs of lines: > > Pair 1: (as above, lines 10 and 11) > Timing[Sum[k, {k, m}] /. m -> n - 4] > Timing[Sum[k, {k, m}] /. m -> Evaluate[n - 4]] > > Pair 2: (same as Pair 1, except "dummy" variable 'm' replaced by 'z' in > second line only) > Timing[Sum[k, {k, m}] /. m -> n - 4] > Timing[Sum[k, {k, z}] /. z -> Evaluate[n - 4]] > > In each pair (assuming a fresh Kernel for each pair), the second line is > much faster than the first; but in the first pair, the speed increase is > much greater that the speed increase in the second pair. It seems like= the > symbol chosen for the "dummy variable" is somewhere retained, and affects > further evaluations. (If so, how?) > > Two ancillary questions: > 1. Is there a programmatic way (from a notebook) to stop then restart the > Kernel? > 2. Is there a set of commands that effectively return the Kernel to its > initial state? > (i.e., clear all user-defined symbols and history and reclaim memory) The important difference here I belive is that you can show analytically that Sum[k, {k, g}]=1/2 g (1 + g) And sometimes mathematica makes this substitution, leading to effectively 0 computation time, and other times it doesn't. My test of the expressions show that the computation time is effectively zero for all expression on the form where g =>n+ 1 or n+2 ect. and that it takes about 0.2 sec when it's on the form g=>n-1 n-2 This could have something to do with the requirement for the above to be true that g>k, and some slight error in the way Mathematica resons when doing the computation. If you call Trace[Sum[k, {k, n + 1}]] Trace[Sum[k, {k, n - 1}]] You see that the first one returns very quickly, while the second one generate alot of intermediate calculations, non using the algebraic solution at all. Why It does this I cannot say.