Comment by joe_the_user

Comment by joe_the_user 10 months ago

Aren't all computations inherently serial?

No. "inherently serial" refers to problems that are specified serially and can't be spend up by parallel processing. The sum of a set of N numbers is an example of a problem that is not inherently serial. You can use parallel reduction to perform the computation in O(log(N)) time on an idealized parallel computer but it takes O(N) time on an idealized serial computer.

And, it turns, exactly which problems are really are inherently serial is somewhat challenging problem.

visarga 10 months ago

> The sum of a set of N numbers is an example of a problem that is not inherently serial.

But addition with floats (not reals) is non associative.

Reply View 2 replies

immibis 10 months ago

They didn't say floats, and the sum of a set of floats is not uniquely defined as a float for the rain you stated, at least not without specifying a rounding mode. Most people use "round to whatever my naïve code happens to do" which has many correct answers. To add up a set of floats with only the usual 0.5ULP imprecision, yes, isn't trivial.

Reply View | 0 replies
rand_r 10 months ago

Using hardware floating point types is not suitable if mathematical correctness matters, and is largely a deprecated practice. Check out Python’s fraction module for example, for exact arithmetic[0].
[0]: https://www.geeksforgeeks.org/fraction-module-python/

Reply View | 0 replies