[Jprogramming] Aiming at a multi-core future

[Mark D. Niemiec]

Viktor Cerovski <viktor.cerovski at gmail.com> wrote:

> An implicit assumption in such parallelization of +/ is that + is
> associative.
> This, strictly speaking, is true neither for floating point numbers nor
> for machine integers.  Furthermore, for extended precision integers 
> associativity holds but it might still be desirable to be able to control
> the order of execution to make time and/or space smaller.

While it cannot be made associative for floating point (without a lot of work),
the only bar to associativity for machine integers is in cases where an
intermediate sum overflows an integer and is promoted to floating point.

On 32-bit machines, floating-point numbers have more precision (53 bits),
so the only way you could lose data (and associativity) is by adding a list of
2^(53-32), or around 2 million or more very large numbers.

On 64-bit machines, however, floating-point has less precision than integers, so
integer overflow will likely lose associativity.

(Then again, this is an implementation issue. It would be very easy for a
distributed implementation to compute sums of integers using double
machine words, and then only convert to floating point if the final
result won't fit in a single machine word - not only is this faster, but
it also guarantees accuracy and  associativity. This can only overflow on
32-bit machines for arrays with more than 4 billion items - and you would
run out of memory and address space long before that. And on 64-bit machines,
it would take an array of more than 64 million terabytes. I'm not overly concerned.)

-- Mark D. Niemiec <mniemiec at interserv.com>