(2007-06-02) Extending bitwise addition to ordinary rational numbers.
We may investigate what happens when bitwise (exclusive-or) addition isapplied to thebinary expansions of ordinaryfractions. (Those areultimately periodic.)
Adding bitwise two periodic expansionsof periods p and q yields an expansion whose period divides thelowest common multiple (LCM) of p and q.
The nonzero fractions whose denominator isa power of 2, havetwobinary expansions (one ending with infinitely many zeros, the other endingwith infinitely many ones). The issue is resolved by introducing the binary antizero0 :
0 = ....111111111111111111.111111111111111111...
Note that if we add (in the ordinary sense) any nonzero number to0,we obtain that same number, represented either by its unique binaryexpansion or by one of two equivalent ones, (Indeed, adding0 in the ordinary way lets you switch fromone such representation to the other.) With ordinary arithmetic, there's no difference (literally!) between 0 and0 or between ½ and [ 0+½ ]. With Nim-arithmetic, on the other hand,0 cannot be eliminatedexcept with the use of a unary minus (there's no need for a binary minus operator, since addition and subtractionare the same operation). The relation to remember is:
x + [-x] = 0 = -0
So, the antizero 0 may also be called "-0" (minus zero).
Nim-addition endows thebinary expansions with the structureof a group (each expansion is its own opposite). We call such a binary expansion a nimber. One or twonimbers areassociated with each number.
Nimbers form an Abelian group under Nim-addition. The subgroups correspond to fractions with a binary period thatdivides a given n. Those are fractions whose denominators are divisorsof 2n-1. They are of the form [x+y/(2n-1)] where y is an integer from 0 to 2n-1. (both extremes being excluded if we rule out numbers whose denominatorsare powers of 2). The structure is thus homomorphic to a simple cartesianproduct of two groups: The integernimbers on one hand(to which x belongs) and, on the other hand, the finite group of 2n integernimbers to which y belongs.
' Nim-addition generalized to positive fractions in UBASIC:'fnSim(X,Y)local D,N,Z,SS=1:while or{even(den(X)),even(den(Y))}:X*=2:Y*=2:S*=2:wend'Both denominators are now odd. Divisor S is a power of 2.D=lcm(den(X),den(Y))if D>1 then Z=2:N=1:while Z<>1:inc N:Z=(Z+Z)@D:wend:D=2^N-1N=floor(X):X=X-NZ=floor(Y):Y=Y-ZZ=bitxor(N,Z)+bitxor(num(X)*D\den(X),num(Y)*D\den(Y))//Dreturn(Z//S)
Denominator
BinaryPeriod
Mersenne Multiple
1
1
1
3
2
3
5
4
15
7
3
7
9
6
63
11
10
1023
13
12
4095
15
4
15
17
8
255
19
18
262143
21
6
63
23
11
2047
25
20
1048575
27
18
262143
29
28
268435455
31
5
31
33
10
1023
35
12
4095
37
36
68719476735
39
12
4095
41
20
1048575
43
14
16383
45
12
4095
47
23
8388607
49
21
2097151
51
8
255
53
52
4503599627370495
55
20
1048575
57
18
262143
59
58
288230376151711743
61
60
1152921504606846975
63
6
63
65
12
4095
67
66
73786976294838206463
69
22
4194303
71
35
34359738367
73
9
511
75
20
1048575
77
30
1073741823
79
39
549755813887
81
54
18014398509481983
83
82
4835703278458516698824703
85
8
255
87
28
268435455
89
11
2047
91
12
4095
93
10
1023
95
36
68719476735
97
48
281474976710655
99
30
1073741823
101
100
1267650600228229401496703205375
103
51
2251799813685247
105
12
4095
107
106
81129638414606681695789005144063
109
36
68719476735
111
36
68719476735
113
28
268435455
Recall that along primeto some base of numeration is aprime p whose inverse 1/p has period p-1 in that base. In binary, the long primes are:
By Fermat's little theorem, the binary period of a prime p divides p-1. Composite numbers for which this is true are the (rare) pseudoprime to base 2. The smallest of these is 341 = 11×13, whose binary period is 10:
All we have to do is define the product of two 2-powers. Among integers, this is done by specifying that theproduct of a Fermat 2-power by any lesser integer is equal to their ordinary product.
Let's introduce [½] into the picture. The product of ½ by any integer can't bean integer (or else multiplying the result by the inverseof that integer would yield an integer instead of ½ as it should). More generally, [½] cannot be the root of any quadratic polynomial with integer coefficients (the integernimbers are quadratically closed).
