6 ms·
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.
by joe_the_user 2y 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 2y 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.
- immibis 2y agoThey 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.
- rand_r 2y agoUsing 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/ https://www.geeksforgeeks.org/fraction-module-python/