kodimatrix 23 мар 2023 в 16:44

Алгебра int о которой не говорят

Средний

10 мин

23K

Программирование*IT-стандарты*Математика*

FAQ

Да, тайтл кликбейтный, но тема алгебраических свойств integer'а и float'а, действительно, не часто освещается в литературе и интернетах, однако эти знания углубляют понимание реализации компьютерной арифметики и применимы на практике.

~~Толчком~~ Мотивацией к написанию статьи послужил кейс, продемонстрировавший свойство целого типа, которое легко упустить из виду, но на практике приводящее к неожиданному поведению. Это ни разу не новое открытие в computer science, и под капотом все довольно просто, но сохраним интригу. Подойдем к этому свойству через реальную задачу, затем посмотрим на целочисленную арифметику с точки зрения теории групп и разложим все по полочкам. Если вы используете язык программирования с ограниченными целыми числами, то статья может оказаться полезной.

Сайд эффект от прочтения статьи: появится навык доказательства утверждения 2+2=0.

Содержание

Случай из жизни
Абстрактная алгебра
int со сложением — группа или нет?
Так а что с -INT_MIN ?
Особенности реализаций int в языках программирования
Outro

Случай из жизни

Недавно столкнулся с проблемой при реализации простого шахматного AI. За модной аббревиатурой прячется классический алгоритм alpha-beta pruning. Заголовок статьи не анонсировал дебрей теории игр, поэтому здесь не будет о методе MinMax и парадигме Branch and bound, по этой теме на Хабре много отличный статей: Минимакс на примере игры в зайца и волков, Шахматы на C++ и др. Постараюсь предметно описать кэйс, но без лишний деталей.

В код ниже (источник) нет необходимости вчитываться. Нам важно отметить следующее: функция alphaBeta() имеет параметры alpha, beta и рекурсивно вызывает себя поменяв местами аргументы и их знаки -beta, -alpha.

 int alphaBeta( int alpha, int beta, int depthleft ) {  
    if( depthleft == 0 ) return quiesce( alpha, beta );  
    for ( all moves)  {  
       score = -alphaBeta( -beta, -alpha, depthleft - 1 ); // рекурсивный вызов
       if( score >= beta )  
          return beta;  
       if( score > alpha )  
          alpha = score;  
    }  
    return alpha;  
 }

Согласно теории, корневой вызов должен быть таким:

score = alphaBeta(-oo, +oo, depth);

В тот день мне посчастливилось писать код на машине с ограниченным объемом памяти, и мне показалось неплохой идеей вместо $+\infty$ и $-\infty$ использоватьINT_MAX иINT_MIN. Обычно так делать не стоит, но мне очень хотелось.

Да, этот алгоритм не работает. Разбираемся.

Очевидно, первый рекурсивный вызов происходит со следующими аргументами:

alphaBeta(-INT_MAX, -INT_MIN, depth - 1);

Посмотрим лог значений alpha и beta "внутри" этого вызова:

alpha = -2147483647
beta  = -2147483648

С alpha все хорошо. А вот у beta значение не поменяло знак! И это ломает алгоритм. Получается -INT_MIN равен -2147483648, то есть равен INT_MIN (онлайн пример). Конечно, в данном случае можно использовать другие аргументы для корневого вызова и все будет работать. Но как жить дальше? В начальной школе оператор арифметического отрицания работал не так как в этих ваших компьютерах.

Независимо от субъективной оценки степени очевидности проблемы не спешите закрывать вкладку, ибо этот кейс служит предлогом для более серьезного разговора: об абстрактной алгебре, ибо именно этот раздел занимается всеми этими вопросами ~~жизни, вселенной и~~ всего такого.

Абстрактная алгебра

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

Что это такое и зачем нужно

Абстрактная алгебра — чрезвычайно важный для науки раздел математики. Исследования в этой области происходят по следующей схеме:

Выбирается некоторая система аксиом для операции(ий) на множестве;
Находятся и доказываются свойства этой структуры.

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

Кажется, распространение свойств, работает не только на формальном, но и на интуитивном уровне. Имею ввиду, что когда вы получаете опыт работы с некоторым объектом соответствующим определенной алгебраической структуре, после этого уже на интуитивном уровне легко оперировать другими объектами (из совершенно других областей и приложений) обладающим теми же свойствами. Например, на первом курсе раскрытие скобок в выражениях, где суммируются векторы, не кажется сложным, потому что это работает так же, как для сложения вещественных чисел. Однако для первокурсника преобразования выражений с произведениями матриц непривычны из-за нового свойства некоммутативности.

