Fast Fourier Transform with Booleans

Abstract

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

Проект

Это была моя первая работа в 1985-1986 годах. Я работал на факультете прикладной математики университета. Логики кафедры математики, Роберт Исаакович Фрейдзон и другие, работали над проблемой NP-полноты. В частности, они пытались опровергнуть тезис о том, что поиск решения системы булевых уравнений является NP-полной проблемой.

Для проверки своих теории, им нужно было конструировать системы булевых уравнений, имеющих ровно одно решение. Разработанный ими подход был основан на простом целочисленном уравнении: A * B = C.

Каждое из трех чисел, A, B и C, может быть выражено как набор булевых пременных с использованием двоичного кода: (A1, A2, ...) * (B1, B2, ...) = (C1, C2, ...)

Целочисленное умножение может быть представлено системой уравнений, связывающих все эти булевы переменные: C1, A1, B1, C2, A2, B2, и т.д. Например, для 4-битных чисел одно из уравнений будет примерно таким: ¬A4 ⋀ B4 ⋁ A4 ⋀ ¬B4 = C8

Возьмем два простых числа, перемножим их и подставим произведение в качестве переменной C. Теперь у нас есть система булевых уравнений, которая имеет ровно одно решение: двоичные представления A и B. Выбор произвольно больших A и B позволяет нам создавать сколь угодно большие системы уравнений с единственным решением.

Задача

Я должен был написать программу на PL/I, которой давались бы два простых числа, и она бы генерировала бы все эти булевы уравнения. Добавочной целью было сделать систему уровнений как можно компактнее. Я решил использовать алгоритм умножения, основанный на быстром преобразовании Фурье. Алгоритм и сам по себе сложный, но, вдобавок ко всему, я должен был реализовывать его не напрямую. Вместо этого, я должен был написать генератор, который бы производил логические уравнения, которые, в свою очередь, уже бы реализовывали алгоритм.

Проблема

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

Решение

Я переписал программу с PL/I на язык макро-препроцессора PL/I. Этот макроязык был необычайно мощным: он сам был полноценным языком программирования. В новой версии мой алгоритм умножения был выражен в терминах основных логических операций, реализованных как макро-функции. Я сделал два набора этих базовых логических макросов: одна реализация OR(A,B) генерировала фрагмент логического выражения, например "A ⋁ B"; другая реализация не создавала строку, а просто исполняла выражение как есть. Одним параметром я мог заставить программу либо генерировать уравнения, либо выполнять логические операции! Я отладил алгоритм умножения в этом простом режиме. Я убедился, что он правильно вычисляет такие выражения, как 3 * 2 = 6. После этого я щелкнул переключателем, и программа начала генерировать правильные уравнения без дополнительной отладки.

%DECLARE (GenerateExpression) BIT;
%GenerateExpression = 1;

%DECLARE ExpressionType CHAR;
%IF GenerateExpression
  %THEN ExpressionType = 'CHAR';
  %ELSE ExpressionType = 'BIT';

%AND: PROCEDURE (Left, Right) RETURNS CHAR;
  DECLARE (Left, Right) CHAR;
  DECLARE Code CHAR;

  IF GenerateExpression
    THEN Code = '''(''' || Left || ''' || '' ⋀ '' || ''' || Right || ''')''';
    ELSE Code = '(' || Left || ' & ' || Right || ')';

  RETURN Code;
%END AND;

%OR: // Similar to AND

%NOT: // Similar to AND
...

Теперь давайте воспользуемся этими макросами:

PROCEDURE SOME_LOGIC(A, B,C) RETURNS ExpressionType;
   DECLARE (A, B, C) ExpressionType;
   RETURN OR(AND(A, NOT(B)), C);
END;

Если значение GenerateExpression равно False, эта программа сгенерирует следующий код:

PROCEDURE SOME_LOGIC(A, B, C) RETURNS BIT;
  DECLARE (A, B, C) BIT;
  RETURN ((A & ^(B)) | C);
END;

Соответственно, PUT LIST 'RESULT: ', SOME_LOGIC(1, 1, 0); напечатает:

RESULT: 0

Если же GenerateExpression равно Тrue, то программа сгенерирует:

PROCEDURE SOME_LOGIC(A, B, C) RETURNS CHAR;
  DECLARE (A, B, C) CHAR;
  RETURN '(' || '(' || A || ' ⋀ ' || '¬(' || B || ')' || ')' || ' ⋁ ' || C || ')';
END;

и PUT LIST 'RESULT: ', SOME_LOGIC('X', 'Y', 'Z'); напечатает:

RESULT: ((X ⋀ ¬(Y)) ⋁ Z)

Та же программа, но совершенно другой тип поведения.

Не по существу

В 1992 году я был в Америке в командировке. Роберт Исаакович Фрейдзон, мой бывший профессор математической логики, в то время жил в Бостоне. Мы разговаривали с ним по телефону, и я ему сказал, что моя поездка заканчивается и я еду домой. Его реакция была: «Ты охуел что-ли? Тебе же дана возможность изменить всю свою жизнь! Послушай меня: не дури и найди способ остаться!»

Instead of figuring out how to debug my life, I popped on a plane and went home to be with my wife whose grandmother had died while I was in America. About two years later, when another opportunity presented itself, I got smarter and permanently substituted one variable in my professional career: the country of residence. Same programming languages, but an entirely different type of life.

Быстрое преобразование Фурье в булевой алгебре