5
$\begingroup$

I was playing around with Sum and noticed that summing all integers from 1 to a million is order of magnitudes slower than summing other numbers

In[1]:= RepeatedTiming[Sum[nn, {nn, 1, 10^6}]]

Out[1]= {0.52, 500000500000}

In[2]:= RepeatedTiming[Sum[nn, {nn, 1, 10^7}]]

Out[2]= {0.000086, 50000005000000}

I even made a plot of the results where a difference can clearly be seen

In[3]:= f[n_] := RepeatedTiming[Sum[nn, {nn, 1, n}]][[1]]

In[4]:= data = Table[{10^n, f[10^n]}, {n, 0, 15}]

Out[4]= {{1, 1.4*10^-6}, {10, 2.074*10^-6}, {100, 0.000013}, {1000, 
  0.00002}, {10000, 0.00028}, {100000, 0.002}, {1000000, 
  0.560}, {10000000, 0.0003}, {100000000, 0.0002}, {1000000000, 
  0.000077}, {10000000000, 0.000098}, {100000000000, 
  0.00010}, {1000000000000, 0.000080}, {10000000000000, 
  0.0002}, {100000000000000, 0.00029}, {1000000000000000, 0.00028}}

In[5]:= ListLogLinearPlot[data, PlotRange -> All, 
 AxesLabel -> {None, "Time [s]"}]

Plot of timing of summing numbers

Why is summing 10^6 so much slower?

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ Probably just an unfortunate internal choice of algorithms for the default Method->Automatic setting. Try Method -> "Procedural" and you get what you expect. In your case of course Method -> "Polynomial" would be more appropriate. $\endgroup$
    – Rolf Mertig
    Commented Oct 22, 2016 at 10:08
  • $\begingroup$ This issue also occured in this thread. $\endgroup$
    – corey979
    Commented Oct 22, 2016 at 11:49

1 Answer 1

Reset to default
7
$\begingroup$

As Rolf Mertig pointed out, it is due to the poor choice of Method.

AbsoluteTiming[Sum[nn, {nn, 1, 10^6},
        Method -> #]][[1]] & /@ {Automatic, "Polynomial", "Procedural", "RationalFunction"}

{0.147212, 0.000725, 0.013981, 0.000916}

AbsoluteTiming[Sum[nn, {nn, 1, 10^7},
        Method -> #]][[1]] & /@ {Automatic, "Polynomial", "Procedural", "RationalFunction"}

{0.003995, 0.000429, 0.135826, 0.000984}

Improve this answer
$\endgroup$

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