| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1411.1 | The easy part... | CIVAGE::LYNN | Lynn Yarbrough @WNP DTN 427-5663 | Wed Apr 03 1991 18:00 | 21 |
| >(1) Using only XORL3, construct an instruction sequence for permuting 3
>registers in the following manner:
>
>Initially: R0 = x R1 = y R2 = z
>Finally: R0 = z R1 = x R3 = y
>
>(2) Find the minimum length of such a sequence, and PROVE that it's impossible
>to find a shorter sequence (for many, solving (1) will do most of the work of
>this proof).
(Let + = XOR)
1) r0+r1 -> r0 (x+y)
2) r1+r2 -> r1 (y+z)
3) r2+r0 -> r2 (x+y+z)
4) r2+r1 -> r2 (x)
5) r0+r2 -> r0 (y)
6) r1+r0 -> r1 (z)
(I think I did that backwards, but the other way is symmetric.)
Proof: it takes one operation per register to transfer its contents to
another register, and one operation to clear the other contents out of the
latter register, so two operations * three registers = 6.
|
| 1411.2 | proving the easy is hard | CLT::TRACE::GILBERT | Ownership Obligates | Thu Apr 04 1991 09:43 | 13 |
| Sorry, Lynn, but I don't buy that proof:
>Proof: it takes one operation per register to transfer its contents to
>another register, and one operation to clear the other contents out of the
latter register, so 2 operations per register * 3 registers = 6 operations.
(I tweaked the last line to make the physicists happy)
You say it takes one read per register and one write per register. Right.
But an operation (or instruction) can do *two* reads and a write. So the
`proof' only succeeds in showing that at least 3 operations are needed,
since fewer than 3 instructions cannot provide the 3 writes. The proof
*doesn't* show that 3 instructions are insufficient -- 3 instructions will
provide 6 reads and 3 writes (of the 3 and 3 that the proof says are needed).
|
| 1411.3 | | CLT::TRACE::GILBERT | Ownership Obligates | Fri Apr 05 1991 17:30 | 6 |
| Each register is in one of 2^3 states: 0,x,y,z,x+y,y+z,z+x,x+y+z.
Since there are three registers, there are (2^3)^3 = 2^9 = 512 states.
It's straight-forward (with a computer) to find a shortest path thru
these state transitions. This search shows there are two states `farthest'
from the initial state -- the two `rotations' of the input registers,
and that these are reached in 6 transitions.
|
| 1411.4 | XOR2 vs XOR3 | CADSYS::COOPER | Topher Cooper | Fri Apr 05 1991 18:57 | 14 |
| NOTE: Three register XOR instructions do not help in solving the
first problem.
Let the three registers all be of width w. The amount of information
in the three registers is thus 3w bits at the outset. Since we need
3w bits of information to remember the initial contents, and we have
("between" instructions) 3w bits of information, information can never
be redundantly stored. We must never throw away information. But an
instruction which places the XOR of two of the registers in a third,
erases the information previously held in the third register. Once
such an operation has been done, therefore, the original contents
cannot be recreated.
Topher
|