Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Three Ways of XOR

horia141.com

Post reply on HN
Print view View original

21–30 of 69 posts

Re: The Three Ways of XOR

#21

Post by blurbleblurble »

knappa wrote: post #20
blurbleblurble wrote: post #13

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…

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.

Re: The Three Ways of XOR

#22

Post by Existenceblinks »

ambrop7 wrote: post #2

> most programming languages don’t have an explicit “logical operator” for it I guess the author never taught of != . The only thing to be careful with is that it doesn't implicitly convert arguments to boolean, so expressions like " != (flags & Flag)" will go wrong without an explicit conversion "bool(flags & Flag)" or equivalent expression like "((flags & Flag) != 0)". And let's not forget about the friend, ==. I'v…

> "(a && b) || (!a && !b)"

It is XNOR, not XOR (no pun intended)

Boolean algebra laws excellently help if there are many input aN. I used to use it to simplify legacy ruby codes written by c-style programmer (you can imagine how the conditions look like)

Re: The Three Ways of XOR

#23

Post by makecheck »

The last statement in the article is technically a hardware decision (the article says: “As an extra treat, XOR can be considered an imparity function. When its input has an even number of zeros, the output is zero. Otherwise it is one.”).

While 2-input XOR behaves as “one or the other but not both”, a many-input gate is generally implemented by chaining other XORs and the chaining causes even/odd parity instead of a “must be only one” behavior [1].

[1] https://en.wikipedia.org/wiki/XOR_gate

Re: The Three Ways of XOR

#24

Post by gumby »

FabHK wrote: post #6

Lovely article, in particular the small but deep excursion into AI history and the AI winter after the publication of Minsky/Papert's "Perceptrons" (though it was 70's, not 80's). Wonder when the current AI summer will come to an end...

I posted this on his site but it needed to be approved. Also, there's actually a comment in the book (I just borrowed my gf's copy) in which they speculate that multilayer networks could be built, but since they only computers they had were .15 MIPS KA-10s (and all the figures in the book were hand drawn) they didn't pursue it.

My guess is it's still early days on the AI boom.

My comment on AI Winter:

Minor correction: Marvin and Seymour's Perceptrons book was published around 1969 and nuked neural nets around there. AI winter set in in the 80s as expert systems and similar crude symbolic systems proved not to be scalable (I was at that AAAI in 1984 and remember that panel well).

Moore's law rescued NNs and is about to rescue symbolic AI as well.

Re: The Three Ways of XOR

#26

Post by im3w1l »

ambrop7 wrote: post #2

> most programming languages don’t have an explicit “logical operator” for it I guess the author never taught of != . The only thing to be careful with is that it doesn't implicitly convert arguments to boolean, so expressions like " != (flags & Flag)" will go wrong without an explicit conversion "bool(flags & Flag)" or equivalent expression like "((flags & Flag) != 0)". And let's not forget about the friend, ==. I'v…

If you only want to convert the second argument you can use the ==! operator ;)

Re: The Three Ways of XOR

#27

Post by andreareina »

ambrop7 wrote: post #2

> most programming languages don’t have an explicit “logical operator” for it I guess the author never taught of != . The only thing to be careful with is that it doesn't implicitly convert arguments to boolean, so expressions like " != (flags & Flag)" will go wrong without an explicit conversion "bool(flags & Flag)" or equivalent expression like "((flags & Flag) != 0)". And let's not forget about the friend, ==. I'v…

!!a != !!b also works, but that's unwieldy.

I think maybe part of the reason is that usually you're also doing something with the value of the lhs or rhs, so you end up having to separate the cases anyway:

    if (a && !b) { frob(a); }
    else if (b && !a) { twiddle(b); }
    else { panic(); }

Re: The Three Ways of XOR

#28

Post by wz1000 »

FabHK wrote: post #6

Lovely article, in particular the small but deep excursion into AI history and the AI winter after the publication of Minsky/Papert's "Perceptrons" (though it was 70's, not 80's). Wonder when the current AI summer will come to an end...

> Wonder when the current AI summer will come to an end...

Are we really closer to AI in a significant way today? Chomsky makes an interesting argument to the contrary. He points out that any physical system, say the motion of falling bodies, can be closely modeled statistically given enough data points. However, this modeling gives us very little insight into why the system behaves in that manner, i.e. gravity.

Of course, this presumes that the human brain isn't just an advanced statistical model trained by billions of years of evolution.

Re: The Three Ways of XOR

#29

Post by SonOfLilit »

makecheck wrote: post #23

The last statement in the article is technically a hardware decision (the article says: “As an extra treat, XOR can be considered an imparity function. When its input has an even number of zeros, the output is zero. Otherwise it is one.”). While 2-input XOR behaves as “one or the other but not both”, a many-input gate is generally implemented by chaining other XORs and the chaining causes even/odd parity instead of a…

It's not "just an implementation decision"[1], it's a reasonable mathematical definition: for a binary operator OP, we define it's n-parameter version whenever a OP (b OP c) == (a OP b) op c, which is true for XOR but not e.g. for XNOR (F == F) == T is F, but F == (F == T) is T.

[1] and sorry if I'm falling victim to the difficulty of interpreting tone on the internet

Re: The Three Ways of XOR

#30

Post by johncolanduoni »

blurbleblurble wrote: post #21
knappa wrote: post #20

Earlier quoted context omitted.

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).
Post reply on HN