16.1 Integer Internals

mpz_t variables represent integers using sign and magnitude, in space dynamically allocated and reallocated. The fields are as follows.

_mp_size

The number of limbs, or the negative of that when representing a negative integer. Zero is represented by _mp_size set to zero, in which case the _mp_d data is undefined.

_mp_d

A pointer to an array of limbs which is the magnitude. These are stored “little endian” as per the mpn functions, so _mp_d[0] is the least significant limb and _mp_d[ABS(_mp_size)-1] is the most significant. Whenever _mp_size is non-zero, the most significant limb is non-zero.

Currently there’s always at least one readable limb, so for instance mpz_get_ui can fetch _mp_d[0] unconditionally (though its value is undefined if _mp_size is zero).

_mp_alloc

_mp_alloc is the number of limbs currently allocated at _mp_d, and normally _mp_alloc >= ABS(_mp_size). When an mpz routine is about to (or might be about to) increase _mp_size, it checks _mp_alloc to see whether there’s enough space, and reallocates if not. MPZ_REALLOC is generally used for this.

mpz_t variables initialised with the mpz_roinit_n function or the MPZ_ROINIT_N macro have _mp_alloc = 0 but can have a non-zero _mp_size. They can only be used as read-only constants. See Integer Special Functions for details.

The various bitwise logical functions like mpz_and behave as if negative values were twos complement. But sign and magnitude is always used internally, and necessary adjustments are made during the calculations. Sometimes this isn’t pretty, but sign and magnitude are best for other routines.

Some internal temporary variables are setup with MPZ_TMP_INIT and these have _mp_d space obtained from TMP_ALLOC rather than the memory allocation functions. Care is taken to ensure that these are big enough that no reallocation is necessary (since it would have unpredictable consequences).

_mp_size and _mp_alloc are int, although mp_size_t is usually a long. This is done to make the fields just 32 bits on some 64 bits systems, thereby saving a few bytes of data space but still providing plenty of range.