Back to index

glibc  2.9
Defines | Functions
mod_1.c File Reference
#include <gmp.h>
#include "gmp-impl.h"
#include "longlong.h"

Go to the source code of this file.

Defines

#define UMUL_TIME   1
#define UDIV_TIME   UMUL_TIME

Functions

mp_limb_t mpn_mod_1 (mp_srcptr dividend_ptr, mp_size_t dividend_size, mp_limb_t divisor_limb)

Define Documentation

#define UDIV_TIME   UMUL_TIME

Definition at line 34 of file mod_1.c.

#define UMUL_TIME   1

Definition at line 30 of file mod_1.c.


Function Documentation

mp_limb_t mpn_mod_1 ( mp_srcptr  dividend_ptr,
mp_size_t  dividend_size,
mp_limb_t  divisor_limb 
)

Definition at line 45 of file mod_1.c.

{
  mp_size_t i;
  mp_limb_t n1, n0, r;
  mp_limb_t dummy;

  /* Botch: Should this be handled at all?  Rely on callers?  */
  if (dividend_size == 0)
    return 0;

  /* If multiplication is much faster than division, and the
     dividend is large, pre-invert the divisor, and use
     only multiplications in the inner loop.  */

  /* This test should be read:
       Does it ever help to use udiv_qrnnd_preinv?
        && Does what we save compensate for the inversion overhead?  */
  if (UDIV_TIME > (2 * UMUL_TIME + 6)
      && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME)
    {
      int normalization_steps;

      count_leading_zeros (normalization_steps, divisor_limb);
      if (normalization_steps != 0)
       {
         mp_limb_t divisor_limb_inverted;

         divisor_limb <<= normalization_steps;

         /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
            result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
            most significant bit (with weight 2**N) implicit.  */

         /* Special case for DIVISOR_LIMB == 100...000.  */
         if (divisor_limb << 1 == 0)
           divisor_limb_inverted = ~(mp_limb_t) 0;
         else
           udiv_qrnnd (divisor_limb_inverted, dummy,
                     -divisor_limb, 0, divisor_limb);

         n1 = dividend_ptr[dividend_size - 1];
         r = n1 >> (BITS_PER_MP_LIMB - normalization_steps);

         /* Possible optimization:
            if (r == 0
            && divisor_limb > ((n1 << normalization_steps)
                          | (dividend_ptr[dividend_size - 2] >> ...)))
            ...one division less... */

         for (i = dividend_size - 2; i >= 0; i--)
           {
             n0 = dividend_ptr[i];
             udiv_qrnnd_preinv (dummy, r, r,
                             ((n1 << normalization_steps)
                              | (n0 >> (BITS_PER_MP_LIMB - normalization_steps))),
                             divisor_limb, divisor_limb_inverted);
             n1 = n0;
           }
         udiv_qrnnd_preinv (dummy, r, r,
                          n1 << normalization_steps,
                          divisor_limb, divisor_limb_inverted);
         return r >> normalization_steps;
       }
      else
       {
         mp_limb_t divisor_limb_inverted;

         /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
            result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
            most significant bit (with weight 2**N) implicit.  */

         /* Special case for DIVISOR_LIMB == 100...000.  */
         if (divisor_limb << 1 == 0)
           divisor_limb_inverted = ~(mp_limb_t) 0;
         else
           udiv_qrnnd (divisor_limb_inverted, dummy,
                     -divisor_limb, 0, divisor_limb);

         i = dividend_size - 1;
         r = dividend_ptr[i];

         if (r >= divisor_limb)
           r = 0;
         else
           i--;

         for (; i >= 0; i--)
           {
             n0 = dividend_ptr[i];
             udiv_qrnnd_preinv (dummy, r, r,
                             n0, divisor_limb, divisor_limb_inverted);
           }
         return r;
       }
    }
  else
    {
      if (UDIV_NEEDS_NORMALIZATION)
       {
         int normalization_steps;

         count_leading_zeros (normalization_steps, divisor_limb);
         if (normalization_steps != 0)
           {
             divisor_limb <<= normalization_steps;

             n1 = dividend_ptr[dividend_size - 1];
             r = n1 >> (BITS_PER_MP_LIMB - normalization_steps);

             /* Possible optimization:
               if (r == 0
               && divisor_limb > ((n1 << normalization_steps)
                             | (dividend_ptr[dividend_size - 2] >> ...)))
               ...one division less... */

             for (i = dividend_size - 2; i >= 0; i--)
              {
                n0 = dividend_ptr[i];
                udiv_qrnnd (dummy, r, r,
                           ((n1 << normalization_steps)
                            | (n0 >> (BITS_PER_MP_LIMB - normalization_steps))),
                           divisor_limb);
                n1 = n0;
              }
             udiv_qrnnd (dummy, r, r,
                       n1 << normalization_steps,
                       divisor_limb);
             return r >> normalization_steps;
           }
       }
      /* No normalization needed, either because udiv_qrnnd doesn't require
        it, or because DIVISOR_LIMB is already normalized.  */

      i = dividend_size - 1;
      r = dividend_ptr[i];

      if (r >= divisor_limb)
       r = 0;
      else
       i--;

      for (; i >= 0; i--)
       {
         n0 = dividend_ptr[i];
         udiv_qrnnd (dummy, r, r, n0, divisor_limb);
       }
      return r;
    }
}

Here is the call graph for this function: