23.03.2023 13:44
kodimatrix 33 10000 Источник

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

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

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

Содержание

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

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

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

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

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

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

  4. Так а что с -INT_MIN ?

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

  6. 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 (онлайн пример). Конечно, в данном случае можно использовать другие аргументы для корневого вызова и все будет работать. Но как жить дальше? В начальной школе оператор арифметического отрицания работал не так как в этих ваших компьютерах.

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

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

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

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

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

  1. Выбирается некоторая система аксиом для операции(ий) на множестве;

  2. Находятся и доказываются свойства этой структуры.

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

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

Полезно знать, какой алгебраической структуре соответствует та штука, с которой вы работаете, чтобы понимать с какими свойствами имеешь дело. И этим вопросом в контексте 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.

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

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

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

  • сумма двух любых целых чисел — это целое число, то есть замкнутость выполняется;

  • из начальной школы мы умеем жонглировать скобками — ассоциативность выполняется;

  • существует нейтральный элемент: 0;

  • для любого ненулевого элемента aсуществует обратный: -a.

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

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

  • замкнутость выполняется: произведение двух целых чисел является целым числом;

  • очевидно, ассоциативность выполняется;

  • существует нейтральный элемент: 1;

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

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

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

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

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

  • +_n — операция сложения по модулю;

  • + — обычное сложение целых чисел.

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

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

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

  • замкнутость выполняется (по построению множества);

  • ассоциативность выполняется;

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

    Вначале докажем вспомогательное утверждение для целых чисел:

    \forall x, y \in \mathbb{Z}, n \in \mathbb{Z^+}: \:(x + y) \bmod n = (x \bmod n + y \bmod n) \bmod n;

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

    Целоеxможно представить следующим образом:

    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}

    что и следовало доказать.

  • существует нейтральный элемент: 0.

  • для любого ненулевого элемента aсуществует обратный: a^{-1} = n-a.

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

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

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

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

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

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

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

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

  • старший бит является знаковым;

  • дополнительный код неотрицательных чисел совпадает с прямым кодом;

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

  • фича представления: позволяет реализовать вычитание через сложение;

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

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

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

Дополнительный код (bin)

Дополнительный код (dec)

Знаковое целое число

0000\:0000_{2c}

000_{10c}

0

0000\:0001_{2c}

001_{10c}

1

0000\:0010_{2c}

002_{10c}

2

...

...

...

0111\:1110_{2c}

126_{10c}

126

0111\:1111_{2c}

127_{10c}

127

1000\:0000_{2c}

128_{10c}

-128

1000\:0001_{2c}

129_{10c}

-127

...

...

...

1111\:1110_{2c}

254_{10c}

-2

1111\:1111_{2c}

255_{10c}

-1

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}

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

Полезно разобраться в том как получить обратный по сложению элемент знакового целого. Для группы сложения по модулю мы записывали формулу: a^{-1} = m-a, где m—делитель 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}

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

-128 + (-128) = 0.

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

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

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

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

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

