(gmp) Efficiency

Prev (gmp) Demonstration Programs Up (gmp) GMP Basics Next (gmp) Debugging
 
 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' or `mpq_t' variable used to hold successively increasing
      values will have its memory repeatedly `realloc'ed, 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 Initializing Integers).
 
      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 extract it and call a `ui' function, just
      use the regular `mpz' function.
 
 In-Place Operations
      `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.
 
 Divisibility Testing (Small Integers)
      `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 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 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).
 
 Rational Arithmetic
      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.
 
      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);
 
 Number Sequences
      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 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.
 
Prev (gmp) Demonstration Programs Up (gmp) GMP Basics Next (gmp) Debugging
automatically generated by info2html