[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
3.11 Efficiency
- Small Operands
-
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.
- Static Linking
-
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.
- Initializing and Clearing
-
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.
- Reallocations
-
An
mpz_t
ormpq_t
variable used to hold successively increasing values will have its memory repeatedlyrealloc
ed, which could be quite slow or could fragment memory, depending on the C library. If an application can estimate the final size thenmpz_init2
ormpz_realloc2
can be called to allocate the necessary space from the beginning (see section Initialization Functions).It doesn’t matter if a size set with
mpz_init2
ormpz_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 likempz_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
andsi
Functions-
The
ui
functions and the small number ofsi
functions exist for convenience and should be used where applicable. But if for example anmpz_t
contains a value that fits in anunsigned long
there’s no need extract it and call aui
function, just use the regularmpz
function. - In-Place Operations
-
mpz_abs
,mpq_abs
,mpf_abs
,mpz_neg
,mpq_neg
andmpf_neg
are fast when used for in-place operations likempz_abs(x,x)
, since in the current implementation only a single field ofx
needs changing. On suitable compilers (GCC for instance) this is inlined too.mpz_add_ui
,mpz_sub_ui
,mpf_add_ui
andmpf_sub_ui
benefit from an in-place operation likempz_add_ui(x,x,y)
, since usually only one or two limbs ofx
will need to be changed. The same applies to the full precisionmpz_add
etc ify
is small. Ify
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 likempz_mul(x,x,y)
will, unlessy
is only one limb, make a temporary copy ofx
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 likempz_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. - Divisibility Testing (Small Integers)
-
mpz_divisible_ui_p
andmpz_congruent_ui_p
are the best functions for testing whether anmpz_t
is divisible by an individual small integer. They use an algorithm which is faster thanmpz_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 any of 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 likempz_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). - Rational Arithmetic
-
The
mpq
functions operate onmpq_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
andmpq_denref
macros give access to the numerator and denominator to do things outside the scope of the suppliedmpq
functions. See section 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 thanmpq_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);
- Number Sequences
-
Functions like
mpz_fac_ui
,mpz_fib_ui
andmpz_bin_uiui
are designed for calculating isolated values. If a range of values is wanted it’s probably best to call to get a starting point and iterate from there. - Text Input/Output
-
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.
[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This document was generated on March 31, 2014 using texi2html 5.0.