Комментарии (33)


  1. romcky
    00.00.0000 00:00
    #0
    +18

    Спасибо за двадцатилетний флэшбек с лекций по алгебре. Если позволите, поясню для школь тех, кто совсем не дружит с группами, операциями по модулю и обратными кодами. У нас в целое (рассмотрим 8 бит) помещаются числа от -128 до +127, то есть, если мы поменяем знак у -1 получим +1, если у -2 получим +2, ..., если у -127 получим +127, если поменяем знак у -128, что получим? Следующее число после 127, а так как они закончились, начинаем с наименьшего в нашей числовой шкале, то есть -128.


  1. Politura
    00.00.0000 00:00
    #25361294
    +3

    Что-то как-то сложно все и не очень понятно зачем оно нужно. На Википедии довольно просто написано почему именно так реализованы знаковые числа: https://ru.m.wikipedia.org/wiki/Дополнительный_код

    Ну а на грабли, когда -int_min > int_max, а не равно, думаю, натыкались все, кто пытался инвертить знаковые числа для каких-то задач.


    1. kodimatrix Автор
      00.00.0000 00:00
      #25361484
      +2

      На Википедия представлен классический способ объяснения 2s-complement, который позволяет понять устройство и фичу (вычитание реализуется через сложение) этого представления.
      Одна из задач этой статьи (кроме этого обсуждаются и другие вопросы) — посмотреть на доп.код под иным углом (теория групп) и изучить, из каких идей можно исходить, чтобы "разработать с нуля"/вывести представление знаковых целых с такой полезной фичей.

      Иными словами, уровень понимания, которое дает стандартное объяснение, я бы назвал: "Что бы что? И как с этим работать?".
      А уровень понимания через алгебру: "Из чего исходить, чтобы "с нуля разработать" знаковые целые с такой фичей? И какие еще свойства имеют место?".

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


      1. Politura
        00.00.0000 00:00
        #25361552
        +1

        Иными словами, уровень понимания, которое дает стандартное объяснение, я бы назвал: "Что бы что? И как с этим работать?".А уровень понимания через алгебру: "Из чего исходить, чтобы "с нуля разработать" знаковые целые с такой фичей? И какие еще свойства имеют место?".

        Наверное зависит от бекграунда, если он математический, то ваш вариант будет понятнее, если больше программерский, то и Википедии достаточно.

        Я в свое время благодаря объяснению, что сделано чтоб в железе операции сложения/вычитания были одинаковыми для знаковых и беззнаковых чисел чуть поиграл с битами на 8-и битных примерах и понял в чем дело, а на вашем голову сломал. :) Видать далековат я от математики.


        1. kodimatrix Автор
          00.00.0000 00:00
          #25361960

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


  1. romcky
    00.00.0000 00:00
    #25361390
    +18

    Спасибо за двадцатилетний флэшбек с лекций по алгебре. Если позволите, поясню для школь тех, кто совсем не дружит с группами, операциями по модулю и обратными кодами. У нас в целое (рассмотрим 8 бит) помещаются числа от -128 до +127, то есть, если мы поменяем знак у -1 получим +1, если у -2 получим +2, ..., если у -127 получим +127, если поменяем знак у -128, что получим? Следующее число после 127, а так как они закончились, начинаем с наименьшего в нашей числовой шкале, то есть -128.


    1. alexdevfox
      00.00.0000 00:00
      #25364176
      +2

      Когда комментарий лучше самой статьи ????


  1. yurixi
    00.00.0000 00:00
    #25361542

    Как можно такие простые вопросы так растянуть, усложнить, запутать? Автор и математическую теорию приплёл там где почти не затрагивается вопрос вычислений. Кем и для кого это написано? (только мои ощущения, не принимайте близко к сердцу) Безвкусная перемудрённая графоманская статья, ещё и критикующая С++ без действительно важных причин. Если в программе может быть переполнение целого, то либо целое — не тот тип который должен это содержать, либо проверки должен сделать программист, как тот кто полностью представляет себе ограничения своей программы.


    Сначала люди себе придумывают, что целые числа в компьютере это целые числа из математики, а потом удивляются, что это не так. А задать вопрос, кто вас так жестоко обманул, не пробовали?


    Обманул не то что вместо одних чисел подсунул другие, а в том что убедил что в компьютере должна быть реализована математическая теория не через программы, а сразу встроено, чтоб программист сразу общался с компьютером теоремами, прямо на уровне железа. Я бы сказал, что у вас просто нет понимания низкоуровневого программирования. Всё бы ничего, но выставлять своё непонимание как критику — это уже слишком.


    А ещё вот так сильно разбавив математикой как водой, это даже тянет на оскорбление математики. Ей всё равно, а вот читателям неприятно. У меня ощущения как будто читал ссору между недоматематиком и недопрограммистом.
    А точнее — они были на одной стороне конфликта.


    1. YourChief
      00.00.0000 00:00
      #25361664
      +7

      Сначала люди себе придумывают, что целые числа в компьютере это целые числа из математики, а потом удивляются, что это не так. А задать вопрос, кто вас так жестоко обманул, не пробовали?

      Целые числа в компьютере из математики, и автор посвятил статью описанию из какой именно математики.

      Обманул не то что вместо одних чисел подсунул другие, а в том что убедил
      что в компьютере должна быть реализована математическая теория не через
      программы, а сразу встроено, чтоб программист сразу общался с
      компьютером теоремами, прямо на уровне железа.

      Демагогический приём подмены тезиса. Автор не высказывал подобных ожиданий.

      Всё бы ничего, но выставлять своё непонимание как критику — это уже слишком.

      Автор как раз всё понял и разъяснил. А Вы-то суть прочитанного поняли?

      А ещё вот так сильно разбавив математикой как водой, это даже тянет на оскорбление математики. Ей всё равно, а вот читателям неприятно

      Говорите за себя.

      А ещё вот так сильно разбавив математикой как водой, это даже тянет на
      оскорбление математики. Ей всё равно, а вот читателям неприятно. У меня
      ощущения как будто читал ссору между недоматематиком и
      недопрограммистом.

      А точнее — они были на одной стороне конфликта.

      В Вашем комментарии 0 фактов, демагогия и хамство. Отвратительно.


      1. yurixi
        00.00.0000 00:00
        #25361704

        Целые числа в компьютере из математики, и автор посвятил статью описанию из какой именно математики.

        Да, но с претензией, разве нет?


        Демагогический приём подмены тезиса. Автор не высказывал подобных ожиданий.

        Нет, это у меня не демагогический прием, это описание усиленного впечатления. Я знаю, что автор не высказывал ожиданий, но сама "постановка вопроса" — это именно претензия в описанном мной направлении


        Автор как раз всё понял и разъяснил. А Вы-то суть прочитанного поняли?

        Суть написанного это описание устройство и описание претензии к нему. Вот вторая часть мне и не нравится. А где часть о том что претензии не такие критичные? Её нет. Автор недоволен С++, это факт.


        Говорите за себя.

        Ну я и сравнил с собой. Я бы не расписывал полями и группами обыкновенный цикл для кодов. Раздутость усиливает претензию автора. Написанное в статье — раза в два больше чем материал который я бы уже посчитал раздутым.


        В Вашем комментарии 0 фактов, демагогия и хамство. Отвратительно.

        Я старался без оскорблений выразить ощущения. Факт что автор не уважает низкоуровневое программирование есть. Возможно даже намеренно избегает представления о нём. Демагогии у меня нет, я в одном моменте только усилил описание. Хамства тоже как такового нет, потому что я с уважением отношусь к автору и поддержу его в улучшении качества статей.


        К слову, ваши замечания тоже были очень полезны, я ещё раз переоценил свои выводы и думаю, что такие статьи полезны. И критикующие комментарии к ним полезны тоже.


        1. kodimatrix Автор
          00.00.0000 00:00
          #25362074
          +2

          Автор недоволен С++, это факт.

          Ответ в другой ветке обсуждения.

          Факт что автор не уважает низкоуровневое программирование есть.

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

          К слову, ваши замечания тоже были очень полезны, я ещё раз переоценил свои выводы и думаю, что такие статьи полезны. И критикующие комментарии к ним полезны тоже.

          Полностью согласен! И спасибо Вам за комментарии.


    1. kodimatrix Автор
      00.00.0000 00:00
      #25362058
      +1

      Автор и математическую теорию приплёл там где почти не затрагивается вопрос вычислений.

      Математика занимается не только вычислениями.

      критикующая С++ без действительно важных причин

      Тот раздел статьи, скорее, не критика C++, а ироничное рассуждение о конкретном факте из стандарта. И эта ирония является продуктом переживания за развитие языка.

      Если в программе может быть переполнение целого, то либо целое — не тот тип который должен это содержать, либо проверки должен сделать программист

      Согласен. Но это очень косвенно связано с текстом статьи. К тому же, вопрос проверок переполнения в C/C++ тоже не так прост.

      Я бы сказал, что у вас просто нет понимания низкоуровневого программирования.

      Гномье программирование? Это про endian'ы, байты, битовые маски, выравнивания и аллокации памяти, а так же другую волшебную магию?
      Да, слышал я о таком. Но сам то я из хоббитов - не нужны мне эти приключения...


  1. mmMike
    00.00.0000 00:00
    #25361870
    +3

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

    А Вы не задумывались почему "не часто"?

    Вот когда то давно, учил и теорию групп в рамках вышки и одновременно теорию выч машин (типичная тема курсовиков - создание ALU). И как то никто из преподавателей не пытался натянуть сову на глобус.

    Вы точно уверены в необходимости объяснения такой простой вещи как двоичная арифметика и представление чисел в "дополнительной кодировке" через призму удобной именно Вам "совы" (терминологии и мат аппарата)?

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

    Извините. Но что то вспомнился анекдот, с уроком в средней школе по площади треугольника и совету учительницы поменять пределы интегрирования на вопрос ученика, почему площадь у него отрицательная в расчетах.


    1. kodimatrix Автор
      00.00.0000 00:00
      #25362018

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

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

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


  1. MilPavel
    00.00.0000 00:00
    #25362098
    +2

    Используйте MS Excel и VBA, и Вы удивитесь, как все правильно, логично и просто работает, без интересных особенностей модных языков.


  1. NeoCode
    00.00.0000 00:00
    #25362144
    +3

    Очевидно, что в рамках некоторого целочисленного знакового типа отрицательных чисел на 1 больше чем положительных, и поэтому у INT_MIN нет соответствующего парного числа. Но дополнительный код - самая простая реализация целых чисел, позволяющая в том числе повышать разрядность вычислений за счет цепочек сложения с переносом (ADD/ADC, SUB/SBB).

    А вот что интересно. Существуют ли процессорные архитектуры с более сложными аппаратными реализациями целых чисел? Например, можно код условного "-128" объявить как целочисленный NaN, что может быть весьма полезно для аппаратной реализации "нуллабельности" (optional<int>). И появляется симметрия, -INT_MIN всегда будет равно INT_MAX и наоборот. Разумеется, такое режим не должен быть единственным, от классического дополнительного кода не следует отказываться. Но в качестве расширения, управляемого какими-то префиксами ассемблерных команд - почему бы и нет? И если идти по этому пути, то можно реализовать и еще режимы, например вычисления с насыщением.


    1. netch80
      00.00.0000 00:00
      #25362838
      +2

      Например, можно код условного "-128" объявить как целочисленный NaN

      Процессорных не видел. Программно — в kdb+ именно так и сделано.
      В однобайтных, 0x80 = NaN, 0x7f = +Inf, 0x81 = -Inf.
      Правда, там криво — если расширить до 2 байтов и выше, 0x7f переходит в 127. Намеренно недоработано для скорости обработки данных.
      Есть ещё разные статьи с предложениями подобной арифметики как защитного подхода.


      1. kodimatrix Автор
        00.00.0000 00:00
        #25363016

        Очень интересная информация! Не могли бы Вы поделиться ссылками?


        1. netch80
          00.00.0000 00:00
          #25363074

          https://code.kx.com/q/basics/datatypes/
          См. колонки null, inf. Хотя для постороннего, да, эта дока совсем зашифрованная.


          1. kodimatrix Автор
            00.00.0000 00:00
            #25364690

            Спасибо за ссылку!
            Да, язык суровый. Даже самый понятный фрагмент (и то только в контексте) выглядит устрашающе:

            q)1+-1+-1+1+ -0W 0N 0W 1 2 3
