4 ms·

A small correction: the sigma summation should go to n-1, not n. It's weird that LLVM computes n(n-1)/2 in such a convoluted way, namely: (n-1)(n-2)/2 + n - 1

sham1 2y ago
IIRC that way of doing the summation is specifically done to avoid issues with overflow.
- valleyer 2y ago
  I feel like you're probably right, but I can't figure out the exact reason. The multiplication of (n-1)(n-2) already expands to 64 bits. It has to: Even when the loop accumulator doesn't overflow when counting up to n(n-1)/2 in the abstract machine, (n-1)(n-2) will be larger (and possibly overflow 32 bits) for most n. (The highest valid n is 92682, I think.) So surely once you're doing that, I'd think n(n-1)/2 can be done in 64 bits just as easily. unsigned int sum2(unsigned int n) { unsigned long ln = n; return ln * (ln - 1) / 2; } a.out <+0>: pushq %rbp a.out <+1>: movq %rsp, %rbp a.out <+4>: movl %edi, %ecx a.out <+6>: leaq -0x1(%rcx), %rax a.out <+10>: imulq %rcx, %rax a.out <+14>: shrq %rax a.out <+17>: popq %rbp a.out <+18>: retq
constantcrying 2y ago
It has to. Just imagine what happens when in the iterative algorithm count = count + i is just before overflowing. In that case the O(N) algorithm has no overflow, but if you look at the closed form solution. Surely (count)*(count-1) would overflow. A compiler must never be allowed to swap a non-overflow with a overflow. Which is one big limit of these optimizations.
- valleyer 2y ago
  Sure, but in the scenario you describe, (count-1)*(count-2) also overflows, and that's why the generated code already to 64 bits for the multiply. (See my cousin comment to this one.)

sham1 2y ago

IIRC that way of doing the summation is specifically done to avoid issues with overflow.

valleyer 2y ago
I feel like you're probably right, but I can't figure out the exact reason. The multiplication of (n-1)(n-2) already expands to 64 bits. It has to: Even when the loop accumulator doesn't overflow when counting up to n(n-1)/2 in the abstract machine, (n-1)(n-2) will be larger (and possibly overflow 32 bits) for most n. (The highest valid n is 92682, I think.) So surely once you're doing that, I'd think n(n-1)/2 can be done in 64 bits just as easily. unsigned int sum2(unsigned int n) { unsigned long ln = n; return ln * (ln - 1) / 2; } a.out <+0>: pushq %rbp a.out <+1>: movq %rsp, %rbp a.out <+4>: movl %edi, %ecx a.out <+6>: leaq -0x1(%rcx), %rax a.out <+10>: imulq %rcx, %rax a.out <+14>: shrq %rax a.out <+17>: popq %rbp a.out <+18>: retq

constantcrying 2y ago

It has to. Just imagine what happens when in the iterative algorithm count = count + i is just before overflowing. In that case the O(N) algorithm has no overflow, but if you look at the closed form solution. Surely (count)*(count-1) would overflow. A compiler must never be allowed to swap a non-overflow with a overflow. Which is one big limit of these optimizations.

valleyer 2y ago
Sure, but in the scenario you describe, (count-1)*(count-2) also overflows, and that's why the generated code already to 64 bits for the multiply. (See my cousin comment to this one.)