Fast Fourier Transform with Booleans

Abstract

This article describes an inventive debugging technique I used in the area of Mathematical Logic. If you don't care about mathematical logic, skip to the last two paragraphs.

Project

This was on my very first job in 1985-1986. I was working at the University Department of Applied Math. Logicians at the Department, Robert Freidson et al, were working on the problem of NP-Completeness. Specifically they were trying to disprove the thesis that finding a solution of a system of boolean equations is an NP-Complete problem.

To test their theories they needed to be able to construct systems of Boolean equations having exactly one solution. The approach they developed was based on this simple integer equation: A*B = C.

Each of the three numbers, A, B and C, can be expressed as a set of booleans using the binary notation:
(A1, A2, ...) * (B1, B2, ...) = (C1, C2, ...)

The integer multiplication can be represented by a system of equations connecting all these booleans: C1, A1, B1, C2, A2, B2, etc. For example, for 4-bit numbers one of the equations would be something like: ¬A4 ⋀ B4 ⋁ A4 ⋀ ¬B4 = C8

Let's take two primes, multiply them and substitute the product for C. Now we have a system of Boolean equations that has exactly one solution: the binary representations of A and B. Choosing arbitrarily large A and B allows us to produce arbitrarily large systems of equations with exactly one solution.

My assignment

I was supposed to write a program in PL/I, which given two primes would generate all these Boolean equations. An additional goal was to make the system as small as I could. I chose to use a multiplication algorithm based on Binary Fast Fourier Transform. The algorithm is complex as it is, but on top of that, I was not supposed to implement it as is. Rather, I was supposed to implement a generator, which would produce boolean equations, which in turn would implement the algorithm.

Challenge

I wrote the program. It was generating something, but even for very small primes it would produce very large numbers of equations and those equations were actually wrong: substituting the original primes did not satisfy the equations. I clearly had bugs in my generator. And I had no clue as to how to debug it: it would produce a ten-foot printout consisting of incomprehensible logical expressions, some of which were incorrect.

Solution

I rewrote the program from PL/I to the PL/I Macro Preprocessor language. That macro language was unusually powerful: it was itself a complete programming language. The new version expressed the multiplication algorithm in terms of basic Boolean operations implemented as Macro functions. I supplied two sets of those basic Boolean macros: one implementation of OR(A,B) would generate a piece of Boolean expression like A | B; the other implementation would actually execute the expression instead of generating a string. By flipping a switch I could make the program either generate equations or perform actual Boolean operations! I debugged it in the latter mode verifying that it was computing things like 3*2 = 6 correctly. Then I flipped the switch and the program started generating correct equations without any additional debugging.

%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
...

Now, let's use these macros:

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

If the value of GenerateExpression is False, this program will produce this code:

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

So PUT LIST 'RESULT: ', SOME_LOGIC(1, 1, 0); will print

RESULT: 0

If GenerateExpression is true, the program will produce this code:

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

so PUT LIST 'RESULT: ', SOME_LOGIC('X', 'Y', 'Z'); will print:

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

Same program, but an entirely different type of behavior.

Tangent

In 1992 I was in America on a business trip. Robert Freidson, my former Math Logic professor, lived in Boston at that moment. We were talking on the phone and I told him that my trip was ending and I was going home. His reaction was: "You must be fucked in the head! This is your opportunity to change your life. Listen to me: you must find a way to stay!"

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.