Полезно знать, какой алгебраической структуре соответствует та штука, с которой вы работаете, чтобы понимать с какими свойствами имеешь дело. И этим вопросом в контексте int и float я задался где-то на младших курсах университета. То были темные времена: ChatGPT еще не существовало, а для гуглежа не хватало прямых рук. Не зная нужной литературы, ничего другого не оставалось как ~~о ужас~~ думать самому. На честный формальный подход не хватило запала, но, на вскидку я пришел к некоторым выводам, которые позже подтвердил преподаватель. С тех пор я жил с уверенностью, в частности, в то, что int по сложению образует группу. Спокойно жил пока не встретил alpha-beta pruning...

Давайте обсудим самую простую и, в некотором смысле, самую важную алгебраическую структуру.

Определение группы

Множество с бинарной операцией $(\mathrm{G}, *)$ называется группой если выполняются аксиомы:

замкнутости: $\forall a, b \in G ~~~ \exists c \in G\colon ~~~ a * b = c;$
ассоциативности: $\forall a, b, c\in G\colon ~~~ (a*b)*c = a*(b*c);$
существования нейтрального элемента: $\exists e \in G \quad \forall a \in G\colon ~~~ e*a=a*e=a;$
существования обратного элемента: $\forall a \in G \quad \exists a^{-1}\in G\colon ~~~ a*a^{-1}=a^{-1}*a=e.$

Формальное определение может показаться сложным, но на самом деле это не так страшно. Что бы почувствовать суть нужны примеры.

Примеры групп

Целые числа со сложением

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

Образуют группу.

Целые числа с умножением

замкнутость выполняется: произведение двух целых чисел является целым числом;
очевидно, ассоциативность выполняется;
существует нейтральный элемент: ;
для любого ненулевого элемента обратный: $\frac{1}{a}$ , то есть не для любого целого найдется обратный по умножению в множестве целых чисел.

Не образуют группу. А вот множество рациональных чисел без нуля с умножением образуют группу.

Сложение по модулю

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

Введем обозначения:

— операция сложения по модулю;
— обычное сложение целых чисел.

Результатом сложения по модулю $n \in \mathbb{Z}$ является остаток суммы при делении на , то есть:

$\forall a, b \in \mathbb{Z}_n: a +_n b := (a + b) \bmod n;$

где $\mathbb{Z}_n = \{0, 1, \ldots, n- 1\}$ .

Рассмотрим сложение целых чисел по модулю 4.
$\mathbb{Z}_4=\{0, 1, 2, 3\}$ .

Пример:

$2+_4 2= (2+2) \bmod 4 = 0$

Таблица сложения по модулю 4.:

Каждая из аксиом (кроме ассоциативности) наглядно демонстрируется таблицей сложения. Обобщим для произвольного :

замкнутость выполняется (по построению множества);
ассоциативность выполняется;
Доказательство
Вначале докажем вспомогательное утверждение для целых чисел:
$\forall x, y \in \mathbb{Z}, n \in \mathbb{Z^+}: \:(x + y) \bmod n = (x \bmod n + y \bmod n) \bmod n;$
Доказательство:
Целоеможно представить следующим образом:
$x=x_c + x_r\cdot n.$
Рассмотрим левую часть утверждение:
$\begin{align} (x + y) \bmod n =(x_c + y_c + n \cdot (x_r + y_r)) \bmod n = \\ = (x_c + y_c) \bmod n. \end{align}$
Рассмотрим правую часть утверждение:
$(x \bmod n + y \bmod n) \bmod n= (x_c + y_c) \bmod n.$
Пришли к тому, что левая и правая части тождественны, следовательно утверждение доказано. Если кто-то дочитал до этой строки, смеха ради напишите в комментариях: "Хорошо, что Галуа не видел этого доказательства ассоциативности".
Перейдем к доказательству ассоциативности:
$\begin{align} \forall a, b, c \in \mathbb{Z}_n: \: (a +_n b) +_n c &= ((a + b) \bmod n + c) \bmod n= \\ &= ((a + b) \bmod n + c \bmod n ) \bmod n \end{align}$
применим вспомогательное утверждение:
$\begin{align} ((a + b) \bmod n + c \bmod n ) \bmod n = ((a + b) + c) \bmod n = \\ = (a + (b + c)) \bmod n=(a + (b + c) \bmod n) \bmod n = \\ = a +_n (b +_n c); \end{align}$
что и следовало доказать.
существует нейтральный элемент: .
для любого ненулевого элемента существует обратный: $a^{-1} = n-a$ .

