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