Bitwise XOR de números racionales

19

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 .

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
Zgarb
fuente
¿Cuál es el período máximo que debemos soportar?
Neil
@Neil ¿Qué te hace pensar que existe tal máximo?
orlp
3
Nota: Algunos números tienen dos expansiones binarias, es decir, aquellos números donde el período final tiene una duración de uno. Está implícito en la definición del problema anterior que debemos elegir la representación que termina000...en estos casos (que también es lo que obtenemos si usamos el algoritmor). Por ejemplo, en el caso5/8, 1/3que obtenemos23/24porque elegimos la expansión0.101000...para5/8. Si elegimos en su lugar0.10011111...como5/8, el resultado después de XOR se convierte19/24, entonces esto está mal. Relacionado con Wikipedia: 0.999 ...
Jeppe Stig Nielsen
3
@JeppeStigNielsen Maldición ... Esto significa que, a diferencia de XOR normal, (a ^ b) ^ b == ano se cumple. Por ej (19/24 ^ 1/3) ^ 1/3 != 19/24. Eso me hizo perder bastante entusiasmo por esto :(
orlp

Respuestas:

3

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

orlp
fuente
De hecho, mi error. Disculpas! (tenga en cuenta que un enlace a tio incluido en la respuesta sería genial)
Sr. Xcoder
1

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

tsh
fuente