19
\$\begingroup\$

Introduction

Every rational number between 0 and 1 can be represented as an eventually periodic sequence of bits. For example, the binary representation of 11/40 is

0.010 0011 0011 0011 ...

where the 0011 part repeats indefinitely. One way of finding this representation is the following. Start with r = 11/40, then repeatedly double it and take the fractional part, recording when it goes above 1. When the value of r repeats, you know you have entered a loop.

1. r = 11/40
2. 2*r = 11/20 < 1   ->  next bit is 0, r = 11/20
3. 2*r = 11/10 >= 1  ->  next bit is 1, r = 2*r - 1 = 1/10
4. 2*r = 1/5 < 1     ->  next bit is 0, r = 1/5
5. 2*r = 2/5 < 1     ->  next bit is 0, r = 2/5
6. 2*r = 4/5 < 1     ->  next bit is 0, r = 4/5
7. 2*r = 8/5 >= 1    ->  next bit is 1, r = 2*r - 1 = 3/5
8. 2*r = 6/5 >= 1    ->  next bit is 1, r = 2*r - 1 = 1/5, same as in 4.
   The loop 5. -> 6. -> 7. -> 8. now repeats.

To get from the binary string back to 11/40, you can use the formula

(int(prefix) + int(suffix)/(2^len(suffix) - 1)) / 2^len(prefix)

where prefix is the initial part 010, suffix is the repeating part 0011, and int converts a binary string to integer.

Given two such representations, we can perform the bitwise XOR operation on them. The resulting sequence will also be periodic, so it represents a rational number.

For some rational numbers, there are two binary representations.

1/4 = 0.010000000...
    = 0.001111111...

The choice between them can affect the result of the bitwise XOR. In these cases, we use the former representation, which has infinitely many 0s.

The task

Your inputs are two rational numbers in the half-open interval [0,1). Your output shall be the result of the bitwise XOR operation applied to the inputs, expressed as a rational number. Note that the output can be 1, even though neither of the inputs are.

The exact formats of input and output are flexible, but each rational number should be represented by two integers, the numerator and denominator (with the exception of 0 and 1, which can be represented as 0 and 1 if desired). You can assume that the inputs are expressed in lowest terms. The output must be expressed in lowest terms. A built-in rational number type is an acceptable format, as long as it satisfies these restrictions. You can ignore any bounds on integers imposed by your language, but your algorithm should theoretically work for all rational numbers.

The lowest byte count wins. Standard rules apply.

Example

Consider the inputs 11/40 and 3/7. We write their representations one above the other, delimiting the repeating parts by pipes |. Then we extract repeating parts of equal lengths, and apply bitwise XOR to them and the parts before them.

11/40 = 0. 0 1 0|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 ...
3/7   = 0.|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|...
     -> 0. 0 0 1|0 1 0 1 1 1 1 0 1 0 0 0|0 1 0 1 1 1 1 0 1 0 0 0|0 1 0 ...

The resulting rational number is 89/520.

Test cases

0 0 -> 0
1/2 1/2 -> 0
1/2 1/4 -> 3/4
1/3 2/3 -> 1
1/2 3/4 -> 1/4
5/8 1/3 -> 23/24
1/3 1/5 -> 2/5
15/16 3/19 -> 257/304
15/16 257/304 -> 3/19
3/7 11/40 -> 89/520
5/32 17/24 -> 59/96
16/29 16/39 -> 621001733121535520/696556744961512799
\$\endgroup\$
  • \$\begingroup\$ What's the maximum period we need to support? \$\endgroup\$ – Neil Nov 14 '17 at 9:54
  • \$\begingroup\$ @Neil What makes you think that such a maximum exists? \$\endgroup\$ – orlp Nov 14 '17 at 10:06
  • 3
    \$\begingroup\$ Note: Some numbers have two binary expansions, namely those numbers where the eventual period has length one. It is implicit in the problem definition above that we must choose the representation that ends in 000... in this cases (which is also what we get if we use the algorithm with r). For example, in the case 5/8, 1/3 we get 23/24 because we choose the expansion 0.101000... for 5/8. If we choose instead 0.10011111... as 5/8, the result after XOR becomes 19/24, so this is wrong. Related to Wikipedia: 0.999... \$\endgroup\$ – Jeppe Stig Nielsen Nov 14 '17 at 15:14
  • 3
    \$\begingroup\$ @JeppeStigNielsen Damn... This means that unlike regular XOR (a ^ b) ^ b == a does not hold. E.g. (19/24 ^ 1/3) ^ 1/3 != 19/24. That made me lose quite a bit of excitement about this :( \$\endgroup\$ – orlp Nov 14 '17 at 16:01
  • 1
    \$\begingroup\$ See also What do bitwise operators look like in 3d? on Mathematics. \$\endgroup\$ – Ilmari Karonen Nov 14 '17 at 20:11
3
\$\begingroup\$

Python 3, 193 164 bytes

def x(a,b,z=0):
 l=[]
 while(a,b)not in l:l+=[(a,b)];z=2*z|(a<.5)^(b<.5);a=a*2%1;b=b*2%1
 p=l.index((a,b));P=len(l)-p
 return((z>>P)+z%2**P*a**0/~-2**(P or 1))/2**p

Takes input as Python 3's fractions.Fraction type, and outputs it as well.

Fun fact (you can easily show this using generating functions), if you change (a<.5)^(b<.5) to ((a>=.5)and(b>=.5)) above you get the binary AND between two rational numbers. Call this nd(a, b). Then we have a + b - 2*nd(a, b) = x(a, b)!

\$\endgroup\$
  • \$\begingroup\$ Indeed, my mistake. Apologies! (note that a link to tio included in the answer would be great) \$\endgroup\$ – Mr. Xcoder Nov 14 '17 at 13:53
1
\$\begingroup\$

JavaScript, 141 bytes

(p,q,r,s)=>(h=(v,u)=>v%u?h(u,v%u):[a/u,b/u])(b=(g=x=>x%q||x%s?g((x|x/2)+x%2):x)(1),a=(o=b/(b-(b&~-b)),x=p*b/q,y=r*b/s,(x%o^y%o)+(x/o^y/o)*o))

Wont work for last test case (integer overflow). Input 4 numbers for p/q xor r/s, output an array with two numbers. For testcase 0, 0, you should input 0, 1, 0, 1.

How:

(All numbers described here is in binary form.)

  1. find the smallest number b, which b = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s);
  2. Let x = p * b / q, y = r * b / q; Convert p / q, r / s to x / b and y / b;
  3. Let o = 10 ^ (p - q) - 1; split x, y to [x % o, x / o], [y % o, y / o]; get xor for each part [x % o xor y % o, x / o xor y / o], and join back to (x % o xor y % o) + (x / o xor y / o) * o; Donate it as a;
  4. If a = 0, the answer is 0 (or 0 / 1); Otherwise let u = gcd(a, b); the answer is (a/u) and (b/u).

f=

(p,q,r,s)=>(h=(v,u)=>u%v?h(u%v,v):[a/v,b/v])(b=(g=x=>x%q||x%s?g((x|x/2)+x%2):x)(1),a=(o=b/(b-(b&~-b)),x=p*b/q,y=r*b/s,(x%o^y%o)+(x/o^y/o)*o))
<div oninput="[v5.value,v6.value]=['?','?'];[v5.value,v6.value]=f(+v1.value,+v2.value,+v3.value,+v4.value)">
<input id=v1 />/<input id=v2 /> xor <input id=v3 />/<input id=v4 /> = <output id=v5></output> / <output id=v6></output>
<style>input{width:40px}</style>
</div>

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.