Образуют группу.

Эта группа встречается повсеместно, например: часы на циферблате — целые числа по модулю 12.

Другие примеры

Теперь вооружившись некоторыми знаниями алгебры вернемся к нашим ~~баранам~~ int'ам.

int со сложением — группа или нет?

Начнем с беззнаковых -битных целых со сложением. Имеет место переполнение (wrap around) и, конечно, это группа сложения по модулю , о которой мы говорили выше.

А что со знаковыми целыми?

Нужно вспомнить имплементацию и пазл сложится. Сегодня в компьютерах отрицательные целые числа представляются так называемым дополнительным кодом (two’s complement) (и это даже зафиксировано стандартом C++20). Обычно это представление объясняют как-то так:

старший бит является знаковым;
дополнительный код неотрицательных чисел совпадает с прямым кодом;
что бы получить код отрицательного числа -x нужно воспользоваться магическим алгоритмом: инвертировать двоичный код x и прибавить единицу;
фича представления: позволяет реализовать вычитание через сложение;

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

Рассмотрим представление знаковых 8-битных целых.

Построим таблицу в соответствии с выше указанными правилами представления знаковых целых чисел (и упорядочим таблицу по возрастанию кода, почему бы и нет):

Дополнительный код (bin)	Дополнительный код (dec)	Знаковое целое число
$0000\:0000_{2c}$	$000_{10c}$
$0000\:0001_{2c}$	$001_{10c}$
$0000\:0010_{2c}$	$002_{10c}$
...	...	...
$0111\:1110_{2c}$	$126_{10c}$
$0111\:1111_{2c}$	$127_{10c}$
$1000\:0000_{2c}$	$128_{10c}$
$1000\:0001_{2c}$	$129_{10c}$
...	...	...
$1111\:1110_{2c}$	$254_{10c}$
$1111\:1111_{2c}$	$255_{10c}$

Captain Obvious спешит отметить, что столбец Дополнительный код (dec) сильно похож на Беззнаковое целое число (соответствующее дополнительному коду (bin)). Можно думать об этом столбце так как удобно. Но здесь и далее записан дополнительный десятичный код с фиксированной разрядностью.

Заметим, что обратное преобразование (из знакового целого в дополнительный код) можно определить аналогичным образом:

код неотрицательного числа совпадает с самим числом;
код отрицательного получается инвертированием двоичного кода (на самом деле, можно ввести инвертирование и для других позиционных систем счисления) модуля числа и прибавления единицы.

Если ~~ментально~~ ладонью закрыть правый столбец, то можно видеть, что коды они и в Африке коды, и со сложением с wrap around (т.е. по модулю) образуют группу...

Для того чтобы избежать путаницы, введем следующие обозначения:

$\oplus$ — операция сложения по модулю (сложение кода (bin ли dec) c wrap around), и аналогично операция вычитания: $\ominus$ ;
— операция сложения знаковых целых чисел (т.е. операция существующая в языках программирования и которую мы сейчас изучаем).

Вот как можно выполнить сложение знаковых целых:

преобразовываем каждый знаковый целый операнд в дополнительный код;
выполняем сложение по модулю;
преобразовываем дополнительный код результата обратно в знаковое целое.

$1 + (-128) = 0000\:0001_{2c} \oplus 1000\:0000_{2c} = 1000\:0001_{2c} = -127.$

Можно пользоваться десятичной записью дополнительного кода:

$\begin{align} -8 + (-119) = 248_{10c} \oplus 137_{10c} = 385_{10} \bmod 256_{10} = 129_{10c} &= -127; \\ \\ 3 + 126 = 003_{10c} \oplus 126_{10c} = 129_{10c} &= -127; \\ \\ -3 + (-126) = 253_{10c} \oplus 130_{10c} = 383_{10} \bmod 256_{10} = 127_{10c} &= 127. \end{align}$

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

Полезно разобраться в том как получить обратный по сложению элемент знакового целого. Для группы сложения по модулю мы записывали формулу: $a^{-1} = m-a$ , где —делитель mod'а. Воспользуемся ей:

$-x = 2^8_{10} \ominus x_{10} = \left( \left(2^8_{10} \ominus 1_{10}\right)_{2c} \ominus x_{2c} \right) \oplus 0000\:0001_{2c} = \mathord{\sim} x_{2c} \oplus 0000\:0001_{2c}.$

