Важнейшим из искусств для нас является не кино, а умножение (и деление). Хотя, конечно, это не искусство, а довольно рутинная операция. Замечательно, что можно делигировать полномочия по выполнению умножения электронным вычислительным машинам (компьютерам/орденадорам, если брать кальку с английского/французского).
Рассмотрим в этой статье одну задачку из дискретной математики. А после получения решения я вам покажу лайф-хак, как можно при изучении дискретной математики использовать excel или google sheets, чтобы пощупать логические схемы и устройства.
Итак, задача!
В матричном умножителе вместо элементов ""и"" поставили элементы ""или"". Можно ли получить с помощью этого умножителя произведение чисел, используя O(n) дополнительных элементов? Вы можете добавить эти элементы в произвольные места в схеме для умножителя.
Примечание. К сожалению, эта статья никак логически не вытекает из того, что было написано ранее, и уже вовсю использует основы дискретной математики. Так получилось, что у меня накопился материал по решению задачек в этой области, но начал я их публиковать с конца. Постараюсь снабдить все перекрестными ссылками и убрать это примечание
Законы де Фата Моргана
Замена в задаче элемента "и" на элемент "или" не должна вызывать сложностей, ведь именно этому посвящены законы де Моргана, которые каждый первокурсник, грызущий гранит дискретной математики, выучивает как "Отче Наш". В частности, используя привычное русскому человеку двойное отрицание (нет, я не откажусь от чашечки чая или варенья) мы увидим, что
- А И Б = НЕ( НЕ (А И Б)))= НЕ (НЕ(А) ИЛИ НЕ (Б))
А это значит, что достаточно перед входами всех элементов "или" поставить элементы "не", и после каждого выхода элемента "или" поставить элемент "не". Тогда полченная схема будет делать все то же самое, что и раньше (а мы будем пить чай с вареньем).
Но получится ли при этом влезть в "свадебный костюм" размерчика О(n)? Во-первых, n это число двоичных разрядов у первого и второго множителя (и матричный умножитель не матрицы умножает, а двоичные числа - просто схема его похожа на матрицу). Матричный умножитель выполняет умножение, точно также как третьекласник - в столбик. Поэтому, элементы "и" которые осуществляют умножение 0 и 1 используются n^2 раз (см. также рисунок 1 ниже, где приводится схема 4х разрядного умножителя, с 16ю элементами "и").
Значит, наивное применение двойного отрицания и законов де Моргана потребует от нас вставить в схему 3n^2 элементов "не" и в лимит O(n) мы не влезем. Квадрат от числа элементов растет гораздо быстрее чем само число элементов (спасибо, Кэп).
Поэтому дальнейших шаг при решении задачи является запрещенным приемом. Раз по условиям надо, значит как-то можно исхитриться и вставлять элементы "не" не везде.
Полный сумматор
В элементе, который у нас осуществляет суммирование три выхода и два выхода (см. Рисунок 2). На входы подаются слагаемые x1, x2 и бит переноса (carry flag) c (либо, на некоторых сумматорах вместо с подается 0 и соответствующий вход не изображен на рисунке 1).
На выходы попадает сумма по модулю 2 и бит переноса для результата, который вычисляется как медиана трех входов (каких значений на входе больше, те и пойдут в перенос). Нужно проверить, что будет с результатом, если на вход попадут не переменные, а их отрицания. Ведь от применения элементов "не" к разрядам перемножаемых чисел не уйти.
Оказываетеся, на выходе тогда тоже будут отрицания соответствующих операций! А значит, если на каждый сумматор приходят отрицания, и уходят отрицания, на каждый элемент "или" приходят отрицания и уходят отрицания, то по всей схеме умножителя, до самого конца пойдут отрицания операций с поступившими разрядами множителей. Тогда можно только еще нулевые остатки заменить на 1, и вместо полученных разрядов результата, взять их отрицания, чтобы получить правильный результат умножения!
Таким образом, ответ на задачу следующий:
Нужно заменить входящие переменные на их отрицания (это 2n элементов "не"), на те сумматоры, куда не поступали переносы (было зафиксирован вход - перенос=0), подать 1 (это еще n элементов "не"), и на выходе поставить отрицания на каждый разряд результата (еще 2n элементов "не"). Т.к. выходы сумматора mod(x+y+z,2), <x,y,z> самодуальные, на выходы матричного умножителя придут результаты, являющиеся отрицанием выходов умножителя. Всего нужно 5n отрицаний (или 4n отрицаний и n единиц). Ну а 5n =O(n), и предложенный способ проходит в требуемый лимит по числу элементов.
Практика - критерий истины
Такие абстрактные аргументы правильны и очень убедительны. Но если вас еще гложит червь сомнения - вдруг где-то на схеме мы пропустили переход, нарушающий нашу логику, то можно просто устроить модель сумматора в электронных таблицах!
Такая реализация не очень сложна, но очень поучительна. Если у вас не получится до конца, пишите в комментах, кину ссылку на google sheets. Если нужна консультация по дискретной математике, записывайтесь в комментах.