: : C y r e k S o f t : :

 
* Home

* FAQ

* Tools

+ Games + GNU bc + Interesting + Stuff + Links
 
  1 2 3 4 5 6 7 8 9 10 11 12
1 - 2/3 3/4 4/5 5/6 6/7 7/8 8/9 9/10 10/11 11/12 12/13
2 2/3 - 6/5 4/3 10/7 3/2 14/9 8/5 18/11 5/3 22/13 12/7
3 3/4 6/5 - 12 5/2 2 9/4 24/11 7/2 10/3 31/8 4
4 4/5 4/3 12 - 20/9 12/5 28/11 8/3 36/13 20/7 44/15 3
5 5/6 10/7 5/2 20/9 - 10 65/6 40/3 65/12 6
1025
146
20/3
6 6/7 3/2 2 12/5 10 - 18 24 14/3 5 62/15 4
7 7/8 14/9 9/4 28/11 65/6 18 - 56 9/2
130
31
10923
2212
36/7
8 8/9 8/5 24/11 8/3 40/3 24 56 - 72/17 40/9 88/19 24/5
9 9/10 18/11 7/2 36/13 65/12 14/3 9/2 72/17 -
130
3
32767
1434
28
10 10/11 5/3 10/3 20/7 6 5
130
31
40/9
130
3
-
2050
119
20
11 11/12 22/13 31/8 44/15
1025
146
62/15
10923
2212
88/19
32767
1434
2050
119
- 124
12 12/13 12/7 4 3 20/3 4 36/7 24/5 28 20 124 -

Table 1. - (x-1 XOR y-1)-1

Explanation

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.

Repeating binary fractions

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:
  1. x XOR y = y XOR x
  2. 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.

Exercises

  1. Evaluate (x XOR y) for the following:
    1. x = 6, 12
    2. x = 123, 1234
    3. x = 365, 676
  2. Evaluate (x-1 XOR y-1)-1 for the following (three are in the above table but show working for all):
    1. x = 5, y = 6
    2. x = 6, y = 7
    3. x = 31, y = 33
    4. x = 3, y = 43
    5. x = 9, y = 11
  3. Examine and discuss the results of the function f(x) = ((2x-1)-1 XOR (2x+1)-1)-1 for positive integral x.
  4. Prove whether the pattern n/(n+1) in row and column continues indefinitely.
  5. Identify and discuss the problem causing the dichotomy with 3, 6, 12 and 4 described above. (Hint: 0.00{1}... = 0.01; or does it? Should it in the case of XOR?)

Notes

  • The floating point XOR function is implemented as xorf(x,y) for the GNU bc programming language in the logic.bc file from this website's GNU bc page.
  • The HTML for Table 1 was generated by another, Javascript containing, page whose inner HTML attribute was opened to pull the source directly. As a result, this page requires no Javascript at all! A version of that very generator page is available here.

 

 
This site should work with most browsers
though there are some advanced features
that will only work with more recent software
  that mail thing | web{}phodd.net