Основание −1+i: две координаты в одной строке

Если выводишь координаты частного при делении на −1+i и читаешь запись 1100 обратно, переходи к «Теперь сам».

Как думаешь, могут ли четыре бита обозначать точку плоскости

У основания −2 знак получался из чередования весов. Заменим основание на пару (−1,1). При умножении на неё направление веса меняется: первые степени равны 1, −1+i, −2i, 2+2i, −4. Теперь сумма выбранных весов может иметь ненулевую вторую координату, хотя цифры по-прежнему только 0 и 1.

Попробуй прочитать 1100. Это β³+β²=(2+2i)−2i=2. Другой короткий пример: 11=β+1=i. Значит строка может обозначать не только привычное целое число, но и точку, у которой первая координата нулевая, а вторая равна единице. Чтобы не путать число 11 с записью 11 в этом формате, всегда называй основание.

На что это похоже

У каждого разряда есть стрелка на клетчатой плоскости. Единица добавляет эту стрелку, ноль пропускает. Разряд левее получается из предыдущего поворотом и изменением длины: умножение на −1+i поворачивает на 135 градусов и увеличивает длину в √2 раза. Несколько выбранных стрелок складываются покоординатно.

Для вычислений не требуется геометрическая библиотека. Достаточно хранить две целые координаты. Именно это делает программа ниже: никаких приближённых комплексных чисел и ошибок округления. Геометрия помогает представить веса, а арифметика пар задаёт точное правило.

Механизм: что означает умножение комплексных пар

Запись a+bi означает пару (a,b). При сложении складываем координаты. При умножении раскрываем скобки и заменяем i² на −1: (a+bi)(c+di)=(ac−bd)+(ad+bc)i. В частности, умножение на −1+i переводит (a,b) в (−a−b,a−b). Это даёт обратное чтение строки по Горнеру.

Такие числа с целыми a,b называют гауссовыми целыми. Хотим выбрать цифру r из {0,1}, чтобы a+bi=(qₐ+qᵦi)(−1+i)+r. Приравняем координаты: a=−qₐ−qᵦ+r, b=qₐ−qᵦ. Сложение и вычитание уравнений дают qₐ=(b−a+r)/2, qᵦ=(r−a−b)/2.

Оба частных целые, если r имеет ту же чётность, что и a+b. При одинаковой чётности координат выбираем 0, при разной - 1. Чётность a−b совпадает с чётностью a+b, потому что они отличаются на 2b. Значит одна выбранная цифра одновременно делает оба числителя чётными.

Правило

