But what about the cheap computations that you could as well do in C? The Euler Project gave me the change to try it out with an easy problem. I was solving problem 9 from project Euler, which in short searches for natural numbers a<b<c, such that a^2+b^2=c^2, and a+b+c=1000.

The C-program that finds these numbers is

int main(void) {

for(int a = 1; a < 10000; a++) {

for(int b = a + 1; b <= 10000; b++) {

int c = 1000 - a - b;

if(a * a + b * b == c * c) {

printf("%d\n",a*b*c);

return 0;

}

}

}

}

Note that I de-optimized a little bit by bounding a and b in [1,10,000], which is ten times greater than it should be. The result is still correct, but now it's slow enough so that we can measure something.

The run-time in C is 0.016 seconds on my machine

Bringing this to Mathematica is more than straightforward:

Module[{a, b, c},

For[a = 1, a <= 10000, a++,

For[b = a + 1, b <= 10000, b++,

c = 1000 - a - b;

If[a a + b b == c c, Return[a b c]]

]

];

0

][]

Now the run-time is at 8.5 seconds. But! Mathematica can compile! To something faster, that is. It's as easy as wrapping a Compile around the computation. We get:

Compile[{},

Module[{a, b, c},

For[a = 1, a <= 10000, a++,

For[b = a + 1, b <= 10000, b++,

c = 1000 - a - b;

If[a a + b b == c c, Return[a b c]]

]

];

0

]

]

And now we're down to 0.38 seconds. Just as a reminder:

C | uncompiled M | compiled M |
---|---|---|

0.16 | 8.53 | 0.38 |

Which brings me to the following conclusion: For basic arithmetic computation, Mathematica will slow you down by a factor 40, if you use it only casually, or by a factor of 2 if you have some experience with it (Not everything is nicely compilable, so this is a bit optimistic).

Mathematica taketh away, but it also giveth: The library functions are fast, and there's plenty of them. You can treat Mathematica just like any scripting language: If the operations in your inner loop are costly, Mathematica is good for you! Otherwise, you pay a price for a wide range of library-functions. And it is worth delving into that library.

If you directly translate C code to Mathematica you will end up with non-optimal Mathematica code. Sure, Compile[] will speed up certain numeric computations, but in some cases you're just much better off solving the problem in a different way.

ReplyDeleteIn this case (on my laptop):

Nested For[] loops: 12.33 seconds

Single Do[] loop: 9.89 seconds

Compiled nested For[] loops 0.59 seconds

Compiled single Do[] loop 0.42 seconds

But if I solve the problem in a different way, using Mathematica's Reduce[] function, I get every possible solution (not just the first one) in a fraction of the time (0.12 seconds).

Reduce[{a^2 + b^2 == c^2, c == 1000 - a - b, b >= a, a >= 1}, {a, b, c}, Integers] // AbsoluteTiming

-Rob

Hi Ragfield! Well, I slowed down the loops by choosing the ranges too big. I know, silly me, makes things incomparable. But it's just too fast in all languages if you choose the proper bounds! Which is why Reduce can compete.

ReplyDeleteThanks for the single Do loop, that actually makes a difference!

I find interesting how in Mathematica you can have significant speed differences for choosing very similar things.

Niko,

ReplyDeleteI was unaware of the (possible) speedups using compile! Thanks for the demo.

@ragfield (hey, is that you?!)

c should be positive as well; this will yield one answer, corrected code would be something like:

Reduce[a^2+b^2==c^2 && c==1000-a-b && 0 < a < b < c, {a,b,c}, Integers]//AbsoluteTiming

The real challenge is to compute a*b*c:

Reduce[a^2+b^2==c^2 && c==1000-a-b && 0 < a < b < c, {a,b,c}, Integers][[All,2]]/.And->Times//AbsoluteTiming

(here is just replaced the head from And to Times to do the product)

Cheers!

Sander

Hi Niko,

ReplyDeleteyou may be interested in the following rather perverse solution, which is about 10 times faster than your compiled one, and thus, about 2-3 times slower than C code:

fn = Compile[{},

Module[{al = Range[10000],bl=1,c=Range[10000],d=Range[10000],zeros = 0*Range[10000]},

For[bl=1,bl<=10000,bl++,

c=1000-al-bl;

d=UnitStep[-Abs[c*c-bl*bl-al*al]];

If[d!=zeros,Break[]]];

c=d*al*bl*c;

Return[Total@c]]];

Besides, I think you missed an extra zero - your compiled code is really about 20-30 times slower than C code, while the uncompiled version is couple of hundreds times slower than C code.

Regards,

Leonid

could you please check this page and say how to fix it

ReplyDeletehttp://stackoverflow.com/questions/4830953/compute-the-arithmetic-functions-for-large-integer-in-mathematica-faster

http://stackoverflow.com/questions/4832062/how-to-write-the-code-for-this-program-specially-in-mathematica