Introducción

Cada número racional entre 0 y 1 puede representarse como una secuencia periódica de bits. Por ejemplo, la representación binaria de 11/40 es

0.010 0011 0011 0011 ...

donde la 0011parte se repite indefinidamente. Una forma de encontrar esta representación es la siguiente. Comience con r = 11/40 , luego duplíquelo repetidamente y tome la parte fraccionaria, registrando cuando sube por encima de 1. Cuando el valor de r se repite, sabe que ha entrado en un ciclo.

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.

Para volver de la cadena binaria a 11/40, puede usar la fórmula

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

donde prefixes la parte inicial 010, suffixes la parte que se repite 0011y intconvierte una cadena binaria en un entero.

Dadas dos de estas representaciones, podemos realizar la operación XOR bit a bit en ellas. La secuencia resultante también será periódica, por lo que representa un número racional.

Para algunos números racionales, hay dos representaciones binarias.

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

La elección entre ellos puede afectar el resultado del XOR bit a bit. En estos casos, usamos la representación anterior, que tiene infinitos ceros.

La tarea

Sus entradas son dos números racionales en el intervalo medio abierto [0,1). Su salida será el resultado de la operación XOR bit a bit aplicada a las entradas, expresada como un número racional. Tenga en cuenta que la salida puede ser 1, aunque ninguna de las entradas lo sea.

Los formatos exactos de entrada y salida son flexibles, pero cada número racional debe estar representado por dos enteros, el numerador y el denominador (con la excepción de 0 y 1, que pueden representarse como 0y 1si se desea). Puede suponer que las entradas se expresan en términos más bajos. La salida debe expresarse en términos más bajos. Un tipo de número racional incorporado es un formato aceptable, siempre que cumpla con estas restricciones. Puede ignorar cualquier límite en los enteros impuesto por su idioma, pero su algoritmo debería funcionar teóricamente para todos los números racionales.

El conteo de bytes más bajo gana. Aplican reglas estándar de código de golf .

Ejemplo

Considere las entradas 11/40 y 3/7. Escribimos sus representaciones una encima de la otra, delimitando las partes repetidas por tuberías |. Luego extraemos partes repetidas de igual longitud y aplicamos XOR bit a bit a ellas y a las partes anteriores.

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 ...

El número racional resultante es 89/520.

Casos de prueba

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

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

Toma la entrada como el fractions.Fractiontipo de Python 3 y también la genera.

Dato curioso (puede mostrar esto fácilmente usando funciones generadoras), si cambia (a<.5)^(b<.5)a lo ((a>=.5)and(b>=.5))anterior, obtiene el AND binario entre dos números racionales. Llama a esto nd(a, b). Entonces tenemos a + b - 2*nd(a, b) = x(a, b)!

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))

No funcionará para el último caso de prueba (desbordamiento de enteros). Ingrese 4 números para p/q xor r/s, envíe una matriz con dos números. Para el caso de prueba 0, 0, debe ingresar 0, 1, 0, 1.

Cómo:

(Todos los números descritos aquí están en forma binaria).

1. encuentra el número más pequeño b, que b = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s);
2. Deje x = p * b / q, y = r * b / q; Convertir p / q, r / sa x / by y / b;
3. Dejar o = 10 ^ (p - q) - 1; división x, ya [x % o, x / o], [y % o, y / o]; obtener xor para cada parte [x % o xor y % o, x / o xor y / o]y unirse de nuevo a (x % o xor y % o) + (x / o xor y / o) * o; Done como a;
4. Si a = 0, la respuesta es 0(o 0 / 1); De lo contrario dejar u = gcd(a, b); La respuesta es (a/u)y (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>