# Why is summing 1 million slow? [duplicate]

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:= RepeatedTiming[Sum[nn, {nn, 1, 10^6}]]

Out= {0.52, 500000500000}

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

Out= {0.000086, 50000005000000}


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

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

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

Out= {{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:= ListLogLinearPlot[data, PlotRange -> All,
AxesLabel -> {None, "Time [s]"}] Why is summing 10^6 so much slower?

## marked as duplicate by Mr.Wizard♦Oct 22 '16 at 11:20

• 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. – Rolf Mertig Oct 22 '16 at 10:08
• This issue also occured in this thread. – corey979 Oct 22 '16 at 11:49

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

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


{0.147212, 0.000725, 0.013981, 0.000916}

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


{0.003995, 0.000429, 0.135826, 0.000984}