News for hackers. Stuff that matters.
Re:Project Euler by archgoon on Monday October 14, 2024 @09:01PM (#41843878)
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.

Re:Project Euler by j2kun on Monday October 14, 2024 @10:19PM (#41844299)
I believe the term for this is scalar evolution.
Re:Project Euler by archgoon on Monday October 14, 2024 @10:23PM (#41844325)
Yep! That is it alright.

Here's a talk from an llvm conference with the details.

https://www.youtube.com/watch?v=AmjliNp0_00

Re:Project Euler by sbrother on Tuesday October 15, 2024 @12:41AM (#41845005)
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?
Re:Project Euler by marin049 on Tuesday October 15, 2024 @01:00AM (#41845099)
Integer overflow is actually undefined behaviour thus the compiler is free to assume it doesn't happen.
Re:Project Euler by xigoi on Tuesday October 15, 2024 @12:47PM (#41850481)
If you assume two’s complement arithmetic, then this is always equivalent because you’re basically just calculating the answer in a modular ring.