News for hackers. Stuff that matters.
Re:The Three Ways of XOR by macawfish on Sunday February 12, 2017 @06:37PM (#13631871)
One thing I love about xor is an interesting correspondence between bitwise xor and the outer product of the exterior algebra.

Say we have an N=4 dimensional vector space, and we use binary place values to represent units vector in a basis, like this:

w = 1000

x = 0100

y = 0010

z = 0001

Then a multivector basis could be represented e.g.:

xyz = 0111

xy = 0110

wz = 1001

Now, if ^ is the outer product:

xy^yz = xz ↔ 0110 xor 0011 = 0101.

wx^yz = wxyz ↔ 1100 xor 0011 = 1111.

and so on.

If anyone has more information about this, I'd be really interested in seeing it!

Re:The Three Ways of XOR by taneq on Sunday February 12, 2017 @07:43PM (#13632198)
I had a similar 'aha' moment a few years ago about inner product (aka dot product) and the choice of '.' as an operator to access elements of a structure.

    struct Example {
      int elem1;
      int elem2;
      ...
    };
    
    Example ex1 = { 1, 2, ... };
    int a = ex1.elem1;
    int b = ex1.elem2;
    ...
If we think of ex1 as a vector, and elem1 as a constant vector [1, 0, 0...] (and elem2 as a constant vector [0, 1, 0, ...] and so on) then ex1.elem1 is literally the inner product of ex1 and the constant elem1.

I have no idea if that was the original thinking behind dot notation but it's neat and I like it.

Re:The Three Ways of XOR by halma on Monday February 13, 2017 @08:03AM (#13634906)
I remember this and other tricks are implemented in Gaigen (a code generator for geometric algebra).

https://sourceforge.net/projects/g25/?source=directory

The XOR trick is close to slide 16 of http://www.science.uva.nl/research/ias/ga/gaigen/files/20020...

...

How to compute the geometric product of unit orthogonal basis blades (3/3) If we represent each basis vector with a specific bit in a binary number (e1 = 001b, e2 = 010b, e3 = 100b), computing the geometric product of basis blades is exactly the xor operation on binary numbers!

  (e1^e2)(e2^e3) = e1^e3
  011b xor 110b = 101b
We have to take care of the signs though:

- basis vectors have to be rearranged into a specific order before they can annihilate each other (this rearranging causes a sign change in the result). This can also be computed binary. - signature of annihilated basis vectors can change the sign as well.

Re:The Three Ways of XOR by knappa on Sunday February 12, 2017 @08:17PM (#13632372)
Unless you mean something different from the usual multilinear algebra meaning of "exterior algebra", xy^yz is zero. (It contains two y's.) I think that you must actually mean Clifford algebras. (But there are also signs when in characteristic ≠ 2.)
Re:The Three Ways of XOR by macawfish on Sunday February 12, 2017 @09:15PM (#13632671)
Yeah, I do mean Clifford algebras. Thanks for the catch. I'll have to study up on the distinction between "outer products" in Clifford algebras and exterior algebras.
Re:The Three Ways of XOR by johncolanduoni on Monday February 13, 2017 @03:36AM (#13633931)
They are isomorphic as vector spaces (again with characteristic != 2), but their products are not preserved by the isomorphism (unless the Clifford algebra is trivial).