It really tickles my brain in a lovely way that it avoids all overflow risk as well

▲ repiret 2 days ago | parent | next [-]

There is no overflow risk. The trick works on any Abelian group. N-bit values form an Albanian group with xor where 0 is the identity and every element is its own inverse. But N-bit values also form an Abelian group under addition with overflow, where 0 is the identity and 2s-compliment is the inverse.

If you’re working on an architecture where a single multiplication and a bit shift is cheaper than N xor’s, and where xor, add, and sub are all the same cost, then you can get a performance win by computing the sum as N(N+1)/2; and you don’t need a blog post to understand why it works.

▲ ikurei 2 days ago | parent | next [-]

I think they meant that XOR avoids the overflow risk, whereas doing the sum of the array to figure out which number could cause an overflow.

	▲	jonathrg a day ago \| parent [-]
		(wrapping) overflow doesn't affect the final result.

▲ lblume 2 days ago | parent | prev | next [-]

You can also calculate the XOR-accumulation of all values between 1 and n in O(1) using a lookup table like this:

    [n, 1, n+1, 0][n%4]

▲ 2 days ago | parent | prev | next [-]

[deleted]

▲ OjotCewIo 2 days ago | parent | prev [-]

> The trick works on any Abelian group

(https://en.wikipedia.org/wiki/Abelian_group -- I'll use ⋆ as the Abelian group's operation, and ~ for inversion, below.)

I believe you are implying:

(g(1) ⋆ ... ⋆ g(n)) ⋆ ~(g(i(1)) ⋆ g(i(2)) ⋆ ... ⋆ g(i(n-1))) = g(m)

where "m" is the group element index that is not covered by "i".

However, for this to work, it is requried that you can distribute the inversion ~ over the group operation ⋆, like this:

~(g(i(1)) ⋆ g(i(2)) ⋆ ... ⋆ g(i(n-1))) = ~g(i(1)) ⋆ ~g(i(2)) ⋆ ... ⋆ ~g(i(n-1))

because it is only after this step (i.e., after the distribution) that you can exploit the associativity and commutativity of operation ⋆, and reorder the elements in

g(1) ⋆ ... ⋆ g(n) ⋆ ~g(i(1)) ⋆ ~g(i(2)) ⋆ ... ⋆ ~g(i(n-1))

such that they pairwise cancel out, and leave only the "unmatched" (missing) element -- g(m).

However, where is it stated that inversion ~ can be distributed over group operation ⋆? The above wikipedia article does not spell that out as an axiom.

Wikipedia does mention "antidistributivity":

https://en.wikipedia.org/wiki/Distributive_property#Antidist...

(which does imply the distributivity in question here, once we restore commutativity); however, WP says this property is indeed used as an axiom ("in the more general context of a semigroup with involution"). So why is it not spelled out as one for Abelian groups?

... Does distributivity of inversion ~ over operation ⋆ follow from the other Abelian group axioms / properties? If so, how?

▲ FBT a day ago | parent [-]

> ... Does distributivity of inversion ~ over operation ⋆ follow from the other Abelian group axioms / properties? If so, how?

It does. For all x and y:

  (1) ~x ⋆ x = 0 (definition of the inverse)
  (2) ~y ⋆ y = 0 (definition of the inverse)
  (3) (~x ⋆ x) ⋆ (~y ⋆ y) = 0 ⋆ 0 = 0 (from (1) and (2))
  (4) (~x ⋆ ~y) ⋆ (x ⋆ y) = 0 (via associativity and commutativity)

In (4) we see that (~x ⋆ ~y) is the inverse of (x ⋆ y). That is to say, ~(x ⋆ y) = (~x ⋆ ~y). QED.

	▲	stephencanon a day ago \| parent \| next [-]
		Right. Another way to see this is that for a general (possibly non-Abelian) group, the inverse of xy is y⁻¹x⁻¹ (because xyy⁻¹x⁻¹ = x1x⁻¹ = xx⁻¹ = 1 [using "1" for the identity here, as is typical for general groups], or more colloquially, "the inverse operation of putting on your socks and shoes is taking off your shoes and socks"). For an Abelian group, y⁻¹x⁻¹ = x⁻¹y⁻¹, and we're done.
	▲	OjotCewIo a day ago \| parent \| prev [-]
		Awesome, thanks! :)

▲ analog31 2 days ago | parent | prev [-]

True, I hadn't thought of that. I'm spoiled by Python. ;-)