I don't think it requires big integers. If you do it with machine words, the overflow/underflow will exactly cancel out so you will be fine. I think. If that's

I don't think it requires big integers. If you do it with machine words, the overflow/underflow will exactly cancel out so you will be fine. I think. If that's not true, then adding each x and subtract i as you process it is sufficient to ensure you only need integers comparable in size to N, not N^2.