Что если взять замечательную математику (а именно линейные уравнения) и наш не менее замечательный JavaScript, а потом наложить одно на другое? То в условиях ограничений и специфики js-среды простая математическая задача может обернуться весьма любопытной и полной подводных js-камней проблемой. На прошедшей конференции HolyJS 19 в Москве одно такое линейное уравнение (среди прочих задач от компании SEMrush) наделало не мало шума.
И да, это снова рубрика Занимательного JavaScript'а: прошу под кат всех неравнодушных.
Конечно, все описанное ниже — это лишь несерьезная попытка симбиоза двух замечательных вещей с целью поразвлечься — не стоит воспринимать всерьез. И этого материала бы не было, если бы не живой интерес со стороны участников конференции, за что им отдельная благодарность!
1. Найдите все целые решения уравнения:
2. Найдите все целые решения уравнения:
Второе уравнение отличается от первого только дополнительной операцией в правой части.
Обратимся к первому уравнению. И для начала разберемся с приоритетами используемых операций, согласно таблице:
Мы берем побитовое отрицание от x, далее складываем с 9. Результат сложения сдвигаем побитово вправо на количество бит, равное результату деления 6 на 3.
Очевидно, проблема кроется в использовании побитовых операций над искомым x. Но чтобы найти какой-нибудь условный корень для дальнейших рассуждений, стоит попробовать привести уравнение к приближенному математическому аналогу.
Побитовые операции работают с операндами как со знаковыми 32-разрядными целыми числами. Побитовое NOT можно заменить на целочисленное отрицание от инкремента:
Побитовый сдвиг вправо (с сохранением знака) можно заменить на целочисленное деление на двойку в степени, равной операнду справа:
Конечно, эти замены очень условны, и мы об этом поговорим далее. А сейчас у нас получилось обычное линейное уравнение, единственный корень которого равен -24. Подставим значение в левую и правую части исходного уравнения:
Обе части равны, а значит все не так безысходно и -24 — это действительно решение.
Если мы нарисуем графики функций f1(x) = (8 -x) / 4 и f2(x) = -x / 3, то конечно обнаружим единственную точку пересечения двух прямых в x = -24.
Но мы сделали пару неравнозначных замен с побитовыми операциями в левом выражении, так что в действительности график функции f1 будет несколько отличаться. Для любых x значение функции будет целым числом, отличным от значения на непрерывной прямой f1 с возможным сдвигом в диапазоне от -1 до 1. Это значит, что область поиска решений мы можем ограничить слева и справа от -24, где значения функций f1 и f2 начинают отличаться более чем на единицу.
Чтобы найти границы области поиска, можно 1) решить неравенство с модулем, либо 2) поближе взглянуть на графики функций. Мы обнаружим, что x стоит искать на отрезке [-36, -12]:
Для перебора целых решений в некотором закрытом диапазоне [beg, end] напишем функцию findx:
Функция возвращает массив целых чисел, для которых значение переданной функции f сводится к true. Для поиска решений представим уравнение как js-функцию с использованием оператора равенства:
Таким образом, x = [-24, -21, -18, -15] — это искомые решения первого уравнения.
Перебор — это конечно успех, но давайте все-таки разберемся с графиком функции f1 до конца и решим уравнение графически. Тем более, что для решения не подразумевается обязательное владение консолью браузера.
Оператор побитового NOT просто отбрасывает дробную часть, тем самым результат -(x+1) будет округлен в меньшую сторону. С оператором побитового сдвига чуть посложнее. Его мы заменили на целочисленное деление, но в зависимости от знака делимого числа, эта операция округляет результат либо в меньшую, либо в большую сторону:
Однако мы знаем, что искомый x находится в диапазоне [-36, -12]. Соответственно, левый операнд побитового сдвига (8 -x) — в диапазоне [20, 44], то есть всегда положительный. Что в свою очередь означает целочисленное деление с округлением в меньшую сторону.
Разобравшись с характером операций, мы можем нарисовать верный график функции f1:
Мы найдем четыре точки пересечения функций в тех же координатах x = [-24, -21, -18, -15].
Итак, мы подобрались ко второму уравнению:
Оно отличается от первого добавлением побитового OR. Если правый операнд такой операции — ноль, то результатом будет просто значение левого операнда с отброшенной дробной частью.
Для начала пробежимся тем же перебором, только определимся с областью поиска. Так как теперь функция f2 имеет схожий характер с f1, то для надежности возможный сдвиг стоит просуммировать и ограничить поиск там, где функции отличаются по модулю уже более, чем на две единицы — это [-48, 0].
И мы получили те же ответы. Кроется подозрение, что все-таки что-то не так. А дело в том, что представив исходное уравнение такой js-функцией, мы объединили два выражения (левое и правое) через оператор равенства в одно. А оператор равенства имеет свой приоритет, который выше приоритета побитового OR. Функция тождественна следующей:
В этом случае побитовое OR не дает никакого эффекта, так как true | 0 = 1. Чтобы этого избежать, в теле функции необходимо явно указать, что мы сравниваем результаты двух подвыражений:
Количество решений прибавилось. Теперь посмотрим на графики функций. По аналогии с f1, «лесенкой» строится модифицированная функция f2:
Местами графики функций накладываются друг на друга, но нас интересуют только точки с целым значением координаты x: [-32, -29, -28, -26, -25, -24, -23, -22, -21, -19, -18, -15], всего 12 решений. Пересечения двух «лесенок» с шагом 3 и 4 можно найти и алгоритмически, если хочется.
В предлагаемой на конференции задаче был еще дополнительный вопрос: требовалось найти минимальное решение уравнения 2. При этом не сказано, что это обязательно целое, поэтому ответ x = -32 — оказывается неверным.
Найти решение грубым перебором здесь не получится, а вот решить графически очень просто. Это ближайшее значение x к -33 справа:
Кажется, что x = -32.(9). Но это все еще не верно. Так как наша среда — JavaScript, значит в представлении чисел мы ограничены используемым типом данных. Тип number представляет собой float64 — числа с плавающей точкой двойной точности (IEEE 754). Помнить об этом и назвать примерную точность было достаточно, чтобы получить плюшевую лису!
Как уже было сказано выше, побитовые операции конвертируют операнды в 32-разрядные числа, представленные последовательностью 0 и 1 — это диапазон [-2147483648, 2147483647]. Если же число в него не влезает, то старшие биты будут отброшены.
В первом уравнении это не играет никакой роли, так как в правой части нет побитовой операции. Но вот во втором эта конвертация чисел накладывает интересный эффект.
Например, число -24 будет представлено как:
Отрицательное значение числа получается путем инвертирования (побитовое NOT) бит в записи положительного числа с прибавлением единицы.
Любое число вне диапазона, после преобразования заканчивающееся на эту 32-разрядную последовательность, будет тождественно в бинарных операциях числу -24. Например, это числа:
В правой части уравнения перед побитовой операцией мы делим x на 3. Найдем такое x среди «эквивалентов» -24, которое нацело делится на 3. Ближайшее такое число — это 12884901864. Подставим его в уравнение:
Результат деления на 3 (-4294967288) не помещается в отведенные 32 разряда; при инвертировании битов в итоге теряется знак и остается только 8:
Дополнительно можно убедиться в верности результата, вызвав функцию eq2:
Если подумать, то рядом с этим корнем можно найти и проекции остальных 11 целых решений.
Таким образом, появляется огромное количество новых решений, а рассмотрен только ближайший положительный эквивалент -24. Тем не менее, это все уже не так интересно, как основная задача, и при разборе решений от участников подобные очень редкие ответы оценивались отдельно. Чтобы не путаться, можно внести ограничение на искомые целые числа в условие задачи как знаковые 32-разрядные.
А можно и не вносить! Тогда, чтобы найти наименьший корень, стоит обратить внимание на окрестности Number.MAX_SAFE_INTEGER с отрицательным знаком, так как это число целое и в предельной точности float64. Ну а дальше уже самостоятельно.
По итогам конференции большая часть участников решала задачу перебором, при этом диапазон для поиска был совершенно отличным по разным соображениям. Но как мы увидели, достаточно прогнать на ~50 целых числах. Многие попадали на ловушки с приоритетами операций. Кто-то тоже решал графически, что порадовало. Единицы удивили выходом за 32 разряда. Для продвижения дальше по задачам можно было воспользоваться и грубым перебором. Но чтобы получить дополнительный приз, необходимо было все таки провести некоторый около-математический анализ.
Очень надеюсь, что идея подобной нетипичной задачи в качестве развлечения для формата конференции Вам понравилась. За последний год у меня скопилось несколько таких «занимательных» JavaScript-задач. Я решил собрать их все в одном месте. Переходите по ссылке, если не боитесь: Unexpected Challenged JavaScript. Задачи Look Complex и Broken Pipe, которые также были предложены на конференции, уже выложены. Да, таких сборников много, но этот — мой! Всем еще раз спасибо.
И да, это снова рубрика Занимательного JavaScript'а: прошу под кат всех неравнодушных.
Предыдущие задачи
Конечно, все описанное ниже — это лишь несерьезная попытка симбиоза двух замечательных вещей с целью поразвлечься — не стоит воспринимать всерьез. И этого материала бы не было, если бы не живой интерес со стороны участников конференции, за что им отдельная благодарность!
Формулировка
1. Найдите все целые решения уравнения:
9 +~ x >> 6 / 3 = -x / 3
2. Найдите все целые решения уравнения:
9 +~ x >> 6 / 3 = -x / 3 | 0
Второе уравнение отличается от первого только дополнительной операцией в правой части.
Математическое приближение
Обратимся к первому уравнению. И для начала разберемся с приоритетами используемых операций, согласно таблице:
(9 +(~ x)) >> (6 / 3) = -x / 3
Мы берем побитовое отрицание от x, далее складываем с 9. Результат сложения сдвигаем побитово вправо на количество бит, равное результату деления 6 на 3.
Очевидно, проблема кроется в использовании побитовых операций над искомым x. Но чтобы найти какой-нибудь условный корень для дальнейших рассуждений, стоит попробовать привести уравнение к приближенному математическому аналогу.
Побитовые операции работают с операндами как со знаковыми 32-разрядными целыми числами. Побитовое NOT можно заменить на целочисленное отрицание от инкремента:
(9 -(x + 1)) >> (6 / 3) = -x / 3
(8 - x) >> 2 = -x / 3
Побитовый сдвиг вправо (с сохранением знака) можно заменить на целочисленное деление на двойку в степени, равной операнду справа:
(8 - x) / 2^2 = -x / 3
(8 - x) / 4 = -x / 3
Конечно, эти замены очень условны, и мы об этом поговорим далее. А сейчас у нас получилось обычное линейное уравнение, единственный корень которого равен -24. Подставим значение в левую и правую части исходного уравнения:
9 +~ (-24) >> 6 / 3; // = 8
-(-24) / 3; // = 8
Обе части равны, а значит все не так безысходно и -24 — это действительно решение.
Перебор для ленивых
Если мы нарисуем графики функций f1(x) = (8 -x) / 4 и f2(x) = -x / 3, то конечно обнаружим единственную точку пересечения двух прямых в x = -24.
Но мы сделали пару неравнозначных замен с побитовыми операциями в левом выражении, так что в действительности график функции f1 будет несколько отличаться. Для любых x значение функции будет целым числом, отличным от значения на непрерывной прямой f1 с возможным сдвигом в диапазоне от -1 до 1. Это значит, что область поиска решений мы можем ограничить слева и справа от -24, где значения функций f1 и f2 начинают отличаться более чем на единицу.
Чтобы найти границы области поиска, можно 1) решить неравенство с модулем, либо 2) поближе взглянуть на графики функций. Мы обнаружим, что x стоит искать на отрезке [-36, -12]:
| (8 - x) / 4 + x / 3 | <= 1
Для перебора целых решений в некотором закрытом диапазоне [beg, end] напишем функцию findx:
const findx = (f, beg, end) =>
[...Array(end - beg + 1)].map((_, i) => i + beg).filter(f);
Функция возвращает массив целых чисел, для которых значение переданной функции f сводится к true. Для поиска решений представим уравнение как js-функцию с использованием оператора равенства:
let eq1 = x => 9 +~ x >> 6 / 3 == -x / 3;
findx(eq1, -36, -12); // [-24, -21, -18, -15]
Таким образом, x = [-24, -21, -18, -15] — это искомые решения первого уравнения.
Графическое решение
Перебор — это конечно успех, но давайте все-таки разберемся с графиком функции f1 до конца и решим уравнение графически. Тем более, что для решения не подразумевается обязательное владение консолью браузера.
Оператор побитового NOT просто отбрасывает дробную часть, тем самым результат -(x+1) будет округлен в меньшую сторону. С оператором побитового сдвига чуть посложнее. Его мы заменили на целочисленное деление, но в зависимости от знака делимого числа, эта операция округляет результат либо в меньшую, либо в большую сторону:
10 >> 2; // = 2
-10 >> 2; // = -3
Однако мы знаем, что искомый x находится в диапазоне [-36, -12]. Соответственно, левый операнд побитового сдвига (8 -x) — в диапазоне [20, 44], то есть всегда положительный. Что в свою очередь означает целочисленное деление с округлением в меньшую сторону.
Разобравшись с характером операций, мы можем нарисовать верный график функции f1:
Мы найдем четыре точки пересечения функций в тех же координатах x = [-24, -21, -18, -15].
Второе уравнение
Итак, мы подобрались ко второму уравнению:
9 +~ x >> 6 / 3 = -x / 3 | 0
Оно отличается от первого добавлением побитового OR. Если правый операнд такой операции — ноль, то результатом будет просто значение левого операнда с отброшенной дробной частью.
Для начала пробежимся тем же перебором, только определимся с областью поиска. Так как теперь функция f2 имеет схожий характер с f1, то для надежности возможный сдвиг стоит просуммировать и ограничить поиск там, где функции отличаются по модулю уже более, чем на две единицы — это [-48, 0].
let eq2 = x => 9 +~ x >> 6 / 3 == -x / 3 | 0;
findx(eq2, -48, 0); // [-24, -21, -18, -15]
И мы получили те же ответы. Кроется подозрение, что все-таки что-то не так. А дело в том, что представив исходное уравнение такой js-функцией, мы объединили два выражения (левое и правое) через оператор равенства в одно. А оператор равенства имеет свой приоритет, который выше приоритета побитового OR. Функция тождественна следующей:
x => (9 +~ x >> 6 / 3 == -x / 3) | 0;
В этом случае побитовое OR не дает никакого эффекта, так как true | 0 = 1. Чтобы этого избежать, в теле функции необходимо явно указать, что мы сравниваем результаты двух подвыражений:
let eq2 = x => (9 +~ x >> 6 / 3) == (-x / 3 | 0);
findx(eq2, -48, 0); // [-32, -29, -28, -26, -25, -24, -23, -22, -21, -19, -18, -15]
Количество решений прибавилось. Теперь посмотрим на графики функций. По аналогии с f1, «лесенкой» строится модифицированная функция f2:
Местами графики функций накладываются друг на друга, но нас интересуют только точки с целым значением координаты x: [-32, -29, -28, -26, -25, -24, -23, -22, -21, -19, -18, -15], всего 12 решений. Пересечения двух «лесенок» с шагом 3 и 4 можно найти и алгоритмически, если хочется.
Дополнительный вопрос
В предлагаемой на конференции задаче был еще дополнительный вопрос: требовалось найти минимальное решение уравнения 2. При этом не сказано, что это обязательно целое, поэтому ответ x = -32 — оказывается неверным.
Найти решение грубым перебором здесь не получится, а вот решить графически очень просто. Это ближайшее значение x к -33 справа:
Кажется, что x = -32.(9). Но это все еще не верно. Так как наша среда — JavaScript, значит в представлении чисел мы ограничены используемым типом данных. Тип number представляет собой float64 — числа с плавающей точкой двойной точности (IEEE 754). Помнить об этом и назвать примерную точность было достаточно, чтобы получить плюшевую лису!
Темная сторона побитовых операций
Как уже было сказано выше, побитовые операции конвертируют операнды в 32-разрядные числа, представленные последовательностью 0 и 1 — это диапазон [-2147483648, 2147483647]. Если же число в него не влезает, то старшие биты будут отброшены.
В первом уравнении это не играет никакой роли, так как в правой части нет побитовой операции. Но вот во втором эта конвертация чисел накладывает интересный эффект.
Например, число -24 будет представлено как:
11111111111111111111111111101000
Отрицательное значение числа получается путем инвертирования (побитовое NOT) бит в записи положительного числа с прибавлением единицы.
Любое число вне диапазона, после преобразования заканчивающееся на эту 32-разрядную последовательность, будет тождественно в бинарных операциях числу -24. Например, это числа:
4294967272 | 0; // -24
8589934568 | 0; // -24, prepend '1'
12884901864 | 0; // -24, prepend '10'
17179869160 | 0; // -24, prepend '11'
21474836456 | 0; // -24, prepend '100'
// ...
В правой части уравнения перед побитовой операцией мы делим x на 3. Найдем такое x среди «эквивалентов» -24, которое нацело делится на 3. Ближайшее такое число — это 12884901864. Подставим его в уравнение:
9 +~ 12884901864 >> 6 / 3 = -12884901864 / 3 | 0
9 +~ 12884901864 >> 2 = -4294967288 | 0
9 + 23 >> 2 = 8
8 = 8
Результат деления на 3 (-4294967288) не помещается в отведенные 32 разряда; при инвертировании битов в итоге теряется знак и остается только 8:
00000000000000000000000000001000
Дополнительно можно убедиться в верности результата, вызвав функцию eq2:
eq2(12884901864); // true
Если подумать, то рядом с этим корнем можно найти и проекции остальных 11 целых решений.
Таким образом, появляется огромное количество новых решений, а рассмотрен только ближайший положительный эквивалент -24. Тем не менее, это все уже не так интересно, как основная задача, и при разборе решений от участников подобные очень редкие ответы оценивались отдельно. Чтобы не путаться, можно внести ограничение на искомые целые числа в условие задачи как знаковые 32-разрядные.
А можно и не вносить! Тогда, чтобы найти наименьший корень, стоит обратить внимание на окрестности Number.MAX_SAFE_INTEGER с отрицательным знаком, так как это число целое и в предельной точности float64. Ну а дальше уже самостоятельно.
Заключение
По итогам конференции большая часть участников решала задачу перебором, при этом диапазон для поиска был совершенно отличным по разным соображениям. Но как мы увидели, достаточно прогнать на ~50 целых числах. Многие попадали на ловушки с приоритетами операций. Кто-то тоже решал графически, что порадовало. Единицы удивили выходом за 32 разряда. Для продвижения дальше по задачам можно было воспользоваться и грубым перебором. Но чтобы получить дополнительный приз, необходимо было все таки провести некоторый около-математический анализ.
Очень надеюсь, что идея подобной нетипичной задачи в качестве развлечения для формата конференции Вам понравилась. За последний год у меня скопилось несколько таких «занимательных» JavaScript-задач. Я решил собрать их все в одном месте. Переходите по ссылке, если не боитесь: Unexpected Challenged JavaScript. Задачи Look Complex и Broken Pipe, которые также были предложены на конференции, уже выложены. Да, таких сборников много, но этот — мой! Всем еще раз спасибо.
vintage
Самое маленькое, что мне удалось найти методом научного тыка: