Message Boards Message Boards

0
|
8929 Views
|
4 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Adding integers between 1 and n!

Bruce Colletti
Posted 9 years ago

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.
POSTED BY: Bruce Colletti
4 Replies
Sort By:
Bruce Colletti
Bruce Colletti
Posted 9 years ago

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}
POSTED BY: Bruce Colletti

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.
POSTED BY: Daniel Lichtblau

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
POSTED BY: Frank Kampas
Bruce Colletti
Bruce Colletti
Posted 9 years ago

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.
POSTED BY: Bruce Colletti
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract