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

There are many ways to swap two variables without using a temp variable, as long as the type of the variables is a mathematical group[0].

If the group operation is denoted <>, with identity e, and the inverse of 'a' is 'inv(a)' then you would do

    a = a0;
    b = b0;            // initial assignment

    a = a <> b;        // a = a0 <> b0 and b = b0.
    b = a <> inv(b);   // a = a0 <> b0 and b = a0 <> b0 <> inv(b0) = a0.
    a = inv(b) <> a;   // a = inv(a0) <> a0 <> b0 = b0 and b = a0.
This works when a and b are ints, which are a group with the operator '+' and identity '0', and inverses inv(n) = -n (see [1])

It works when a and b are nonzero floats, which are a group under multiplication with identity 1.0 and inverses inv(x) = 1/x (but see [2]).

It works when a and b have fixed-length binary representations, because fixed-length binary strings are a group where the operation is xor (or '^') and inv(x) = x.

It works when a and b are matrices of the same dimension, which form a group in two different ways - under matrix addition, where the inverse is elementwise negation, and under matrix multiplication (if a and b are nonsingular) where the inverse is the regular matrix inverse [3].

Note that in my third line, the right-hand side of the assignment is inv(b) <> a, whereas all the examples in the blog post used a <> inv(b). They were implicitly assuming a commutative group (i.e. a <> b == b <> a for all a and b) whereas my procedure works even for non-commutative groups, e.g. matrices under matrix multiplication.

Edit: Obviously, if you actually use this in real code... WAT.

[0] http://en.wikipedia.org/wiki/Group_(mathematics)

[1] this even works if one of the operations causes an integer overflow - the magic of modular arithmetic!

[2] floats don't really form a group, because of non-associativity of floating point multiplication.

[3] http://en.wikipedia.org/wiki/Invertible_matrix




> fixed-length binary strings are a group where the operation is xor (or '^') and inv(x) = x

Most people would call this group (Z/2Z)^n, i.e. n copies of Z/2Z under addition. Similarly, for "matrix addition" you could say Z^(mn) or R^(mn) for matrices with dimension mxn with elements Z or R (or whatever you are filling your matrices with). Your only non-abelian example is matrix multiplication, i.e. GL(n,R), general linear transformations of dimension n over R. It may or may not be interesting that this is mainly focused on abelian groups.


>"Edit: Obviously, if you actually use this in real code... WAT."

For those who haven't seen the video : http://www.youtube.com/watch?v=D0EIZa5e9q4&t=0m40s


Actually, isn't having unique inverses a weaker requirement than being a group? Maybe I am wrong...


There are algebraic objects for which inverses are defined, but which aren't groups: namely groupoids, quasigroups and loops.

In groupoids the binary operation isn't total, i.e. there can be pairs (a,b) for which a <> b is not defined -- so we can't use groupoids.

In quasigroups and loops the binary operation doesn't need to be associative. But we require associativity, so that we can deduce

    (a <> b) <> inv b == a <> (b <> inv b) == a <> e == a
So we do actually need all the properties of a group.


A commenter on Reddit pointed out that quasigroups require both left and right division operators \ and /, and that even though they are not associative, the axioms

    x \ (x * y) = y
    x * (x \ y) = y
    (x * y) / y = x
    (x / y) * y = x
must hold -- so in fact, quasigroups are good enough!




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

Search: