Friday, August 14, 2009

A Small Mathematica Vs C Benchmark

Sometimes I get frowned upon because I do expensive computations in Mathematica. Some expensive computations will be very fast in Mathematica, of course. Try computing (10^4)//Factorial.

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:

Table 1. Run times of the Euler project 9 algorithm in seconds. M stands for Mathematica
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.

5 comments:

  1. 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.

    In 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

    ReplyDelete
  2. 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.

    Thanks 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.

    ReplyDelete
  3. Niko,

    I 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

    ReplyDelete
  4. Hi Niko,

    you 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

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

    http://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

    ReplyDelete

Note: Only a member of this blog may post a comment.