Для β=−1+i и цифр 0,1 выбирай r=(a+b)%2, затем одновременно заменяй координаты на ((b−a+r)//2,(r−a−b)//2). Остатки идут от младшего разряда к старшему. Чтение цифры d слева направо: (a,b)←(−a−b+d,a−b). Ноль записывается как 0.

Обе новые координаты вычисляются из прежних. В Python правая часть присваивания паре сначала вычисляется целиком; если писать два отдельных присваивания, второе может случайно использовать уже изменённое a. Это испортит равенство исходного числа и восстановленной записи.

Разбор: число 2 и пара 2+3i

Для (2,0) первая цифра 0, следующее частное (−1,−1). Его цифра тоже 0, частное (0,1). Потом цифра 1 и частное (1,0), ещё цифра 1 и нулевая пара. Остатки 0,0,1,1 дают запись 1100, которую уже проверили через степени β.

Для (2,3) сумма координат нечётна: r=1. Новая пара равна (1,−2). Её цифра тоже 1, затем получается (−1,1), оттуда при цифре 0 переходим в (1,0), а последняя цифра 1 завершает процесс. Запись 1011 означает β³+β+1=(2+2i)+(−1+i)+1=2+3i.

def zapis(a, b):
    if a == b == 0:
        return "0"
    digits = []
    while a or b:
        r = (a + b) % 2
        digits.append(str(r))
        a, b = (b - a + r) // 2, (r - a - b) // 2
    return "".join(reversed(digits))


def znachenie(s):
    a, b = 0, 0
    for c in s:
        a, b = -a - b + int(c), a - b
    return a, b


for a, b in [(2, 0), (0, 1), (2, 3), (-1, -1)]:
    s = zapis(a, b)
    print((a, b), s, znachenie(s))
count = 0
for a in range(-20, 21):
    for b in range(-20, 21):
        assert znachenie(zapis(a, b)) == (a, b)
        count += 1
print("проверены пары:", count)

(2, 0) 1100 (2, 0)
(0, 1) 11 (0, 1)
(2, 3) 1011 (2, 3)
(-1, -1) 110 (-1, -1)
проверены пары: 1681

В выводе показаны исходная пара, строка цифр и результат обратного чтения. (0,1) означает i; это не номер бита и не диапазон. Перебор охватывает квадрат из 41·41=1681 пар. Он проверяет программу на этом квадрате, а не сам по себе доказывает утверждение для любых гауссовых целых.

Разбор: почему выбор цифры единственен и цикл конечен

Младшая цифра определена чётностью, после её удаления частное определено двумя формулами. Значит две разные конечные записи без ведущих нулей не могут обозначать одну пару: первая различающаяся младшая цифра уже противоречила бы чётности текущих координат.

Умножение на β увеличивает длину в √2 раза, поэтому деление её уменьшает. Однако перед делением мы иногда вычитаем 1; одной этой фразы для завершения мало. Точнее, длина нового частного не больше (√(a²+b²)+1)/√2. Если a²+b²≥6, она строго меньше прежней. Когда квадрат длины не больше 5, остаётся всего 21 пара. Формулы не выводят её за этот набор; прямой конечный разбор показывает, что каждая доходит до нуля максимум за восемь шагов. Это малые исключения к строгому уменьшению, а не произвольный предел длины цикла.

Так мы отделили три утверждения: допустимость каждой следующей цифры, единственность конечной записи и завершение процесса. Наличие правильного остатка на одном шаге ещё не доказывает последнее. Такое разделение полезно и при анализе более привычных числовых алгоритмов.

Что ломается без этого

Для координат берут тип с плавающей точкой и затем проверяют чётность приближённых чисел. В этом нет необходимости: все числители делятся на 2 точно. Или пытаются разделить отдельно действительную и мнимую части на −1 и на 1. Комплексное умножение смешивает координаты, поэтому правильное частное выводится из общей пары уравнений.

Основание и алфавит цифр нужно указывать вместе. Для −1−i та же строка даёт сопряжённое число: действительная часть сохраняется, мнимая меняет знак. В основании 2i с цифрами 0,1,2,3 даже для некоторых целых пар нужны позиции после точки. Например, 10.2 означает 2i+2/(2i)=i. Правило «целая пара - значит без дробных позиций» не переносится на любое комплексное основание.

Разбор: группировка цифр меняет основание

В основании −2 сгруппируем соседние биты в пары. Младший бит пары имеет вес 1, старший −2, поэтому значения пар 00,01,10,11 равны 0,1,−2,−1. Следующая пара весит в (-2)²=4 раза больше. Получилась система по основанию 4 с цифрами −2,−1,0,1. Например, 11010 разбивается как 1|10|10 и означает 1·4²+(−2)·4+(−2)=6. Отрицательные цифры здесь появились из группировки, а не из отдельного знака всего числа.

У основания β=−1+i пары тоже можно сгруппировать: новое основание равно β²=−2i, значения пар 00,01,10,11 равны 0,1,−1+i,i. Так, 1100 превращается в две цифры (i,0) по основанию −2i: i·(−2i)=2. Нужно менять и основание, и алфавит цифр вместе; обычные цифры 0,1,2,3 дали бы уже другую систему.

Замена β на γ=1+i меняет и конечность. Для числа i единственная допустимая младшая цифра по чётности равна 1, а частное снова равно i: i=1+(1+i)·i. Значит процесс повторяется и никогда не достигает нуля. Конечной записи i цифрами 0,1 в таком основании нет. Символические записи с бесконечными хвостами слева требуют дополнительной договорённости о переносах; они не являются обычной сходящейся суммой комплексных степеней, чьи модули растут. Основание 1−i даёт сопряжённую ситуацию. Поэтому доказательство завершения для −1+i нельзя переносить на любое основание того же модуля.

Зачем это в работе

Это пример проектирования представления: одной строкой можно закодировать объект с двумя координатами. Но сложение двух единиц уже даёт 1100, а не простой перенос в соседний разряд. Практическая реализация обычно хранит координаты отдельными целыми. Необычная система помогает понять причину такого выбора: компактность описания и простота операций - разные требования к формату.

Теперь сам

Прочитай 110 по основанию −1+i. Затем найди первую цифру и следующее частное для пары (3,2). Какая запись получится у той же строки 110 в основании −1−i?