#14704: Use GMP's mpz_t for bitsets
-------------------------------+--------------------------------------------
Reporter: Stefan | Owner: jason
Type: enhancement | Status: new
Priority: minor | Milestone: sage-wishlist
Component: misc | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
-------------------------------+--------------------------------------------
Comment (by leif):
Replying to [comment:10 leif]:
> Note that GMP operates on limbs, so the (logical) "size" of a plain
`mpz_t` bitset would always be a multiple of `BITS_PER_LIMB`. (And we
certainly don't need the "sign" of a bitset; GMP's treatment may even
disturb.)
Just to elaborate a bit the subtle issues one has to take care of:
{{{
#!c
#include <gmp.h>
int main(void)
{
mpz_t bs;
int i;
mpz_init2(bs,(mp_bitcnt_t)(1UL<<16)); // 2^16 *bits*
gmp_printf("empty bitset:\n"
" size=%d alloc=%d value=%Zd popcnt=%lu\n",
bs[0]._mp_size,
bs[0]._mp_alloc,
bs,
(unsigned long)mpz_popcount(bs));
mpz_com(bs,bs); // complement
gmp_printf("empty bitset complemented:\n"
" size=%d alloc=%d value=... popcnt=%lu\n",
bs[0]._mp_size,
bs[0]._mp_alloc,
/* bs, */
(unsigned long)mpz_popcount(bs));
// restore logical size:
bs[0]._mp_size=1024; // 64-bit *limbs*; 2^16=64*1024
gmp_printf("with (logical) size \"restored\":\n"
" size=%d alloc=%d value=... popcnt=%lu\n",
bs[0]._mp_size,
bs[0]._mp_alloc,
/* bs, */
(unsigned long)mpz_popcount(bs));
// (construct) complement (of empty bitset) "manually":
for(i=0;i<1024;i++)
bs[0]._mp_d[i]=~0UL;
gmp_printf("empty bitset manually complemented:\n"
" size=%d alloc=%d value=... popcnt=%lu\n",
bs[0]._mp_size,
bs[0]._mp_alloc,
/* bs, */
(unsigned long)mpz_popcount(bs));
mpz_clear(bs);
return 0;
}
}}}
gives
{{{
empty bitset:
size=0 alloc=1024 value=0 popcnt=0
empty bitset complemented:
size=-1 alloc=1024 value=... popcnt=18446744073709551615
with (logical) size "restored":
size=1024 alloc=1024 value=... popcnt=1
empty bitset manually complemented:
size=1024 alloc=1024 value=... popcnt=65536
}}}
(Note that I've "hardcoded" 64-bit limbs / assumption is that
`sizeof(long)==8`.)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14704#comment:11>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
