alt Hacker NewsTo provide the solution to the second part of the question, there is no closed-form solution. Since floating point math is not associative, there’s no O(1) optimization that can be applied that preserves the exact output of the O(n) loop.
Replies
Technically there is a closed form solution as long as the answer is less than 2^24 for a float32 or 2^53 for a float64, since below those all integers can be represented fully by a floating point number, and integer addition even with floating point numbers is identical if the result is below those caps. I doubt a compiler would catch that one, but it technically could do the optimisation and have the exact same bit answer. If result was intialised to a non-integer number this would not be true however of course.
This is why you have options like -ffast-math, to allow more aggressive but not 100% identical outcome optimizations.
You can split the problem into chunks, where each chunk has the same exponents all the way through. It doesn't get you O(1), but it gets you O(log(n)).