Project Euler #912: Where are the Odds?

During the solving of a problem on Project Euler, I learned that compilers are smarter than me.

I don't remember the problem number or its title, but it involved starting from the top-left corner of a 2D grid and finding how many possible paths there are to get to the bottom-right corner while only moving either down or right.

My naive solution was a brute-force depth-first recursive search. On my CPU at the time, it took about 3 minutes to solve. I thought, the logic of this is incredibly simple, why not do it in assembly?

My assembly solution took 5 minutes.

I decompiled the compiled C code to see what it had done, but I couldn't understand it. My assembly knowledge was too basic.

Thinking on it now, I wonder if a modern compiler would solve the entire problem at compile-time and just hard-code the answer to be output at runtime.

So fun fact, if you compile

  int sum(int n) {
      int sum = 0;
      for(int i = 0; i < n; i++) {
          sum +=i;
      }
      return sum;
  }

clang, with -O2, will turn this into the polynomial (n+1)*n//2. It can also do similar transformations for multiple loops.

https://godbolt.org/z/so6neac33

So if you do a brute force solution which could have been reduced to a polyomial, clang has a shot of doing just that.

That is mind blowing, but it’s not immediately obvious to me that it’s equivalent for n > sqrt(INT_MAX). Is it? And if so, is the compiler somehow smart enough to know that?