12
$\begingroup$

I was curious about the difference in speed between Total and Sum. I found out Total was faster. However on another occasion I used a longer list and then the result was reversed. Upon closer inspection, I saw that Sum behaved strangely, see the repetitive code below:

Sum[x, {x, 1, 10^4}] // AbsoluteTiming
Sum[x, {x, 1, 10^5}] // AbsoluteTiming
Sum[x, {x, 1, 10^6}] // AbsoluteTiming
Sum[x, {x, 1, 10^7}] // AbsoluteTiming
Sum[x, {x, 1, 10^8}] // AbsoluteTiming
Sum[x, {x, 1, 10^9}] // AbsoluteTiming

{0.000377, 50005000}

{0.002676, 5000050000}

{0.162434, 500000500000}

{0.000157, 50000005000000}

{0.000112, 5000000050000000}

{0.000110, 500000000500000000}

I can not make any sense of the results above.

Compare those with the more expected results from Total

Total[Range[10^4]] // AbsoluteTiming
Total[Range[10^5]] // AbsoluteTiming
Total[Range[10^6]] // AbsoluteTiming
Total[Range[10^7]] // AbsoluteTiming
Total[Range[10^8]] // AbsoluteTiming
Total[Range[10^9]] // AbsoluteTiming

{0.000115, 50005000}

{0.000931, 5000050000}

{0.010395, 500000500000}

{0.101801, 50000005000000}

{1.166246, 5000000050000000}

{12.470277, 500000000500000000}

Can anyone explain what causes this strange behavior ?

$\endgroup$
  • $\begingroup$ Total will most surely sum blindly, while Sum[] could use known properties (at least it will try when n is large enough) $\endgroup$ – Dr. belisarius Nov 4 '14 at 19:45
  • $\begingroup$ For simple problems do the sum symbolically. sum[n_Integer?Positive] = Sum[x, {x, 1, n}] $\endgroup$ – Bob Hanlon Nov 4 '14 at 19:58
  • $\begingroup$ @belisarius - so you mean, Sum's algorithm changes when the list reaches a certain length? $\endgroup$ – MathLind Nov 4 '14 at 20:06
  • $\begingroup$ @MathLind Well, I can't be sure, but it won't surprise me if it does $\endgroup$ – Dr. belisarius Nov 4 '14 at 20:08
  • 1
    $\begingroup$ "If a sum cannot be carried out explicitly by adding up a finite number of terms, Sum will attempt to find a symbolic result. In this case, f is first evaluated symbolically." Presumably, "cannot be carried out explicitly" translates approximately to more than 10^6 terms. $\endgroup$ – Bob Hanlon Nov 4 '14 at 20:15
12
$\begingroup$

Sum uses more than one Method. By default it selects automatically. If you specify one of them you should see more consistent behavior:

SetOptions[Sum, Method -> "Procedural"];

Table[
  Sum[x, {x, 1, 10^n}] // AbsoluteTiming,
  {n, 4, 9}
] // MatrixForm

$\left( \begin{array}{cc} 0.001000 & 50005000 \\ 0.003000 & 5000050000 \\ 0.011001 & 500000500000 \\ 0.104006 & 50000005000000 \\ 0.768044 & 5000000050000000 \\ 10.313590 & 500000000500000000 \\ \end{array} \right)$

Symbolic summation:

SetOptions[Sum, Method -> "RationalFunction"];

Table[
  Sum[x, {x, 1, 10^n}] // AbsoluteTiming,
  {n, 4, 9}
] // MatrixForm

$\left( \begin{array}{cc} 0.002000 & 50005000 \\ 0.002000 & 5000050000 \\ 0.001000 & 500000500000 \\ 0.002000 & 50000005000000 \\ 0.002000 & 5000000050000000 \\ 0.001000 & 500000000500000000 \\ \end{array} \right)$

$\endgroup$
  • $\begingroup$ Thank you for a clear answer. I still find it peculiar that Sum is optimized in such a way as to give rise to a 1000-fold speed jump at a certain list length. What I mean by that is, what it apparently needs roughly 10^7 of list length to realize, it should have detected earlier in shorter lists. $\endgroup$ – MathLind Nov 5 '14 at 20:46
  • 2
    $\begingroup$ @MathLind Thanks for the Accept. I think it is a matter of Mathematica not knowing in advance which method will be fastest. Even the "slow" attempt takes under a fifth of a second. You can let Mathematica try multiple methods in parallel by using Method -> "ParallelFirstToSucceed" but I think you will find that the overhead of that is often slower than the default behavior. Perhaps this could be better optimized but there are other aspects of Mathematica that I consider in far greater need of optimization; specifically the pattern matching. $\endgroup$ – Mr.Wizard Nov 5 '14 at 23:41
  • $\begingroup$ @ Mr.Wizard For me this was an awakening in the context of optimizing code (programs) containing many built-in functions that behave in this way. Without profiling tools, this may possibly require laborious and careful parameter study of all the built-in functions within the expected ranges. A challenge but still very interesting. $\endgroup$ – MathLind Nov 6 '14 at 8:22
  • $\begingroup$ @MathLind Indeed Mathematica can be fiddly that way. There is a profiling tool built in, detailed here: (7768). It has a few quirks but it seems to work acceptably accurately. $\endgroup$ – Mr.Wizard Nov 6 '14 at 8:27
8
$\begingroup$

The pattern becomes more obvious when plotted:

ListLogPlot[
 Table[First@AbsoluteTiming@Sum[x, {x, 1, Round[10^k]}], {k, 1, 10, 
   0.1}], PlotRange -> All, Joined -> True]

enter image description here

This appears to be consistent with Bob Hanlon's observation that Sum attempts to explicitly sum when the number of terms is considered tractable (the time expense of which is linear), and then search for general solutions after that and use bound substitution (which is fast, and proceeds in constant time). Mr. Wizard's answer provides more details.

$\endgroup$
1
$\begingroup$

This seems like an area where Mathematica can be improved. Mathematica knows the general sum with increment of 1. Applying it is very fast.

In[1]  sn = Sum[x, {x, a, b}]
Out[1] -(1/2) (a-b-1) (a+b)
In[2 ] sn /. {a -> 1, b -> 10^35} // AbsoluteTiming
Out[2] {0.,5000000000000000000000000000000000050000000000000000000000000000000000}

We could define a function for this

FastSum[x_, {x_, a_, b_}] := 1/2 (b - a + 1) (a + b);
$\endgroup$
  • 1
    $\begingroup$ I think you ought to include the time it took to figure out the general sum (the first step). $\endgroup$ – Michael E2 Nov 5 '14 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.