Einführung

Jede rationale Zahl zwischen 0 und 1 kann als eine eventuell periodische Folge von Bits dargestellt werden. Zum Beispiel ist die binäre Darstellung von 11/40

0.010 0011 0011 0011 ...

wo der 0011Teil auf unbestimmte Zeit wiederholt. Eine Möglichkeit, diese Darstellung zu finden, ist die folgende. Beginnen Sie mit r = 11/40 , verdoppeln Sie es dann wiederholt und nehmen Sie den Bruchteil auf, wobei Sie aufzeichnen, wenn er über 1 liegt. Wenn sich der Wert von r wiederholt, wissen Sie, dass Sie in eine Schleife eingetreten sind.

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.

Um von der Binärzeichenfolge zurück zu 11/40 zu gelangen, können Sie die Formel verwenden

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

wo prefixist der Anfangsteil 010, suffixder sich wiederholenden Teil 0011, und intwandelt eine binäre Zeichenfolge ganze Zahl ist .

Wenn zwei solche Darstellungen gegeben sind, können wir die bitweise XOR-Operation für sie ausführen. Die resultierende Sequenz wird ebenfalls periodisch sein, sodass sie eine rationale Zahl darstellt.

Für einige rationale Zahlen gibt es zwei binäre Darstellungen.

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

Die Wahl zwischen ihnen kann das Ergebnis des bitweisen XOR beeinflussen. In diesen Fällen verwenden wir die frühere Darstellung, die unendlich viele Nullen hat.

Die Aufgabe

Ihre Eingaben sind zwei rationale Zahlen im halboffenen Intervall [0,1). Ihre Ausgabe soll das Ergebnis der bitweisen XOR-Operation sein, die auf die Eingaben angewendet wird, ausgedrückt als rationale Zahl. Beachten Sie, dass der Ausgang 1 sein kann, obwohl keiner der Eingänge 1 ist.

Die genauen Formate von Eingangs- und Ausgangs sind flexibel, aber jede rationale Zahl sollte von zwei ganzen Zahlen, Zähler und Nenner dargestellt werden (mit Ausnahme von 0 und 1, die als dargestellt werden kann , 0und , 1wenn gewünscht). Sie können davon ausgehen, dass die Eingaben in niedrigsten Ausdrücken ausgedrückt werden. Die Ausgabe muss in niedrigsten Ausdrücken ausgedrückt werden. Ein eingebauter Typ mit rationalen Zahlen ist ein akzeptables Format, sofern diese Einschränkungen erfüllt sind. Sie können alle durch Ihre Sprache auferlegten Grenzen für Ganzzahlen ignorieren, aber Ihr Algorithmus sollte theoretisch für alle rationalen Zahlen funktionieren.

Die niedrigste Byteanzahl gewinnt. Es gelten die Standardregeln für Code-Golf .

Beispiel

Betrachten Sie die Eingänge 11/40 und 3/7. Wir schreiben ihre Darstellungen übereinander und begrenzen die sich wiederholenden Teile durch Pfeifen |. Dann extrahieren wir sich wiederholende Teile gleicher Länge und wenden bitweise XOR auf sie und die Teile vor ihnen an.

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

Die resultierende rationale Zahl ist 89/520.

Testfälle

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

Nimmt Eingaben als Python 3- fractions.FractionTyp und gibt sie ebenfalls aus.

Unterhaltsame Tatsache (Sie können dies leicht mit Hilfe von Generierungsfunktionen zeigen): Wenn Sie (a<.5)^(b<.5)nach ((a>=.5)and(b>=.5))oben wechseln , erhalten Sie das binäre UND zwischen zwei rationalen Zahlen. Nennen Sie das nd(a, b). Dann haben wir a + b - 2*nd(a, b) = x(a, b)!

JavaScript, 141 Byte

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

Funktioniert nicht für den letzten Testfall (ganzzahliger Überlauf). Geben Sie 4 Zahlen für ein p/q xor r/s, geben Sie ein Array mit zwei Zahlen aus. Für den Testfall 0, 0sollten Sie eingeben 0, 1, 0, 1.

Wie:

(Alle hier beschriebenen Zahlen sind in binärer Form.)

1. finde die kleinste Zahl b, die b = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s);
2. Lassen Sie x = p * b / q, y = r * b / q; Konvertieren p / q, r / szu x / bund y / b;
3. Lassen o = 10 ^ (p - q) - 1; Split x, yzu [x % o, x / o], [y % o, y / o]; Holen Sie sich xor für jeden Teil [x % o xor y % o, x / o xor y / o]und verbinden Sie sich wieder mit (x % o xor y % o) + (x / o xor y / o) * o; Spende es als a;
4. Wenn a = 0, lautet die Antwort 0(oder 0 / 1); Sonst lass u = gcd(a, b); Die Antwort ist (a/u)und (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>