Range checker improvements

[bobbinth]

In the current implementation, the range checker component (described here) consists of two tables: 8-bit table and 16-bit table. We use a selector column to identify which table we are in.

This structure can be greatly simplified if we get rid of the 8-bit table entirely, and instead, use a single constraint to allow "jumps" between two consecutive rows of the 16-bit table to be at most 8. Denoting $\Delta v = v' - v$, the constraint would look as follows:

$$ \prod_{i=0}^8 (\Delta v - i) = 0 $$

This constraint would have degree 9, which is fine for us.

The advantages of this approach:

• The range checker becomes much simpler.
• We can get rid of 1 main trace column (the one that is used as the selector) and 1 auxiliary trace column (the one that is used for the 8-bit table).

The drawbacks of this approach:

• We'd need to increase the minimum trace length from ~1K rows to about ~8K rows. In my mind this is not really a drawback as the vast majority of programs are likely to be 8K rows or more. However, this will affect test runtimes, and we'll probably need to refactor our testing methodology to avoid increasing test times by 8x.

[bobbinth]

I think I figured out how we can make this work without having to increase the minimum trace length to 16K cycles (and maybe we can even decrease it to be smaller than 1K cycles).

The core of the idea in the original post is that we allow $\Delta v$ to be between $0$ and $8$ (both inclusive). This works but runs into limitations described in #906.

But what if instead we allow $\Delta v$ to be 9 discrete values (rather than a contiguous range). For example, it could be $0$, $1$, $2$, $4$, $8$, $16$, $32$, $64$, and $128$. The constraint needed to enforce these values would be:

$$ \Delta v \cdot (\Delta v - 1) \cdot (\Delta v - 2) \cdot (\Delta v - 4) \cdot (\Delta v - 8) \cdot (\Delta v - 16) \cdot (\Delta v - 32) \cdot (\Delta v - 64) \cdot (\Delta v - 128) = 0 $$

This is still a degree $9$ constraint, but now we can "jump" by up to 128 units between two adjacent values. The logic for filling-in bridge values would become a bit more complicated, but probably not hugely. The extra complexity would be that if say, the $\Delta v$ between two values had to be $57$, we'd need to insert several "bridge" rows - i.e., with deltas $32$, $16$, $8$, and $1$ - but this would still be better than what was proposed in the original post.

@tohrnii @grjte - what do you think?

[tohrnii]

Ah, makes sense.

[tohrnii]

Closed by #949