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:statewhere head and tail return the first element and the rest of a sequence, respectively (implemented in Boost.Preprocessor by_{i}= (seq_{i},res_{i});

state_{0}= (`bn2`

,true),

seq_{i+1}= tail(seq_{i}),

res_{i+1}=

· if not res_{i}, false,

· else (head(seq_{i}) ==`bn1i`

),

`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:stateHaving implemented_{i}= (seq_{i},res_{i}), with res_{i}one of

· −1 (`bn1`

smaller),

· 0 (`bn1`

==`bn2`

),

· +1 (`bn1`

smaller);

state_{0}= (`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.

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

Nice! Very Lisp-like.

ReplyDelete