Project Euler 78: Counting Partitions

Question

Project Euler problem 78:

Let \$p(n)\$ represent the number of different ways in which \$n\$ coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so \$p(5)=7\$.

Find the least value of \$n\$ for which \$p(n)\$ is divisible by one million.

I used Euler's recurrence relation for the partition of \$n\$, together with the fact that modular addition is distributive: $$(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n.$$

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  // generalized pentagonal numbers
  vector<int> g = vector<int>({1, 2}); // g_1 = 1, g_-1 = 2 
  // integer partitions
  vector<int> p = vector<int>({1}); // p_0 = 1
  for (int n = 1; n ; n++) {
    if (g.back() <= n) {
      int k = g.size()/2 + 1;
      g.push_back(k*(3*k - 1)/2);
      k *= -1;
      g.push_back(k*(3*k - 1)/2);
    }
    int p_n = 0;
    for (vector<int>::iterator g_k = g.begin(); *g_k <= n; ++g_k) {
      if ((g_k - g.begin())/2 % 2 == 0) {
        p_n += p[n - *g_k];
      } else {
        p_n -= p[n - *g_k];
      }
    }
    p.push_back(p_n % 1000000); 
    if (p.back() < 0) p.back() += 1000000;
    if (p.back() == 0) {
      cout << n << endl;
      break;
    }
  }
  return 0;
}

My i7 handles this in ~25ms, but my circa 2008 32-bit centrino needs 600ms. Is there any way that I can squeeze more performance out of the above code? Also, with the exception of removing using namespace std;, is there anything I can do to make the code cleaner/more readable/more presentable?

Answer 1

I see a few minor things that may help you improve your code.

Use list initializers directly

The declarations of g and p are more complex than they need to be. Instead, one can use list initializers directly:

vector < int >g{1, 2};
vector < int >p{1};

This makes the code more readable.

Use auto where it helps readability

Similarly, the inner for loop can be made a bit simpler using auto:

for (auto g_k = g.begin(); *g_k <= n; ++g_k) {

Use const where practical

In this case, const isn't used explicitly, but a const iterator may be used in that same inner loop:

for (auto g_k = g.cbegin(); *g_k <= n; ++g_k) {

Avoid costly mathematical operators

Both the / and % operators tend to be somewhat more computationally costly than + and -. For that reason, if performance is your goal, you might want to seek ways to minimize the use of those more costly operators. For instance, instead of this line:

if ((g_k - g.begin()) / 2 % 2 == 0) {

You could write this instead (assuming 2's complement representation):

if ((g_k - g.cbegin()) & 2) {

On my machine, this gives a measurable speed increase.

Simplify in-loop operations as much as possible

The first if statement uses multiplication and division to calculate the values, but a simple analysis of the numbers shows that it's a fairly simple series, and so the numbers can be calculated using only addition:

int k = 2;
int m = 5;
int dm = k+m;
for (int n = 1; n; n++) {
    if (g.back() <= n) {
        g.push_back(m);
        g.push_back(m + k++);
        m += dm;
        dm += 3;
    }
    // etc.

Use longer, more meaningful names

Names like p and g are not very descriptive. Because this is a fairly short program and mathematical in nature, this isn't a terrible flaw, but it's worth considering if there might be more meaningful names that could be used.

Eliminate "magic numbers"

This code has a number of inscrutable "magic numbers," that is, unnamed constants such as 2, 3, 1000000, etc. Generally it's better to avoid that and give such constants meaningful names. That way, if anything ever needs to be changed, you won't have to go hunting through the code for all instances of "2" and then trying to determine if this particular 2 is relevant to the desired change or if it is some other constant that happens to have the same value.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers). In this particular case, I happen to think it's perfectly appropriate because it's a single short program that and not a header. Some people seem to think it should never be used under any circumstance, but my view is that it can be used as long as it is done responsibly and with full knowledge of the consequences.

Answer 2

I'll just comment on the cleanliness/readability aspect:

• In spite of the given comments, you should give g and p better names. It'll also allow you to remove those comments, which is good because they shouldn't need to be used as such.

• This kind of initialization isn't really necessary:

  vector<int> g = vector<int>({1, 2});
  

  It could just be this:

  vector<int> g = { 1, 2 };
  

  If you're using C++11, you can also omit the =.

• This loop statement may be a little hard to read:

  for (int n = 1; n ; n++)
  

  It's understood that having n alone means the loop will continue as long as it's nonzero, but you can still make that clear here anyway. It's otherwise hard to read this statement at a glance.

• This calculation is unclear as written:

  g.push_back(k*(3*k - 1)/2);
  

  You also reuse it, so consider making it a constant in terms of k.

• Try to add more blank lines between code sections, such as the loops. Having everything together like this can make it harder for the brain to parse out different sections easily.

• The number 1000000 here is a "magic number" (ambiguous hard-coded number). As such, it should be assigned to a constant with a relevant name. This will also allow you to change this number in just one place.