Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site sunybcs.UUCP
Path: utzoo!linus!philabs!seismo!rochester!rocksvax!sunybcs!colonel
From: colonel@sunybcs.UUCP (George Sicherman)
Newsgroups: net.math
Subject: REPOSTING: the Register Exchange problem
Message-ID: <491@sunybcs.UUCP>
Date: Tue, 4-Oct-83 16:29:31 EDT
Article-I.D.: sunybcs.491
Posted: Tue Oct  4 16:29:31 1983
Date-Received: Sun, 9-Oct-83 14:05:08 EDT
Organization: SUNY/Buffalo Computer Science
Lines: 22

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