gonium.net

Following the example of doing code katas, I spend my sunday morning thinking about integer performance in C++. Project Euler provides a nice collection of mathematical problems. As it turns out, some of my assumptions on C++ were totally wrong :-) The problem to solve is the following:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Quite easy. A straightforward, naive implementation uses the modulo operator to filter the integers up to the maximum: unsigned long method1(const unsigned long max) { unsigned long sum=0; for (unsigned long i=0; i torrent; for (unsigned long i=0; i::iterator it; for (it=torrent.begin(); it != torrent.end(); it++) { sum += (*it); } return sum; } Turns out this code is way slower than the first method: 0.34318700 seconds, more than two orders of magnitudes. Thinking of it, it is easy to see why: while the first method can completely run within the CPU, the second code suffers from accessing the main memory. I didn’t assess the overhead imposed by the std::set (no working gprof around). As it turns out, the C++ modulo operator uses the assembler div operation – so the compiler can optimize the code, keep all variables in registers, and use a fast operation. However, the above code is not quite nice as it allows integer overflows for the sum variable. The GNU MP Bignum Library (GMP) provides big integers. Method 3 uses them for the sum variable: mpz_class method3(const unsigned long max) { mpz_class sum(0); for (unsigned long i=0; i Project Euler – Problem 1 Method 1: 1404932684 -> 0.00952700 s. Method 2: 1404932684 -> 0.34736500 s. Method 3: 1404932684 -> 0.01851300 s. Method 4: 1404932684 -> 0.57744300 s. Method 5: 1404932684 -> 0.00094000 s. Creating comparison of methods 4 and 5 100 2318(0.00006400) 2318(0.00001400) 10000 23331668(0.00579500) 23331668(0.00043900) 1000000 233333166668(0.57718100) 233333166668(0.05124100) 100000000 2333333316666668(57.69583200) 2333333316666668(5.84172500) You can download the code from the download page.