Комментарии 42
Спасибо за двадцатилетний флэшбек с лекций по алгебре. Если позволите, поясню для школь тех, кто совсем не дружит с группами, операциями по модулю и обратными кодами. У нас в целое (рассмотрим 8 бит) помещаются числа от -128 до +127, то есть, если мы поменяем знак у -1 получим +1, если у -2 получим +2, ..., если у -127 получим +127, если поменяем знак у -128, что получим? Следующее число после 127, а так как они закончились, начинаем с наименьшего в нашей числовой шкале, то есть -128.
Что-то как-то сложно все и не очень понятно зачем оно нужно. На Википедии довольно просто написано почему именно так реализованы знаковые числа: https://ru.m.wikipedia.org/wiki/Дополнительный_код
Ну а на грабли, когда -int_min > int_max, а не равно, думаю, натыкались все, кто пытался инвертить знаковые числа для каких-то задач.
На Википедия представлен классический способ объяснения 2s-complement, который позволяет понять устройство и фичу (вычитание реализуется через сложение) этого представления.
Одна из задач этой статьи (кроме этого обсуждаются и другие вопросы) — посмотреть на доп.код под иным углом (теория групп) и изучить, из каких идей можно исходить, чтобы "разработать с нуля"/вывести представление знаковых целых с такой полезной фичей.
Иными словами, уровень понимания, которое дает стандартное объяснение, я бы назвал: "Что бы что? И как с этим работать?".
А уровень понимания через алгебру: "Из чего исходить, чтобы "с нуля разработать" знаковые целые с такой фичей? И какие еще свойства имеют место?".
Сложность, возможно, связанна с формальным (хотя и не строгим) стилем изложения.
Зачем заниматься формальностями и прочими математиками? Даже если мы не видим практической пользы, хотя бы потому, что в этом есть красота.
Иными словами, уровень понимания, которое дает стандартное объяснение, я бы назвал: "Что бы что? И как с этим работать?".А уровень понимания через алгебру: "Из чего исходить, чтобы "с нуля разработать" знаковые целые с такой фичей? И какие еще свойства имеют место?".
Наверное зависит от бекграунда, если он математический, то ваш вариант будет понятнее, если больше программерский, то и Википедии достаточно.
Я в свое время благодаря объяснению, что сделано чтоб в железе операции сложения/вычитания были одинаковыми для знаковых и беззнаковых чисел чуть поиграл с битами на 8-и битных примерах и понял в чем дело, а на вашем голову сломал. :) Видать далековат я от математики.
Спасибо за двадцатилетний флэшбек с лекций по алгебре. Если позволите, поясню для школь тех, кто совсем не дружит с группами, операциями по модулю и обратными кодами. У нас в целое (рассмотрим 8 бит) помещаются числа от -128 до +127, то есть, если мы поменяем знак у -1 получим +1, если у -2 получим +2, ..., если у -127 получим +127, если поменяем знак у -128, что получим? Следующее число после 127, а так как они закончились, начинаем с наименьшего в нашей числовой шкале, то есть -128.
Как можно такие простые вопросы так растянуть, усложнить, запутать? Автор и математическую теорию приплёл там где почти не затрагивается вопрос вычислений. Кем и для кого это написано? (только мои ощущения, не принимайте близко к сердцу) Безвкусная перемудрённая графоманская статья, ещё и критикующая С++ без действительно важных причин. Если в программе может быть переполнение целого, то либо целое — не тот тип который должен это содержать, либо проверки должен сделать программист, как тот кто полностью представляет себе ограничения своей программы.
Сначала люди себе придумывают, что целые числа в компьютере это целые числа из математики, а потом удивляются, что это не так. А задать вопрос, кто вас так жестоко обманул, не пробовали?
Обманул не то что вместо одних чисел подсунул другие, а в том что убедил что в компьютере должна быть реализована математическая теория не через программы, а сразу встроено, чтоб программист сразу общался с компьютером теоремами, прямо на уровне железа. Я бы сказал, что у вас просто нет понимания низкоуровневого программирования. Всё бы ничего, но выставлять своё непонимание как критику — это уже слишком.
А ещё вот так сильно разбавив математикой как водой, это даже тянет на оскорбление математики. Ей всё равно, а вот читателям неприятно. У меня ощущения как будто читал ссору между недоматематиком и недопрограммистом.
А точнее — они были на одной стороне конфликта.
Сначала люди себе придумывают, что целые числа в компьютере это целые числа из математики, а потом удивляются, что это не так. А задать вопрос, кто вас так жестоко обманул, не пробовали?
Целые числа в компьютере из математики, и автор посвятил статью описанию из какой именно математики.
Обманул не то что вместо одних чисел подсунул другие, а в том что убедил
что в компьютере должна быть реализована математическая теория не через
программы, а сразу встроено, чтоб программист сразу общался с
компьютером теоремами, прямо на уровне железа.
Демагогический приём подмены тезиса. Автор не высказывал подобных ожиданий.
Всё бы ничего, но выставлять своё непонимание как критику — это уже слишком.
Автор как раз всё понял и разъяснил. А Вы-то суть прочитанного поняли?
А ещё вот так сильно разбавив математикой как водой, это даже тянет на оскорбление математики. Ей всё равно, а вот читателям неприятно
Говорите за себя.
А ещё вот так сильно разбавив математикой как водой, это даже тянет на
оскорбление математики. Ей всё равно, а вот читателям неприятно. У меня
ощущения как будто читал ссору между недоматематиком и
недопрограммистом.А точнее — они были на одной стороне конфликта.
В Вашем комментарии 0 фактов, демагогия и хамство. Отвратительно.
Целые числа в компьютере из математики, и автор посвятил статью описанию из какой именно математики.
Да, но с претензией, разве нет?
Демагогический приём подмены тезиса. Автор не высказывал подобных ожиданий.
Нет, это у меня не демагогический прием, это описание усиленного впечатления. Я знаю, что автор не высказывал ожиданий, но сама "постановка вопроса" — это именно претензия в описанном мной направлении
Автор как раз всё понял и разъяснил. А Вы-то суть прочитанного поняли?
Суть написанного это описание устройство и описание претензии к нему. Вот вторая часть мне и не нравится. А где часть о том что претензии не такие критичные? Её нет. Автор недоволен С++, это факт.
Говорите за себя.
Ну я и сравнил с собой. Я бы не расписывал полями и группами обыкновенный цикл для кодов. Раздутость усиливает претензию автора. Написанное в статье — раза в два больше чем материал который я бы уже посчитал раздутым.
В Вашем комментарии 0 фактов, демагогия и хамство. Отвратительно.
Я старался без оскорблений выразить ощущения. Факт что автор не уважает низкоуровневое программирование есть. Возможно даже намеренно избегает представления о нём. Демагогии у меня нет, я в одном моменте только усилил описание. Хамства тоже как такового нет, потому что я с уважением отношусь к автору и поддержу его в улучшении качества статей.
К слову, ваши замечания тоже были очень полезны, я ещё раз переоценил свои выводы и думаю, что такие статьи полезны. И критикующие комментарии к ним полезны тоже.
Автор недоволен С++, это факт.
Ответ в другой ветке обсуждения.
Факт что автор не уважает низкоуровневое программирование есть.
В другой ветке ироничный ответ. В действительности, я уважаю низкоуровневое программирование, и эта статья тому подтверждение.
К слову, ваши замечания тоже были очень полезны, я ещё раз переоценил свои выводы и думаю, что такие статьи полезны. И критикующие комментарии к ним полезны тоже.
Полностью согласен! И спасибо Вам за комментарии.
Автор и математическую теорию приплёл там где почти не затрагивается вопрос вычислений.
Математика занимается не только вычислениями.
критикующая С++ без действительно важных причин
Тот раздел статьи, скорее, не критика C++, а ироничное рассуждение о конкретном факте из стандарта. И эта ирония является продуктом переживания за развитие языка.
Если в программе может быть переполнение целого, то либо целое — не тот тип который должен это содержать, либо проверки должен сделать программист
Согласен. Но это очень косвенно связано с текстом статьи. К тому же, вопрос проверок переполнения в C/C++ тоже не так прост.
Я бы сказал, что у вас просто нет понимания низкоуровневого программирования.
Гномье программирование? Это про endian'ы, байты, битовые маски, выравнивания и аллокации памяти, а так же другую волшебную магию?
Да, слышал я о таком. Но сам то я из хоббитов - не нужны мне эти приключения...
но тема алгебраических свойств integer'а и float'а, действительно, не часто освещается в литературе и интернетах, однако эти знания углубляют понимание реализации компьютерной арифметики и применимы на практике.
А Вы не задумывались почему "не часто"?
Вот когда то давно, учил и теорию групп в рамках вышки и одновременно теорию выч машин (типичная тема курсовиков - создание ALU). И как то никто из преподавателей не пытался натянуть сову на глобус.
Вы точно уверены в необходимости объяснения такой простой вещи как двоичная арифметика и представление чисел в "дополнительной кодировке" через призму удобной именно Вам "совы" (терминологии и мат аппарата)?
Особенно, с учетом того, что Вас сподвигло на это ошибка в использовании (понимании) целочисленной арифметики (конкретной реализации архитектуры, кстати. Хоть и наиболее типичной сейчас).
Извините. Но что то вспомнился анекдот, с уроком в средней школе по площади треугольника и совету учительницы поменять пределы интегрирования на вопрос ученика, почему площадь у него отрицательная в расчетах.
Вы точно уверены в необходимости объяснения такой простой вещи как двоичная арифметика и представление чисел в "дополнительной кодировке" через призму удобной именно Вам "совы" (терминологии и мат аппарата)? Особенно, с учетом того, что Вас сподвигло на это ошибка в использовании (понимании) целочисленной арифметики
Истинная мотивация для написания статьи связана с тем фактом, что когда-то я не смог найти в интернете информацию по этой теме (алгебраических свойств комп.арифм.), и с тех пор доступнее она не стала (ChatGPT, кстати, часто бредит на тему алгебры). Надеюсь, эта статья поможет тому кто тоже будет искать ответы на те же вопросы.
И та ошибка произошла из-за того, что я нарушил хорошую практику, не сильно задумавшись. Но спустя несколько минут анализа произошедшего, я испытал много эмоций, и это в свою очередь подтолкнуло к написанию статьи.
Используйте MS Excel и VBA, и Вы удивитесь, как все правильно, логично и просто работает, без интересных особенностей модных языков.
Очевидно, что в рамках некоторого целочисленного знакового типа отрицательных чисел на 1 больше чем положительных, и поэтому у INT_MIN нет соответствующего парного числа. Но дополнительный код - самая простая реализация целых чисел, позволяющая в том числе повышать разрядность вычислений за счет цепочек сложения с переносом (ADD/ADC, SUB/SBB).
А вот что интересно. Существуют ли процессорные архитектуры с более сложными аппаратными реализациями целых чисел? Например, можно код условного "-128" объявить как целочисленный NaN, что может быть весьма полезно для аппаратной реализации "нуллабельности" (optional<int>). И появляется симметрия, -INT_MIN всегда будет равно INT_MAX и наоборот. Разумеется, такое режим не должен быть единственным, от классического дополнительного кода не следует отказываться. Но в качестве расширения, управляемого какими-то префиксами ассемблерных команд - почему бы и нет? И если идти по этому пути, то можно реализовать и еще режимы, например вычисления с насыщением.
Например, можно код условного "-128" объявить как целочисленный NaN
Процессорных не видел. Программно — в kdb+ именно так и сделано.
В однобайтных, 0x80 = NaN, 0x7f = +Inf, 0x81 = -Inf.
Правда, там криво — если расширить до 2 байтов и выше, 0x7f переходит в 127. Намеренно недоработано для скорости обработки данных.
Есть ещё разные статьи с предложениями подобной арифметики как защитного подхода.
Очень интересная информация! Не могли бы Вы поделиться ссылками?
https://code.kx.com/q/basics/datatypes/
См. колонки null, inf. Хотя для постороннего, да, эта дока совсем зашифрованная.
Спасибо за ссылку!
Да, язык суровый. Даже самый понятный фрагмент (и то только в контексте) выглядит устрашающе:
q)1+-1+-1+1+ -0W 0N 0W 1 2 3
0N 0N 0N 1 2 3
Читать эту доку с середины - плохая затея. Но, что стало понятно из текста под спойлером: в арифметических выражениях +/- inf под капотом ведет себя просто как max_int / min_int+1, но делается проверка на нул.
Очевидно, что в рамках некоторого целочисленного знакового типа отрицательных чисел на 1 больше чем положительных, и поэтому у -INT_MIN нет соответствующего парного числа.
Да, и в тексте есть доказательство более общего утверждения.
Существуют ли процессорные архитектуры с более сложными аппаратными реализациями целых чисел? Например, можно код условного "-128" объявить как целочисленный NaN, что может быть весьма полезно для аппаратной реализации "нуллабельности" (optional). И появляется симметрия, -INT_MIN всегда будет равно INT_MAX и наоборот.
Не знаю о существовании подобных реализаций. Но мысль интересная! В таком случае, если требовать, что результат сложения с null'ом - есть null, то, похоже, потребуется усложнение АЛУ. И будут потеряны некоторые полезные свойства, но появится полезное свойство опциональности.
Статья хорошая, а комментарии немного удивили. Они тоже по делу, но основная претензия "Ты упоминаешь С++, но ты делаешь это без должного уважения". Напомнило комментарии к любой статье про Байкал.
Сайд эффект от прочтения статьи: появится навык доказательства утверждения 2+2=0.
У меня не появился( Можно объяснить, как предполагается это доказать?
Тип данных uint2_t :)
Конечно, честнее говорить не "доказательство утверждения...", а "выбор/демонстрация такой алгебраической структуры, в которой 2+2=0". Позволил себе не строгую формулировку под картинкой)
Это продемонстрировано в статье как один из примеров групп (таблица сложения 
).
Rust гарантирует wrapping
Он гарантирует панику, если ни одно из поведений переполнения не было выбранно.
Хорошо заходит в тему обсуждений по недавней статье про троичную логику: https://habr.com/ru/company/timeweb/blog/723404 . Троичная симметричная система лишена указанного недостатка.
Хорошо, что Галуа не видел этого доказательства ассоциативности
ох-ох-ох.
Негативных чисел в компьютерном представлении нет, это лишь р-адические числа (которых, кстати, больше, чем натурнальных), кстати, натуральные числа тоже хранятся как р-адические.
Положительные числа - это
+N =(0) + N
а негативные - это:
-N = (9) - N +1
То бишь, +5 = (0)5 , -1 = (9) , а -6 = (9)4
Хотя, конечно, в компьютерах 2-ричная система исчисления, а не 10-тичная.
Что же касается вашей программы - надо было лишь использовать числа от INT_MIN до -INT_MIN и всё бы работало как надо!
Видимо имелось ввиду от INT_MAX до -INT_MAX
Негативных чисел в компьютерном представлении нет
Да, можно так сформулировать. В статье есть абзац про изоморфизм, в котором предложено смотреть на отрицательные числа знакового типа как на специальную запись соответствующих беззнаковых чисел.
это лишь р-адические числа
Действительно, это так. Но это никак не противоречит той математической теории, которая показана в статье. Более того об р-адических числах невозможно говорить без алгебраической подготовки. Статья рассчитывалась быть доступной для читателя, не знающего основные алгебраические структуры. Эта заметка ограничивается понятием группы, не обсуждая даже абелевы группы и, тем более, не доходя до колец и полей. Таким образом, рассмотрение целого типа как р-адических чисел это очень интересная, но более глубокая тема. Спасибо за наблюдение!
Что же касается вашей программы - надо было лишь использовать числа от INT_MIN до -INT_MIN и всё бы работало как надо!
В статье сделано заключение о том, что нужно использовать другие аргументы корневого вызова. И в программе были использованы INT_MAX и -INT_MAX.
Какая то унылая графомань ради графомани. Автору бы в универе работать, научные статьи (в стол) писать, цены бы ему не было. Или он уже там?
Нам важно отметить следующее: функция alphaBeta() имеет параметры alpha, beta и рекурсивно вызывает себя поменяв местами аргументы и их знаки -beta, -alpha
Альфа бета гамма дельта альфа альфа штрих дельта альфа бета штрих дельта альфа гамма штрих дельта бета альфа штрих дельта бета бета штрих дельта бета гамма штрих
Автору огромное спасибо за статью, всегда приятно почитать про абстрактные вещи, которые находят применение в реальности. :)
Хорошо, что Галуа не видел этого доказательства ассоциативности (хотя, справедливости ради, он не видел примерно все доказательства в рамках теории групп в силу своей судьбы).
И да, у меня в старой версии Хабра текст доказательства про наличие не-нейтрального самообратного элемента в группе с чётным количеством элементов почему-то содержит пропуски в местах, где должны быть числа.
Хорошо, что Галуа не видел этого доказательства ассоциативности (хотя, справедливости ради, он не видел примерно все доказательства в рамках теории групп в силу своей судьбы).
Печально, но это правда
И да, у меня в старой версии Хабра текст доказательства про наличие не-нейтрального самообратного элемента в группе с чётным количеством элементов почему-то содержит пропуски в местах, где должны быть числа.
Да, вроде, исправил это. И заметил не точность в формулировке доказываемого утверждения. Изменил: "в любой группе с четным количеством элементов существует нечетное количество элементов совпадающих со своим обратным и отличных от нейтрального элемента."
Спасибо Вам!
Мне кажется, что эта тема возникла только из-за несоответствия абстрактной теории с конкретным ее применением. У любой реализации (у любого применения теории) есть допущения и есть границы, в которых эти допущения работают. Если пытаешься применить теорию на границах (за границами) - сам себе злобный Буратино. Это как бегать с ньютоновской механикой вокруг синхрофазотрона
Алгебра int о которой не говорят