Hacker News new | comments | show | ask | jobs | submit login

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!




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.


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.)


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.


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).


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.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: