Побитовая XOR рациональных чисел

19

Вступление

Каждое рациональное число от 0 до 1 может быть представлено как конечная периодическая последовательность битов. Например, двоичное представление 11/40

0.010 0011 0011 0011 ...

где 0011часть повторяется бесконечно. Один из способов найти это представление заключается в следующем. Начните с r = 11/40 , затем несколько раз удвойте его и возьмите дробную часть, записывая, когда она становится выше 1. Когда значение r повторяется, вы знаете, что вы вошли в цикл.

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.

Чтобы вернуться из двоичной строки обратно в 11/40, вы можете использовать формулу

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

где prefix- начальная часть 010, suffixповторяющаяся часть 0011, и intпреобразующая двоичную строку в целое число.

Имея два таких представления, мы можем выполнить над ними побитовую операцию XOR. Результирующая последовательность также будет периодической, поэтому она представляет собой рациональное число.

Для некоторых рациональных чисел существует два двоичных представления.

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

Выбор между ними может повлиять на результат побитового XOR. В этих случаях мы используем первое представление, которое имеет бесконечно много нулей.

Задание

Ваши входные данные представляют собой два рациональных числа в полуоткрытом интервале [0,1). Ваш вывод должен быть результатом побитовой операции XOR, примененной к входам, выраженной как рациональное число. Обратите внимание, что выход может быть 1, даже если ни один из входов не является.

Точные форматы ввода и вывода являются гибкими, но каждое рациональное число должно быть представлено двумя целыми числами, числителем и знаменателем (за исключением 0 и 1, которые могут быть представлены как 0и 1при желании). Вы можете предположить, что входные данные выражены в самых низких терминах. Выходные данные должны быть выражены в самых низких условиях. Встроенный рациональный тип чисел является приемлемым форматом, если он удовлетворяет этим ограничениям. Вы можете игнорировать любые ограничения на целые числа, наложенные вашим языком, но ваш алгоритм теоретически должен работать для всех рациональных чисел.

Побеждает самое низкое число байтов. Применяются стандартные правила .

пример

Рассмотрим входы 11/40 и 3/7. Мы пишем их представления друг над другом, разграничивая повторяющиеся части трубками |. Затем мы извлекаем повторяющиеся части равной длины и применяем битовую XOR к ним и к частям перед ними.

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

Результирующее рациональное число равно 89/520.

Контрольные примеры

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
источник
Какой максимальный срок мы должны поддерживать?
Нил
@Neil Что заставляет вас думать, что такой максимум существует?
orlp
3
Примечание. Некоторые числа имеют два двоичных разложения, а именно те числа, у которых конечный период имеет длину один. В приведенном выше определении задачи подразумевается, что мы должны выбрать представление, которое заканчивается000...в этих случаях (что также получается, если мы используем алгоритм сr). Например, в случае, если5/8, 1/3мы получаем,23/24потому что мы выбираем расширение0.101000...для5/8. Если мы выберем вместо,0.10011111...как5/8, результат после XOR становится19/24, так что это неправильно. Связано с Википедией: 0,999 ...
Джепп Стиг Нильсен
3
@JeppeStigNielsen Блин ... Это значит, что в отличие от обычного XOR (a ^ b) ^ b == aне держится. Например (19/24 ^ 1/3) ^ 1/3 != 19/24. Это заставило меня потерять немного волнения по этому поводу :(
orlp

Ответы:

3

Python 3, 193 164 байта

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

Принимает ввод как fractions.Fractionтип Python 3 , а также выводит его.

Интересный факт (вы можете легко показать это с помощью генерирующих функций), если вы перейдете (a<.5)^(b<.5)к ((a>=.5)and(b>=.5))описанному выше, вы получите двоичное И между двумя рациональными числами. Назови это nd(a, b). Тогда у нас есть a + b - 2*nd(a, b) = x(a, b)!

orlp
источник
Действительно, моя ошибка. Извиняюсь! (обратите внимание, что ссылка на tio, включенная в ответ, была бы отличной)
Mr. Xcoder
1

JavaScript, 141 байт

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

Не будет работать для последнего контрольного примера (целочисленное переполнение). Введите 4 числа для p/q xor r/s, выведите массив с двумя числами. Для теста 0, 0, вы должны ввести 0, 1, 0, 1.

Как:

(Все числа, описанные здесь, в двоичном виде.)

  1. найти наименьшее число b, которое b = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s);
  2. Пусть x = p * b / q, y = r * b / q; Преобразование p / q, r / sк x / bи y / b;
  3. Пусть o = 10 ^ (p - q) - 1; разделение x, yчтобы [x % o, x / o], [y % o, y / o]; получить xor для каждой части [x % o xor y % o, x / o xor y / o]и присоединиться к (x % o xor y % o) + (x / o xor y / o) * o; Пожертвуйте это как a;
  4. Если a = 0ответ 0(или 0 / 1); Иначе пусть u = gcd(a, b); ответ (a/u)и (b/u).

ТТГ
источник