Adding integers between 1 and n!

Questions
,
1

Re Mathematica 10.2 running under Windows 8.

This compiled code adds the integers between 1 and n! inclusive. Yes, it’s easier to use the formula n! (n! + 1) / 2 but I’m timing a loop.

g = Compile[{{n, _Integer}}, Module[{s = 0}, Do[s += k, {k, 1, n!}]; s],
RuntimeOptions → {“CatchMachineIntegerOverflow” → True},
CompilationTarget → “C”];

It works for n = 12:

AbsoluteTiming@g@12

Out[7]= {3.69531, 114721266640780800}

But fails for n = 13, returning the message “CompiledFunction::cfne: Numerical error encountered; proceeding with uncompiled evaluation. >>”

However, this compiled function works for n = 13:

h = Compile[{{n, _Integer}}, n! (n! + 1) / 2,
   RuntimeOptions -> {"CatchMachineIntegerOverflow" -> True},
   CompilationTarget -> "C"];

AbsoluteTiming@h@13

Out[2]= {0.0000384889, 1.93879*10^19}

So, what is the numerical error that bites the first code, forcing it to punt to “regular” Mathematica but not the other? Is it simply the very long loop that causes this problem? Thanks.

2

It’s a lot faster to use Sum. However, I gather you’re more interested in checking out loops.

In[8]:= AbsoluteTiming @ Sum[i, {i, 12!}]

Out[8]= {0.000297149, 114721266640780800}

In[10]:= (12! (12! + 1))/2

Out[10]= 114721266640780800

In[9]:= AbsoluteTiming @ Sum[i, {i, 13!}]

Out[9]= {0.000228342, 19387894024929830400}

In[11]:= (13! (13! + 1))/2

Out[11]= 19387894024929830400
3

Notice that the result for n=13 is a real number rather than an integer. With the nondefault option setting, the compiled code apparently allows a transfer from machine integers to machine doubles. Whichmakes good sense, given the name of the option.

If you are trying to time a basic flop count this might not pose any problem. This is especially true if the underlying processor speeds are roughly equal for machine ints vs. doubles. If you really need to be certain of arithmetic speed on machine ints, then you will need to change the code to stay under the maximum size for those.

4

Thanks, Frank. You’re right – I’m more interested in loops. The summing example just starts discussion. Your use of Sum, however, is a good observation.

5

Thanks, Dan. I was afraid of that but that’s the way it goes.

The code below works but can it be simpler? The module declares s = 0. and not s = 0 because the latter never returned an answer. I used the gamma function to get a floating point result – (1.0 n)! didn’t work.

g = Compile[{{n, _Integer}}, 
   Module[{s = 0.}, Do[s += k, {k, Gamma[1. + n]}]; s], 
   CompilationTarget -> "C"];

n = 13;
AbsoluteTiming@g@n

{13.5818, 1.93879*10^19}