0N 0N 0N 1 2 3

            Читать эту доку с середины - плохая затея. Но, что стало понятно из текста под спойлером: в арифметических выражениях +/- inf под капотом ведет себя просто как max_int / min_int+1, но делается проверка на нул.


    1. kodimatrix Автор
      00.00.0000 00:00
      #25362946

      Очевидно, что в рамках некоторого целочисленного знакового типа отрицательных чисел на 1 больше чем положительных, и поэтому у -INT_MIN нет соответствующего парного числа.

      Да, и в тексте есть доказательство более общего утверждения.

      Существуют ли процессорные архитектуры с более сложными аппаратными реализациями целых чисел? Например, можно код условного "-128" объявить как целочисленный NaN, что может быть весьма полезно для аппаратной реализации "нуллабельности" (optional). И появляется симметрия, -INT_MIN всегда будет равно INT_MAX и наоборот.

      Не знаю о существовании подобных реализаций. Но мысль интересная! В таком случае, если требовать, что результат сложения с null'ом - есть null, то, похоже, потребуется усложнение АЛУ. И будут потеряны некоторые полезные свойства, но появится полезное свойство опциональности.


  1. iingvaar
    00.00.0000 00:00
    #25362188
    +7

    Статья хорошая, а комментарии немного удивили. Они тоже по делу, но основная претензия "Ты упоминаешь С++, но ты делаешь это без должного уважения". Напомнило комментарии к любой статье про Байкал.


  1. ChessMax
    00.00.0000 00:00
    #25362622

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

    У меня не появился( Можно объяснить, как предполагается это доказать?


    1. netch80
      00.00.0000 00:00
      #25362850
      +2

      Тип данных uint2_t :)


      1. ChessMax
        00.00.0000 00:00
        #25362924
        +1

        Ну т.е. 10 + 10 = 00. Так?


        1. netch80
          00.00.0000 00:00
          #25362952
          +1

          Именно. Только надо было выбрать правильную алгебру :))


    1. kodimatrix Автор
      00.00.0000 00:00
      #25363076

      Конечно, честнее говорить не "доказательство утверждения...", а "выбор/демонстрация такой алгебраической структуры, в которой 2+2=0". Позволил себе не строгую формулировку под картинкой)
      Это продемонстрировано в статье как один из примеров групп (таблица сложения 4_+).


  1. domix32
    00.00.0000 00:00
    #25363506
    +1

    Rust гарантирует wrapping

    Он гарантирует панику, если ни одно из поведений переполнения не было выбранно.


    1. kodimatrix Автор
      00.00.0000 00:00
      #25364724
      +1

      Паника гарантируется в дебаге. В релизе - wrapping. И есть методы с явной обработкой переполнения.


  1. gnomeby
    00.00.0000 00:00
    #25364134
    +1

    Хорошо заходит в тему обсуждений по недавней статье про троичную логику: https://habr.com/ru/company/timeweb/blog/723404 . Троичная симметричная система лишена указанного недостатка.


  1. Kurku9r
    00.00.0000 00:00
    #25364238
    +1

    Хорошо, что Галуа не видел этого доказательства ассоциативности


    1. kodimatrix Автор
      00.00.0000 00:00
      #25364698

      ????


  1. Vitter
    00.00.0000 00:00
    #25366620

    ох-ох-ох.
    Негативных чисел в компьютерном представлении нет, это лишь р-адические числа (которых, кстати, больше, чем натурнальных), кстати, натуральные числа тоже хранятся как р-адические.
    Положительные числа - это
    +N =(0) + N
    а негативные - это:
    -N = (9) - N +1
    То бишь, +5 = (0)5 , -1 = (9) , а -6 = (9)4
    Хотя, конечно, в компьютерах 2-ричная система исчисления, а не 10-тичная.

    Что же касается вашей программы - надо было лишь использовать числа от INT_MIN до -INT_MIN и всё бы работало как надо!


    1. gnomeby
      00.00.0000 00:00
      #25366800
      +2

      Видимо имелось ввиду от INT_MAX до -INT_MAX