We can compare the magnitude of two unsigned BF numbers using a left-to-right lexicographic comparison. This is easily done with a simple state machine having three states, E (Equal), G (Greater) and L (Less). We start in state E, and stay there as long as the input bits from the two numbers are equal. As soon as we find a difference, we switch to state G or L, and stay there until all the input is processed. The final state gives us the result of the comparison.
Old State | Input X,Y | New State |
E | 0,0 | E |
E | 1,1 | E |
E | 1,0 | G |
E | 0,1 | L |
G | G | |
L | L |
Here's an example.
Input X | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
Input Y | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | |
State | E | E | E | E | E | E | E | L | L | L | L | L | L | L |
The final state L means that X < Y.
If we're using the convention for signed numbers suggested earlier that the boundary between positive and negative numbers is Fn+1/2, in order to find out the sign of a number we need to compare it with Fn+1/2. We've just discovered how to do comparison, so all we need is a way to compute Fn+1/2.
We found before that Fn+1/2 consists of every third bit starting from Fn-1, with a few terminating conditions. To compute this using a state machine, we just need a state that cycles through three different values, and output a 1 whenever it reaches one of those states.
The state transition table will look like this:
Old State | Output | New State |
0 | 0 | 1 |
1 | 1 | 2 |
2 | 0 | 0 |
Here's what running this machine produces for n = 10.
F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | F0 | |
State | 0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
Output |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
As with some of our earlier machines, we need to "or" the outputs for the F1 and F0 positions together to produce the final result:
F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Result | 0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
To perform a signed comparison, we first need to test the signs of the operands. If they have different signs, we immediately know the result – the positive one is greater than the negative one. If they have the same sign, the result is the same as an unsigned comparison of the operands.
We can implement this logic by prepending the sign bits to the operands and then performing an unsigned comparison of the resulting n+1 bit operands.
---