> < ^ From:

< ^ Subject:

Dear GAP-forum,

Kevin O'Bryant asked:

I'm writing code relating to combinatorial game theory (in the style

of Berlekamp, Conway, and Guy's Winning Ways) in GAP. Has anyone out

there been down this road already? In particular, in C one may use "^"

for binary addition without carrying (Nim addition), an operation used

repeatedly (and recursively, so time is a BIG issue) and pervasively

in game theory calculations. Is there a quick way to do this in GAP?

By "quick", I mean faster than computing the binary expression, doing

the addition without carry term by term, and then converting back to a

Gap integer.

If you don't need the numerical value often, it might pay off to use blists

(binary lists). The manual section 'More about boolean lists' tells you

more. These are lists that contain only 'true' and 'false', if you

have created such a list, 'IsBlist' converts it implicitely to the internal

storage that takes just one bit per boolean value. For these blists there

are functions 'UnionBlist', 'IntersectionBlist' and 'DifferenceBlist' (note

that for these operations the blists must be of same length) from

which you can build the XOR-operation (i.e. binary addition without carrying)

easily. This should be certainly faster than using integers.

If this is still too slow you would need to add C routines, see the source

file 'blister.c' for information.

If the number of objects you're operating with is fairly small, you could

finally try to use numbers to represent the objects and to create a

nim-addition table, in which you look up the result.

Best,

Alexander Hulpke

> < [top]