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

%

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

Но сначала очень короткое, чрезвычайно сложное введение в алгебру. Вы можете думать об алгебре как об изучении систем счисления. Алгебра в начальной школе обычно включает решение уравнений для неизвестных значений путем изучения свойств операций (+, -, *, / и т. Д.) Над числами. Большинство студентов смотрят на несколько систем счисления с разными операциями, хотя часто студенты прыгают между разными видами систем счисления, не осознавая этого.

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

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

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

Обратите внимание, что в арифметике натуральных чисел дело обстоит иначе, вычитание действительно отличается от сложения, потому что вы можете сложить любые два натуральных числа и получить другое натуральное число, но выражения вроде 1–2 не определены, потому что нет натуральных чисел меньше нуля.

Точно так же целочисленная арифметика имеет деление, а рациональные числа - нет. Игнорируя ноль, для любого рационального числа есть другое рациональное число, на которое вы можете умножить его, чтобы получить единицу (ноль и единица играют аналогичные роли по отношению к сложению и умножению соответственно). Как и выше, вы можете переписать любое деление в рациональных числах как умножение одного числа на обратное умножение другого. Вы не можете делать это в целочисленной арифметике, умножение одного целого числа на другое всегда является целым числом, но выражения вроде 5/2 в этой системе не определены.

Такие операции, как вычитание натуральных чисел и деление целых чисел, расширяют более простую систему. Вы можете себе представить, что на самом деле это вовсе не операции, это сокращение для громоздких выражений, связанных с неизвестными. В натуральном выражении, если бы вы были очень строгими, вы бы не написали выражение вроде 3–2, вы бы написали уравнение с неизвестным, например 2 + x = 3 . Точно так же целочисленная арифметика выражение 6/2 на самом деле означает что-то вроде 2 * x = 6, но мы обычно опускаем эти вещи.

Определение модуля

Модуль - это операция, которая расширяет целочисленную арифметику таким образом, что позволяет нам последовательно определять деление повсюду. Вы не можете просто заменить операнды на их обратные или составить уравнение, используя одно неизвестное, чтобы понять такое выражение, как 5/2 в целых числах. Без других инструментов это выражение просто не определено.

Чтобы дать этому выражению единообразное определение, мы прибегаем к уравнению для двух неизвестных, которое мы называем частным (q) и остаток (r) . Если у нас есть два целых числа, a и b, и мы хотим поговорить о делении a на b мы будем использовать центральное уравнение в этой статье. Вот это:

b*q + r = a

Об этом стоит немного поговорить. Выражение, которому мы хотим присвоить значение, - a / b. То есть a делится на b много частей. Предположим на мгновение, что r равно нулю. Тогда это уравнение будет b * q = a. Это обратное умножению, мы можем разделить обе части, чтобы получить q = a / b. Теперь предположим, что b не делит a равномерно. Тогда никакое целое число q не может решить уравнение b * q = a. однако мы можем выбрать q как можно ближе к a и добавить немного больше, чтобы компенсировать разницу. Мы присвоим значение выражения a / b q. Тогда модуль a% b - это значение r.

Проблема в том, что у нас есть много решений для пар q и r, которые работают. Например, если мы хотим оценить 5/2, мы могли бы иметь q = 1, r = 3 или q = 2, r = 1 или q = 60. , г = -115. Это не особенно полезный ответ, потому что наши символы операций не оценивают что-либо конкретное, и он не отражает идею разделения, которая заключается в разделении a на b частей. Фактически, мы можем выбрать любой ответ для q и найти некоторое r, которое удовлетворяет уравнению, которое мы хотим решить.

Чтобы решить эту проблему, мы добавляем дополнительное ограничение. Мы хотим, чтобы частное было чем-то близким к тому, что могло бы дать рациональное деление (чтобы отразить идею предполагаемого деления), поэтому мы не позволяем r быть больше, чем b , за исключением глупых ответов, подобных первому выше. Мы также говорим, что r не может быть меньше нуля, за исключением еще более глупого третьего ответа, приведенного выше. Этих двух ограничений достаточно, чтобы гарантировать, что наши «/» и «%» будут давать ровно один ответ для любых a и b (если b не равно нулю, это тема другого дня).

Ура! Теперь мы можем делить целые числа, не беспокоясь о работе с рациональными числами. Это очень важно, потому что компьютеры в любом случае могут работать только с целыми числами.

Модуль в JavaScript

Хорошо, отлично, в мире все хорошо, и мы можем безопасно выполнять вычисления, работая только с целыми числами!

