[gecode-users] unsigned 32bit representation, additions

[Christian Schulte]

Hi Serg,

 

For the time being there is not much that you can do about this. And Gecode cannot be easily recompiled using unsigned ints (or 64 bit integers for that matter). I think some people have been experimenting with arbitrary precision integers as well as bit vectors but I do not know how far that got. Anybody?

 

Best

Christian

 

--

Christian Schulte, www.gecode.org/~schulte

Professor of Computer Science, KTH, cschulte at kth.se

Expert Researcher, SICS, cschulte at sics.se

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf Of Serg Buslovsky
Sent: Wednesday, March 11, 2015 6:54 AM
To: users at gecode.org
Subject: [gecode-users] unsigned 32bit representation, additions

 

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/f05e4f54/attachment.html>