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