3 ms·

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, w

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

j2kun 2y ago
I believe the term for this is scalar evolution.
- archgoon 2y ago
  Yep! That is it alright. Here's a talk from an llvm conference with the details. https://www.youtube.com/watch?v=AmjliNp0_00 https://www.youtube.com/watch?v=AmjliNp0_00
sbrother 2y ago
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?
- marin049 2y ago
  Integer overflow is actually undefined behaviour thus the compiler is free to assume it doesn't happen.
- xigoi 2y ago
  If you assume two’s complement arithmetic, then this is always equivalent because you’re basically just calculating the answer in a modular ring.