[gecode-users] unsigned 32bit representation, additions

[Serg Buslovsky]

Hi Group,

I'm thinking about the ways of implementing 32bit unsigned integer
representations in gecode model.
So I have 32 BoolVar's per uint32 representation, which are used to store
corresponding bits, then I can easily define bitwise operations on
"integers" by posting relation constraints on the bits.
The problem is with the addition.
My first approach was to add an IntVar, post linear constraints with powers
of 2 as coefficients to reconstruct integer from bits, however gecode
limits IntVar into signed int bounds and it doesn't fit.
The second approach was to just implement binary addition:
bool lsb = true;
for (int i=(INT_BITS-1); i>=0; i--) {
BoolVarArgs bits;
bits << bools[i] << x->bools[i];
if (!lsb) {
bits << result->bools[INT_BITS+i+1];
}
rel(*model, BOT_XOR, bits, result->bools[i]);
if (lsb) {
rel(*model, BOT_AND, bits, result->bools[INT_BITS+i]);
lsb = false;
} else {
linear(*model, bits, IRT_GQ, 2, result->bools[INT_BITS+i]);
}
}
(bools[i] - bits of the first "integer", x->bools[i] - bits of the second
"integer", result->bools[i] - bits of the resulting "integer",
result->bools[INT_BITS+i] - carry bits)
That works but it turned out to be very inefficient in practice, complexity
of the model is growing exponentially with this approach.

Any thoughts? Maybe there's a way to recompile gecode to use unsigned int
internally? Maybe there are ideas on better implementation of addition?
Maybe just some suggestion on another tool which uses unsigned ints
internally?


Thanks,
Serg
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20150311/fc4abe92/attachment.html>