Hacker News Reader

Comment by skybrian | Hacker News Reader

I'm not sure how useful this is in practice. For example, addition in actual computer languages isn't necessarily associative and compilers often can't treat them as associative.

Floating point numbers added in the wrong order can result in catastrophic cancellation. So for example, as far as JavaScript is concerned, numbers aren't associative.

Integers may overflow. Twos-complement addition is associative, but only because if you get the same bogus answer in the case of overflow. If you actually detect overflow, you may get overflow or not depending on the order in which you add the numbers.

Oftentimes we ignore these issues, but it seems like if you're talking about taking advantage of associative rules to reorder calculations, you have to think about it. Thinking in terms of semigroups instead of concrete datatypes seems like a likely source of bugs when your model makes assumptions that aren't actually true.

View on HN

At a certain level you are correct. A compiler certainly should not be reordering FP calculations, for instance. However, at the level these abstractions are typically used they are absolutely fine. For example, if you want to add up the number of hits your web site has received you will be absolutely fine to use a 64-bit integer and treat addition as associative. There is no possibility of overflow. Similarly, if you train a machine learning model using gradient descent you can compute your gradients in parallel and then sum them, taking advantage of associativity, and this will work out fine. (See Hogwild! for some proofs that #YOLO is an acceptable strategy for SGD https://people.eecs.berkeley.edu/~brecht/papers/hogwildTR.pd...)

So, basically, semigroups and other abstractions are a-ok where they are typically used.

Is unsigned arithmetic non-associative?

Integer addition is associative, even for fixed-bitwidth integers (which constitute "the integers modulo 2^n" for some bitwidth n; e.g. 8-bit bytes under addition form the group of integers modulo 2^8 (i.e., integers modulo 256)).

Note that both the full integers as well as the integers modulo n are groups under addition. As groups are more restrictive than semigroups, all groups are also semigroups (groups are semigroups that also have an identity element and where every element is invertible).

Integer multiplication also forms a semigroup (and in fact a monoid, due to identity), but not a full group due to zero not having an inverse. So, it's usually said that "the non-zero integers" form a group.

You mean integer multiplication in Z_p?

Well, Z_n in this case, but yes.

> Integer multiplication also forms a semigroup (and in fact a monoid, due to identity), but not a full group due to zero not having an inverse.

Wait, what? Very few integers have multiplicative inverses (in the integers). If you meant to speak of modular inverses, then even that is false for composite moduli like 2^n (with n > 1), which may be why im4w1 (https://news.ycombinator.com/item?id=12113934) asked if you meant to work modulo a prime.

Ah, you're right. I don't know what I was thinking. Thanks for the correction!

Reply on news.ycombinator.com