On small operands, the time for function call overheads and memory allocation can be significant in comparison to actual calculation. This is unavoidable in a general purpose variable precision library, although GMP attempts to be as efficient as it can on both large and small operands.
On some CPUs, in particular the x86s, the static libgmp.a should be used for maximum speed, since the PIC code in the shared libgmp.so will have a small overhead on each function call and global data address. For many programs this will be insignificant, but for long calculations there’s a gain to be had.
Avoid excessive initializing and clearing of variables, since this can be quite time consuming, especially in comparison to otherwise fast operations like addition.
A language interpreter might want to keep a free list or stack of initialized variables ready for use. It should be possible to integrate something like that with a garbage collector too.
An mpz_t or mpq_t variable used to hold successively increasing
values will have its memory repeatedly realloced, which could be quite
slow or could fragment memory, depending on the C library. If an application
can estimate the final size then mpz_init2 or mpz_realloc2 can
be called to allocate the necessary space from the beginning
(see Initialization Functions).
It doesn’t matter if a size set with mpz_init2 or mpz_realloc2
is too small, since all functions will do a further reallocation if necessary.
Badly overestimating memory required will waste space though.
2exp Functions ¶It’s up to an application to call functions like mpz_mul_2exp when
appropriate. General purpose functions like mpz_mul make no attempt to
identify powers of two or other special forms, because such inputs will
usually be very rare and testing every time would be wasteful.
ui and si Functions ¶The ui functions and the small number of si functions exist for
convenience and should be used where applicable. But if for example an
mpz_t contains a value that fits in an unsigned long there’s no
need to extract it and call a ui function, just use the regular mpz
function.
mpz_abs, mpq_abs, mpf_abs, mpz_neg, mpq_neg
and mpf_neg are fast when used for in-place operations like
mpz_abs(x,x), since in the current implementation only a single field
of x needs changing. On suitable compilers (GCC for instance) this is
inlined too.
mpz_add_ui, mpz_sub_ui, mpf_add_ui and mpf_sub_ui
benefit from an in-place operation like mpz_add_ui(x,x,y), since
usually only one or two limbs of x will need to be changed. The same
applies to the full precision mpz_add etc if y is small. If
y is big then cache locality may be helped, but that’s all.
mpz_mul is currently the opposite, a separate destination is slightly
better. A call like mpz_mul(x,x,y) will, unless y is only one
limb, make a temporary copy of x before forming the result. Normally
that copying will only be a tiny fraction of the time for the multiply, so
this is not a particularly important consideration.
mpz_set, mpq_set, mpq_set_num, mpf_set, etc, make
no attempt to recognise a copy of something to itself, so a call like
mpz_set(x,x) will be wasteful. Naturally that would never be written
deliberately, but if it might arise from two pointers to the same object then
a test to avoid it might be desirable.
if (x != y) mpz_set (x, y);
Note that it’s never worth introducing extra mpz_set calls just to get
in-place operations. If a result should go to a particular variable then just
direct it there and let GMP take care of data movement.
mpz_divisible_ui_p and mpz_congruent_ui_p are the best functions
for testing whether an mpz_t is divisible by an individual small
integer. They use an algorithm which is faster than mpz_tdiv_ui, but
which gives no useful information about the actual remainder, only whether
it’s zero (or a particular value).
However when testing divisibility by several small integers, it’s best to take a remainder modulo their product, to save multi-precision operations. For instance to test whether a number is divisible by 23, 29 or 31 take a remainder modulo 23*29*31 = 20677 and then test that.
The division functions like mpz_tdiv_q_ui which give a quotient as well
as a remainder are generally a little slower than the remainder-only functions
like mpz_tdiv_ui. If the quotient is only rarely wanted then it’s
probably best to just take a remainder and then go back and calculate the
quotient if and when it’s wanted (mpz_divexact_ui can be used if the
remainder is zero).
The mpq functions operate on mpq_t values with no common factors
in the numerator and denominator. Common factors are checked-for and cast out
as necessary. In general, cancelling factors every time is the best approach
since it minimizes the sizes for subsequent operations.
However, applications that know something about the factorization of the values they’re working with might be able to avoid some of the GCDs used for canonicalization, or swap them for divisions. For example when multiplying by a prime it’s enough to check for factors of it in the denominator instead of doing a full GCD. Or when forming a big product it might be known that very little cancellation will be possible, and so canonicalization can be left to the end.
The mpq_numref and mpq_denref macros give access to the
numerator and denominator to do things outside the scope of the supplied
mpq functions. See Applying Integer Functions to Rationals.
The canonical form for rationals allows mixed-type mpq_t and integer
additions or subtractions to be done directly with multiples of the
denominator. This will be somewhat faster than mpq_add. For example,
/* mpq increment */ mpz_add (mpq_numref(q), mpq_numref(q), mpq_denref(q)); /* mpq += unsigned long */ mpz_addmul_ui (mpq_numref(q), mpq_denref(q), 123UL); /* mpq -= mpz */ mpz_submul (mpq_numref(q), mpq_denref(q), z);
Functions like mpz_fac_ui, mpz_fib_ui and mpz_bin_uiui
are designed for calculating isolated values. If a range of values is wanted
it’s probably best to get a starting point and iterate from there.
Hexadecimal or octal are suggested for input or output in text form. Power-of-2 bases like these can be converted much more efficiently than other bases, like decimal. For big numbers there’s usually nothing of particular interest to be seen in the digits, so the base doesn’t matter much.
Maybe we can hope octal will one day become the normal base for everyday use, as proposed by King Charles XII of Sweden and later reformers.