Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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


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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: