[net.math] REPOSTING: the Register Exchange problem

colonel@sunybcs.UUCP (George Sicherman) (10/04/83)

->	This seems to have gotten detoured, so I'm reposting it. --GLS
Part of CDC folklore is this no-core way to exchange the contents of
two X-registers without destroying any others:

	BX1    X1-X2
	BX2    X1-X2
	BX1    X1-X2

For those who don't know COMPASS, this translates as:  X1 <- X1 xor X2;
X2 <- X1 xor X2; X1 <- X1 xor X2.  The xor's are bitwise.

The problem is to generalize this.  Obviously N registers can be permuted
cyclically with 3 * (N-1) boolean xors.  (Example:  3 operations for
X1 <-> X2, then 3 for X2 <-> X3, 3 for X3 <-> X4, etc.)  The Register
Exchange problem is:  Can N registers be permuted cyclically in FEWER
THAN 3 * (N-1) operations?

The answer is NO for N < 6 -- found by exhaustion!  Except for this
mini-result, nobody has even made a dent in this problem.

				George Sicherman
				...seismo!rochester!rocksvax!colonel