comparator_propagate_generate.txt

Lexicographic comparison for vectors is well known:

x < y iff (x[-1] < y[-1]) | ((x[-1] == y[-1]) & (x[:-1] < y[:-1]))

This corresponds to a serial circuit with a depth linear in the number of elements.

However, it can easily be rewritten in a divide-and-conquer fashion:

x < y iff (x[i:] < y[i:]) | ((x[i:] == y[i:]) & (x[:i] < y[:i]))

If i is chosen to bisect the vector at each step, the circuit has logarithmic depth.

Note that to compute x < y we end up having to compute x == y in parallel.
It's common when designing a recursive algorithm that you have to "strengthen the
induction hypothesis" like this.

Anyway, if you write out the recursive function to construct this circuit, you
get something like the following:

def compare(x, y):
    assert len(x) == len(y)
    if len(x) == 1:
        return ~x[0] & y[0], ~x[0] ^ y[0]
    else:
        i = len(x) // 2
        lt_lo, eq_lo = compare(x[:i], y[:i])
        lt_hi, eq_hi = compare(x[i:], y[i:])
        return lt_hi | (eq_hi & lt_lo), eq_lo & eq_hi