Теперь понятно от куда ноги растут — вот почему дополнительный код устроен именно так, и отныне магический алгоритм с инвертированием расколдован. C+Плюс ко всему, в устном счете удобнее пользоваться вычитанием по модулю обычных десятичных чисел, чем алгоритмом с инвертированием.

Так а что с -INT_MIN ?

Первостепенный вопрос: как реализован унарный оператор минус?

На суръезных ресурсах можно прочитать такое: "The arithmetic-negation operator produces the negative (two's complement) of its operand. (дальше написано про float, хотя вроде 2's complement, но не суть)" (это справедливо не только для C, но и для других языков). Иными словами, унарный оператор минус должен вернуть обратный по сложению элемент по формуле, которую мы только что обсудили.

Думаю, для всех очевидно, но я запишу (для 8-битного целого):

$\begin{align}-128 &= 2^8_{10} \ominus 128_{10} = 128_{10c} = \\ &=\mathord{\sim} 10000000_{2c} \oplus 1_{2c} = 10000000_{2c} = \\ &= -128. \end{align}$

То есть в этой группе число совпадает со своим обратным:

Можно доказать утверждение: в любой группе с четным количеством элементов существует нечетное количество элементов совпадающих со своим обратным и отличных от нейтрального элемента.

Доказательство

По определению группы для каждого элемента существует обратный элемент. Элементы, которые не совпадают со своими обратными образуют пары взаимно обратных (количество элементов: $2\cdot n$ ). Нейтральный элемент совпадает со своим обратным (количество элементов: ). Таким образом пришли к нечетному количеству элементов группы ( $2\cdot n + 1$ ). Чтобы получилось четное количество элементов в группе должно найтись нечетное количество элементов совпадающих со своим обратным и отличных от нейтрального.

"О, я только что понял смысл этой теоремы, а ведь я уже 11 лет читаю этот курс" — Лектор.

Иллюстрация обратных элементов для знаковых и беззнаковых целых

В свете выше изложенного, уже не кажется неожиданным результат возвращаемый оператором унарного минуса для беззнаковых целых (это справедливо не только для C++, но и для других языков), ведь он просто возвращает обратное по сложению число:

unsigned int a = 42;
unsigned int b = -a; // 4294967254 (на моей машине)
unsigned int c = a + b; // 0 (не зависит от машины)

Это хэппи энд? На самом деле, не для всех.

Особенности реализаций int в языках программирования

Из ~~любви~~ уважения начнем с C/C++. Зато потом легче будет (универсальное правило).

По стандартам C/C++ переполнение знакового целого — undefined behaviour, ~~потому что компилятор должен оптимизировать~~. С трудом верится, но, к сожалению, это так, и я не буду разгонять, ибо на хабре уже есть хорошие стать об UB, покрывающие, в том числе, этот вопрос: раз, двас, Меригольд. Так как при переполнении знакового целого произойти может все что угодно и не обязательно wrap around, то фактически знаковый целый тип со сложением не является группой. Было предложение внести ряд изменений в стандарт, но переполнение осталось UB.

К счастью, для беззнакового целого стандарт гарантирует wrap around и, таким образом, это группа по сложению. Вот такая вот неконсистентность.

А что в других языках?

Rust гарантирует wrapping и предоставляет методы для явной обработки переполнения;
в C# (кстати, alpha-beta pruning писался на нем) и Java гарантируется арифметика по модулю и существует возможность контроля переполнения;
в JavaScript плавающая ситуация;
Python, благодаря длинной арифметике, позволяет думать о более возвышенных вещах (но если очень нужно приземлиться:numpy.intс).

Outro

Сюжет у статьи вышел непростым, но надеюсь интересным.

Мы обсудили:

кейс приводящий к проблеме с-INT_MIN;
алгебраическую структуру: группа;
некоторые теоретико групповые аспекты компьютерной целочисленной арифметики;
особенности имплементации целочисленного типа в разных языках программирования.

Мораль: общезначимые знания крайне полезны, но стандарты тоже читать нужно — sad but true.

Мы покрыли широкий спектр тем, но анализ алгебраических свойств компьютерных типов этим не исчерпывается — это лишь верхушка айсберга.

Для погружения в алгебру:

А. Савватеев Теория групп;
Э.Б.Винберг Курс алгебры.

Теги:

Хабы: