# Baffling increase in runtime

Background of my question

I discovered Project Euler today, and decided I would work through the problems in Mathematica. I became obsessed with the first problem, which is essentially "sum all the numbers from 0 to n that are multiples of 3 or 5". I came up with several interesting solutions, and decided I would compare their runtimes to see if there is a way to optimize this calculation. While amusing myself with ListPlot's of runtimes, I noticed some very interesting behavior in my solution that uses Fold:

FoldSum[m_, n_] :=
Fold[If[Mod[#2, 3] == 0 || Mod[#2, 5] == 0, #1 + #2, #1] &, 0, Range[m, n]]
FoldSum[n_] := FoldSum[0, n]


I came up with this plotting function in order to visualize the runtimes of the summing functions as n increased. (In order to maintain fairness amongst trials, I called ClearSystemCache[] just to ensure caching benefits are not messing with the independence of trials).

PlotSum[f_, a_, b_, step_] :=
ListPlot[{#, (ClearSystemCache[]; First[AbsoluteTiming[f[#]]])} & /@
Range[a, b, step], AxesOrigin -> {a, 0}]
PlotSum[f_, b_, step_] := PlotSum[f, 0, b, step]


It was quite interesting to generate graphs comparing the different summing functions I came up with (I listed them below in a separate section). For example, I would plot FoldSum's runtime from n = 0 to n = 999 in steps of 10 by executing PlotSum[FoldSum, 999, 10]

The question

My question pertains to the plot of FoldSum - I noticed that around n = 96000, the runtime of FoldSum suddenly jumps by a factor of around 15. I used the plotting function to generate smaller and smaller ranges until I finally found this:

In[1] = FoldSum[95934] // AbsoluteTiming
Out[1] = {0.020469, 2147472998}

In[2] = FoldSum[95935] // AbsoluteTiming
Out[2] = {0.303367, 2147568933}


My question is, what is so special about numbers greater than 95934 (i.e. why does the runtime suddenly jump by a factor of around 15)? Is it just my computer that does this, or is this reproducible?

Some other fun stuff

In case you actually threw this into Mathematica to reproduce these results, you might enjoy these other solutions:

ListSum[m_, n_] :=
Total[Select[Range[m, n], Mod[#, 3] == 0 || Mod[#, 5] == 0 &]]

TransposeSum[m_, n_] :=
Total[First /@
Select[Transpose[{Range[m, n], Mod[Range[m, n], 3],
Mod[Range[m, n], 5]}], #[[2]] == 0 || #[[3]] == 0 &]]

ConcurrentSum[m_, n_] :=
ParallelSum[If[Mod[i, 3] == 0 || Mod[i, 5] == 0, i, 0], {i, m, n}]

ParallelListSum[m_, n_] :=
Total[Level[
ParallelCombine[ListSum[First[#], Last[#]] &, Range[m, n]], 1]]

ParallelizeSum[f_, m_, n_] :=
Total[Level[ParallelCombine[f[First[#], Last[#]] &, Range[m, n]],
1]]
ParallelizeSum[f_, n_] := ParallelizeSum[f, 0, n]
(* ParallelizeSum[FoldSum, 999] *)


also, to graph a comparison plot between different solutions,

PlotCompare[fList_, m_, n_, step_] :=
ListPlot[PlotSumData[#, m, n, step] & /@ fList]
PlotSumData[f_, m_, n_,
step_] := {#, First[AbsoluteTiming[(ClearSystemCache[]; f[#])]]} & /@
Range[m, n, step]

-
an observation: your sum exceeds 2^31 when moving from 95934 to 95935... – Pinguin Dirk Jun 3 '13 at 8:20
@KeshavSaharia: Your observation is system dependent and does not produce the same result on my machine. On my machine, the increase in runtime is very close to a linear function which looks reasonable. There are many different factors that may affect the running time. Specially, in multitask operating systems, timing is not so accurate. You need to execute your test for a reasonable number of runs and take the average to get acceptable numbers. The temperature of the CPU may affect the runtime as well. Another factor is whether the algorithm is run on GPU or on CPU. – Helium Jun 3 '13 at 8:22
@KeshavSaharia: Do you have a 32 bit machine or OS? This may be the cause based on Pinguin's observation. – Helium Jun 3 '13 at 8:23
It might be just your computer... On my Mac OS X/Mathematica 9 system, I see a slowly rising trend from 80000 to 100000. – cormullion Jun 3 '13 at 8:25
Are you by chance using Mathematica 8? Integers were based on 32-bit machine values in previous versions, and this was changed to 64-bit only in version 9. As a result, Range[2^31, 2^31 + 1] returns a packed array only in the most recent version. While I don't have time now to fully understand the issue, a combination of bigints and non-packed arrays sounds like a plausible explanation for what you observe. Good work by @PinguinDirk in noticing this threshold! – Oleksandr R. Jun 3 '13 at 10:03

This is a common limitation experienced in versions prior to 9. As Oleksandr explains:

Are you by chance using Mathematica 8? Integers were based on 32-bit machine values in previous versions, and this was changed to 64-bit only in version 9. As a result, Range[2^31, 2^31 + 1] returns a packed array only in the most recent version.

Fold automatically compiles, and compiled functions cannot return values that are not machine-size integers, reals, etc. Observe:

DeveloperMachineIntegerQ /@ {2147472998, 2147568933}

{True, False}


You can get an explicit message regarding this compile issue by setting this system option:

SetSystemOptions["CompileOptions" -> "InternalCompileMessages" -> True];


Now:

FoldSum[95935]


CompiledFunction::cfn: Numerical error encountered at instruction 24; proceeding with uncompiled evaluation. >>

2147568933


By setting "FoldCompileLength" to Infinity you prevent this auto-compile and you will find that your timings are consistent (slow):

SetSystemOptions["CompileOptions" -> "FoldCompileLength" -> Infinity];

FoldSum[95934] // AbsoluteTiming
FoldSum[95935] // AbsoluteTiming

{0.1320075, 2147472998}

{0.1320076, 2147568933}

-
For me, on version 9, DeveloperMachineIntegerQ /@ {2^63 - 1, 2^63} gives {True, False}. As expected I guess. – Jacob Akkerboom Jun 3 '13 at 12:10