Rosetta Code talk:Village Pump/CS Pages Wanted

From Rosetta Code
Revision as of 04:29, 21 July 2009 by MikeMol (talk | contribs) (moved Talk:Village Pump:Home/CS Pages Wanted to Rosetta Code talk:Village Pump/CS Pages Wanted: Move to project namespace)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Swapping in a ring

XOR swap is limited to the modulus of 2n. A more general swap is based on addition and subtraction, or equivalently on addition and negative inverse in the ring. This one works for any modulus. Here is an example in Ada. Given <lang ada> type N is mod 5; -- Ring of 0,1,2,3,4 X, Y : N; </lang> Swap X and Y: <lang ada> X := X + Y; Y := X - Y; X := X - Y; </lang> 5 is not a power of two, yet it still works. --Dmitry-kazakov 09:14, 17 March 2009 (UTC)

Isn't the reason that the XOR swap works because integers are stored as binary and XOR will do a bitwise operation? I think the XOR one is better because not all languages have modulus types, but pretty much all languages (if not all) represent integers in binary (or can at least do bitwise operations on them as if they were binary). Maybe I'm missing the problem. --Mwn3d 18:54, 17 March 2009 (UTC)
There is no problem, except that they are two different mathematical structures. XOR works on a lattice. +/- does on a ring. When talking about numbers +/- is more general than XOR. Or better to say that XOR is illegal, because it is not an integer operation. XOR cannot be defined on integers. It can only be defined on modular rings of 2n. It is a language design hole which allows XOR for int in C. But it is OK for unsigned, because unsigned is not an integer, it is modular 2n. Furthermore, in a strongly typed language you might have no access to the representation of a number as an array of bits in order to be able to use it as a lattice. The could be no such. Consider X and Y represented by packed chain codes or character strings. They might have different length so that you simply won't be able to XOR their memory patterns. Yet +/- will perfectly work. --Dmitry-kazakov 21:48, 24 March 2009 (UTC)
Maybe both could be shown in the same task of "Integer swap without a buffer". Bitwise XOR could be used where possible and modulus addition/subtraction (or whatever its formal name is..."ring addition"?) could be used for all examples. Do you think that's possible? --Mwn3d 21:53, 24 March 2009 (UTC)
I think it is a good idea. +/- works on true integers (e.g. BigNum) and on modular integers (ring). XOR works for anything that has a fixed size contiguous representation as an array of bits (lattice). --Dmitry-kazakov 14:22, 25 March 2009 (UTC)
Actually it doesn't need to be a ring (therre's no multiplication involved). It works as is on every additive abelian group. It is easily extended to non-abelian groups: Using generic names for the group operation (op(x,y) is x+y for additive groups, x*y for multiplicative groups) and inversion (inv(x) is -x for additive, x-1 for multiplicative groups), the operation is
x := op(x, y)
y := op(x, inv(y))
x := op(inv(y),x)
Note that bitwise XOR also forms a group with neutral element 0 (0 XOR x = x XOR 0 = x) and the inverse of an element being equal the element itself (x XOR x = 0). --Ce 15:46, 25 March 2009 (UTC)

Discussion in a VP talk page?

So we're talking. In the talk page. Of an article in a namespace whose entire purpose is to foster communication in its articles. Perhaps the material in this talk page ought to be moved to the page proper? --Short Circuit 02:09, 26 March 2009 (UTC)

Well, actually the article doesn't really contain talk content. So maybe the right solution would be to move it from the village pump into the Rosetta Code namespace. --Ce 08:39, 27 April 2009 (UTC)
Actually, the Village Pump was intended to be its own namespace. I haven't taken the time to get MediaWiki to recognize that, though... --Short Circuit 10:55, 27 April 2009 (UTC)
Well, you misunderstood my point: The VP is, as you said, dedicated to communicating. But the article isn't really a communication page, therefore I think it's not correctly located in the VP, but should be in the RP namespace instead. That would not change if VP were a "real" namespace (indeed, I didn't yet even notice that it isn't) --Ce 12:08, 27 April 2009 (UTC)
The VP serves as a sort of communal blog; Calls for content (what the request a task page was supposed to be for, but things that go there tend to get ignored) don't seem to be inappropriate, in that sense. I need to look at replacing the "Request a task" function with a script page that feeds into a bot that will do something like post into a VP page. That might help clarify things a bit. --Short Circuit 16:55, 27 April 2009 (UTC)