To understand this page, you'll need to know about binary numbers, fractions and
the bitwise logic function XOR. If you don't know about any of those, this page
probably isn't for you...:)
When considering bitwise operations such as XOR, it is almost always assumed that the
two operands and the result will all be integers. No consideration is therefore given
to what the result of the calculation might be if either or both of the operands is
non-integral; How should the bits after the binary point be handled?
Fortunately, the process for bitwise XORing two values extends naturally to those
extra bits. e.g.:
34d XOR 23d
= 100010b XOR 010111b
= 110101b
= 53d
...and:
34.125d XOR 23.375d
= 100010.001b XOR 010111.011b
= 110101.010b
= 53.25d
Table 1 then, tabulates the reciprocal of the XOR of reciprocals of the row and column.
e.g.:
Table_1(8, 4)
= 1/(1/8 XOR 1/4)
= 1/(1/1000b XOR 1/100b)
= 1/(0.001b XOR 0.01b)
= 1/(0.011b)
= 1/(3/8d)
= 8/3
... which is indeed the value in Table 1, row 8, column 4.
So far our examples have deliberately avoided the awkward situation that arises with
non-terminating binary fractions. Again the XOR rules extend naturally, but we now
have to check that the (eventually) repeating pattern of the bits in each operand
combines fully with the other. N.B. Since it can be proved that the repeat cycle length
of a result is equal to the lowest common multiple of the repeat cycle lengths of the
operands, it can also be proved that all results will be rational when both operands are
rational. Here's a few examples:
Table_1(9, 10)
= 1/(1/9 XOR 1/10)
= 1/(1/1001b XOR 1/1010b)
= 1/(0.{000111}...b XOR 0.0{0011}...b)
-- cycle lengths of 6 and 4
= 1/(0.0{000010111101}...b)
-- cycle length = 12 = LCM(6,4)
= 1/(0.1b
* 000010111101b/(10b^1100b-1))
= 1/(0.5 * 189/(2^12-1))
-- 12, (1100b) is from the cycle length
= 1/(0.5 * 189/4095)
= 1/(189/8190)
= 1/(3/130)
= 130/3
Table_1(3, 12)
= 1/(1/3 XOR 1/12)
= 1/(1/11b XOR 1/1100b)
= 1/(0.{01}...b XOR 0.00{01}...b)
-- both cycle lengths are 2
= 1/(0.01{00}...b)
-- cycle length = 2 = LCM(2,2)
= 1/(0.01b)
-- repeating zeroes mean nothing and can be cancelled
= 1/(1/4d)
= 4
Table_1(6, 12)
= 1/(1/6 XOR 1/12)
= 1/(1/110b XOR 1/1100b)
= 1/(0.0{01}...b XOR 0.00{01}...b)
-- which is equivalent to...
= 1/(0.00{10}...b XOR 0.00{01}...b)
-- both cycle lengths are again 2
= 1/(0.00{11}...b)
-- cycle length = 2 = LCM(2,2)
= 1/(0.01{00}b)
-- repeating ones can be rounded up to a 1 and repeating zeroes
= 1/(0.01b)
-- ...and repeating zeroes mean nothing and can be cancelled
= 1/(1/4d)
= 4
Now, the XOR result of two integers holds to (among others) two rules:
- x XOR y = y XOR x
- x XOR (x XOR y) = y
Unfortunately the last two examples prove that when the operands are not integers
that the second rule must fail; Both return the same result, meaning that
(
1/12 XOR 1/4) should return
both 1/6 and
1/3 as the result. This is clearly impossible.
