Cpp bignum comparison

Equality of two C preprocessor bignums is trivially established (negatively) when the lengths of their representative sequences differ:

‎#define BN_EQUAL(bn1,bn2) \
‎BOOST_PP_IF( \
‎  BOOST_PP_NOT_EQUAL( \
‎    BOOST_PP_SEQ_SIZE(bn1),BOOST_PP_SEQ_SIZE(bn2)), \
‎  BN_EQUAL_CASE1, \
‎  BN_EQUAL_CASE2)(bn1,bn2)
‎
‎#define BN_EQUAL_CASE1(bn1,bn2) 0

When bn1 and bn2 have the same length, testing for equality involves doing the comparison digitwise. Boost.Preprocessor provides the macro BOOST_PP_SEQ_FOLD_LEFT to traverse the elements of a sequence. For instance, if bn1 is the sequence (bn11)...(bn1m), the call

BOOST_PP_SEQ_FOLD_LEFT(OP,state0,bn1))

expands to

OP(s,···OP(s,OP(s,state0,bn11),bn12)···,bn1m)

where the result of an invocation to OP is provided as a state argument to the next OP invocation (s is a lefotver parameter from older versions of Boost.Preprocessor and currently has no use). To perform digitwise equality comparison of bn1 and bn2 folding over bn1 we can use a state structure that contains the remaining of bn2 to be processed and the intermediate result of the comparison so far:

state_i = (seq_i,res_i);
state₀ = (bn2,true),
seq_i+1 = tail(seq_i),
res_i+1 =
‎ · if not res_i, false,
‎ · else (head(seq_i) == bn1i),

where head and tail return the first element and the rest of a sequence, respectively (implemented in Boost.Preprocessor by BOOST_PP_SEQ_HEAD and BOOST_PP_SEQ_TAIL). When the folding over bn1 is complete, the result member of the returned state structure contains the equality comparison output. In our implementation of this algorithm we choose to represent the state structure as a Boost.Preprocessor sequence:

‎‎#define BN_EQUAL_CASE2(bn1,bn2) \
‎BN_EQUAL_STATE_RESULT( \
‎  BOOST_PP_SEQ_FOLD_LEFT(BN_EQUAL_CASE2_OP,(bn2)(1),bn1))
‎
‎#define BN_EQUAL_CASE2_OP(s,state,x) \
‎BN_EQUAL_CASE2_OP_IMPL( \
‎  x, \
‎  BOOST_PP_SEQ_HEAD(BN_EQUAL_STATE_BN2(state)), \
‎  BN_EQUAL_STATE_BN2(state), \
‎  BN_EQUAL_STATE_RESULT(state))
‎
‎#define BN_EQUAL_CASE2_OP_IMPL(x,y,bn2,result) \
‎(BOOST_PP_SEQ_TAIL(bn2(0))) \
‎(BOOST_PP_IF(result,BOOST_PP_EQUAL(x,y),0))
‎
‎#define BN_EQUAL_STATE_BN2(state) BOOST_PP_SEQ_ELEM(0,state)
‎#define BN_EQUAL_STATE_RESULT(state) BOOST_PP_SEQ_ELEM(1,state)

"Less than" comparison can be implemented along a similar pattern:

‎#define BN_LESS(bn1,bn2) \
‎BOOST_PP_IF( \
‎  BOOST_PP_LESS(BOOST_PP_SEQ_SIZE(bn1),BOOST_PP_SEQ_SIZE(bn2)), \
‎  BN_LESS_CASE1, \
‎  BOOST_PP_IF( \
‎    BOOST_PP_LESS(BOOST_PP_SEQ_SIZE(bn2),BOOST_PP_SEQ_SIZE(bn1)), \
‎    BN_LESS_CASE2, \
‎    BN_LESS_CASE3))(bn1,bn2)
‎
‎#define BN_LESS_CASE1(bn1,bn2) 1
‎#define BN_LESS_CASE2(bn1,bn2) 0

The remaning BN_LESS_CASE3 applicable when bn1 and bn2 are of the same length can be again implemented by folding over bn1 using the following recursive state definition:

state_i = (seq_i,res_i), with res_i one of
‎ · −1 (bn1 smaller),
‎ · 0 (bn1 == bn2 ),
‎ · +1 (bn1 smaller);
state₀ = (bn2,0),
seq_i+1 = tail(seq_i),
res_i+1 =
‎ · if res_i ≠ 0, res_i,
‎ · else if bn1i < head(seq_i), −1,
‎ · else if bn1i > head(seq_i), +1,
‎ · else 0.

Having implemented BN_EQUAL and BN_LESS, the rest of comparison operations are trivially derived:

‎#define BN_NOT_EQUAL(bn1,bn2) BOOST_PP_NOT(BN_EQUAL(bn1,bn2))
‎#define BN_GREATER(bn1,bn2) BN_LESS(bn2,bn1)
‎#define BN_GREATER_EQUAL(bn1,bn2) BOOST_PP_NOT(BN_LESS(bn1,bn2))
‎#define BN_LESS_EQUAL(bn1,bn2) BOOST_PP_NOT(BN_LESS(bn2,bn1))

A complete implementation program of these macros is provided for your preprocessing pleasure. In a later entry we will continue with bignum arithmetic operations.