introduction

Chaque nombre rationnel entre 0 et 1 peut être représenté comme une séquence de bits éventuellement périodique. Par exemple, la représentation binaire de 11/40 est

0.010 0011 0011 0011 ...

où la 0011partie se répète indéfiniment. Une façon de trouver cette représentation est la suivante. Commencez par r = 11/40 , puis doublez-le à plusieurs reprises et prenez la partie fractionnaire, en enregistrant quand il va au-dessus de 1. Lorsque la valeur de r se répète, vous savez que vous avez entré une boucle.

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.

Pour revenir de la chaîne binaire à 11/40, vous pouvez utiliser la formule

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

où prefixest la partie initiale 010, suffixest la partie répétitive 0011et intconvertit une chaîne binaire en entier.

Étant donné deux de ces représentations, nous pouvons effectuer l'opération XOR au niveau du bit sur elles. La séquence résultante sera également périodique, elle représente donc un nombre rationnel.

Pour certains nombres rationnels, il existe deux représentations binaires.

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

Le choix entre eux peut affecter le résultat du XOR au niveau du bit. Dans ces cas, nous utilisons l'ancienne représentation, qui a une infinité de 0.

La tâche

Vos entrées sont deux nombres rationnels dans l'intervalle semi-ouvert [0,1). Votre sortie doit être le résultat de l'opération XOR au niveau du bit appliquée aux entrées, exprimée en nombre rationnel. Notez que la sortie peut être 1, même si aucune des entrées ne l'est.

Les formats exacts d'entrée et de sortie sont flexibles, mais chaque nombre rationnel doit être représenté par deux entiers, le numérateur et le dénominateur (à l'exception de 0 et 1, qui peuvent être représentés comme 0et 1si vous le souhaitez). Vous pouvez supposer que les entrées sont exprimées en termes les plus bas. La sortie doit être exprimée en termes les plus bas. Un type de nombre rationnel intégré est un format acceptable, tant qu'il satisfait à ces restrictions. Vous pouvez ignorer toutes les limites des entiers imposées par votre langage, mais votre algorithme devrait théoriquement fonctionner pour tous les nombres rationnels.

Le nombre d'octets le plus bas gagne. Les règles de code-golf standard s'appliquent.

Exemple

Considérez les entrées 11/40 et 3/7. Nous écrivons leurs représentations les unes au-dessus des autres, délimitant les parties répétitives par des tuyaux |. Ensuite, nous extrayons des parties répétitives de longueurs égales et leur appliquons un XOR au niveau du bit et les parties qui les précèdent.

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

Le nombre rationnel résultant est 89/520.

Cas de test

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 octets

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

Prend l'entrée comme le fractions.Fractiontype de Python 3 et la sort également.

Fait amusant (vous pouvez facilement le montrer en utilisant des fonctions de génération), si vous passez (a<.5)^(b<.5)à ((a>=.5)and(b>=.5))ci-dessus, vous obtenez le binaire ET entre deux nombres rationnels. Appelez ça nd(a, b). Alors nous avons a + b - 2*nd(a, b) = x(a, b)!

JavaScript, 141 octets

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

Ne fonctionnera pas pour le dernier cas de test (débordement d'entier). Entrez 4 nombres pour p/q xor r/s, sortez un tableau avec deux nombres. Pour testcase 0, 0, vous devez saisir 0, 1, 0, 1.

Comment:

(Tous les nombres décrits ici sont sous forme binaire.)

1. trouver le plus petit nombre b, qui b = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s);
2. Laissez x = p * b / q, y = r * b / q; Convertir p / q, r / sen x / bet y / b;
3. Soit o = 10 ^ (p - q) - 1; scission x, yà [x % o, x / o], [y % o, y / o]; obtenir xor pour chaque partie [x % o xor y % o, x / o xor y / o]et rejoindre à nouveau (x % o xor y % o) + (x / o xor y / o) * o; Donnez-le comme a;
4. Si a = 0, la réponse est 0(ou 0 / 1); Sinon, laissez u = gcd(a, b); la réponse est (a/u)et (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>