NOTE: This is an archive of my old blog. Go to for my current website.

Code Kata: Project Euler #1

Posted by md on March 30, 2008

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.

Use this link to trackback from your own site.


Leave a response