Для этого в JavaScript мы можем использовать «%» для модуля, и мы используем «Math.floor» для целочисленного деления. Проверить это!

Прохладный!

КРУТО!

…

Почему именно JavaScript, почему.

Давайте посмотрим здесь 3 * -3, это -9. Довольно близко и меньше целевого числа, что имеет смысл. Но -9 + -2… это -11! WTH. Что ж, может быть, если мы просто опустим знак, тогда -9 + 2 = -7. Нет.

Теперь все сломано! У нас была хорошая согласованная система для работы с целыми числами JavaScript ПОЧЕМУ!

Что тут происходит?

…

Чего ждать?

JavaScript - это безумие. Сохраняет знак слева. В этом нет никакого смысла.

Вы можете подумать сейчас: «Да ладно тебе, мужик, это совершенно педантично», хотя это немного, но не совсем так. Это актуальная проблема, которую я сейчас проиллюстрирую.

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

const Scale = [«C», «D», «E», «F», «G», «A», «B»];

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

А теперь давайте создадим случайную мелодию с этой гаммой. Мы соберем все это в один файл, и когда мы запустим его, он выдаст случайно сгенерированную мелодию!

и давайте попробуем мелодию из 12 нот из простой гаммы.

Аккуратный!

Но это только восхождение! Что, если мы хотим иметь возможность подниматься и опускаться по шкале?

Давайте внесем некоторые изменения

Хм. это не сработало. Ах, да! Потому что отрицательные числа не дают нам записи в нашем массиве! Мы могли бы просто вычислить абсолютное значение, например:

Но у нас все еще есть проблема! Мы настроили программу, чтобы передавать не более 4 тонов за раз. Это скачок на октаву вниз! Когда мы переходим от октавы 0 к октаве -1, мы неожиданным образом перепрыгиваем через массив.

В этом примере это довольно незначительное проступок, но программа не дает ожидаемого поведения. Отрицательные значения, создаваемые модулем JavaScript, значительно затрудняют рассуждение о нашей программе и прогнозирование того, что она собирается делать. Конечно, мы могли бы сделать нулевую октаву самой низкой допустимой и запретить нашему указателю опускаться ниже нуля, но в более сложном приложении это может оказаться невозможным, мы многие не хотим или не можем фиксировать абсолютную нулевую точку. Хуже того, если бы мы просто не подумали об этом заранее, мы могли бы внести ДЕЙСТВИТЕЛЬНО РАЗДРАЖАЮЩИЕ ошибки, которые очень трудно отследить из-за того, как JavaScript плохо обращается с модульной арифметикой.

К счастью, это не так уж и сложно исправить. Мы просто сделаем небольшую вспомогательную функцию.

Наркотик. Оно работает. Вот почему.

Первое, что мы здесь делаем, это берем модуль JavaScript по умолчанию. Происходит одно из двух: мы получим положительное или отрицательное число. Если он положительный, то добавление b и модификация на b снова не дадут никаких изменений. Если у нас есть отрицательное число, добавление b делает что-то более интересное.

Здесь действует совершенно новая система счисления - модульная арифметика. не вдаваясь в подробности, модульная арифметика - это арифметика конечных наборов целых чисел. Например, подумайте о часах. Фактическое время может быть числом от 1 до 12. Если вы добавите некоторое количество часов к времени, оно все равно должно быть в этом диапазоне, чтобы ответ имел смысл. Итак, 6 часов после 7 часов - это 1 час. Сложение работает нормально, за исключением того, что когда мы достигаем 12, мы возвращаемся к 1. Интересно, что умножение тоже работает. Если мы ждем 6 блоков по 5 часов, начиная с 7 часов, сколько сейчас времени? Что ж, это 30 часов, мод 12 - это 6 часов, плюс 7 - 1 час.

Как и в случае с целочисленной и рациональной версиями арифметики, в этой системе всегда есть аддитивные обратные. Любые два числа, сумма которых равна b, равны нулю по арифметическому модулю b. Итак, если a + c = b, то по модулю b земли мы можем сказать, что c = -a. Поскольку JavaScript дает нам отрицание правильного модуля, добавление b дает нам желаемое число! Когда мы снова модифицируем на b, ничего не меняется, поскольку искомое число уже меньше b.

Итак, поехали! Большая проблема с модулем JavaScript и как ее исправить!

Дальнейшее чтение:

Полугруппы, Кольца и Поля

p.s. средний, пожалуйста, внедрите поддержку LaTeX k thx.