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

## 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:
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.

##### Trackbacks

Use this link to trackback from your own site.