Baffling increase in runtime

Question

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]

Answer 1

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:

Developer`MachineIntegerQ /@ {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}