The speed of Sum[] varies strangely

Question

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 ?

Answer 1

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

Answer 2

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]

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.

Answer 3

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