mu_div_qr.c
上传用户:qaz666999
上传日期:2022-08-06
资源大小:2570k
文件大小:11k
源码类别:

数学计算

开发平台:

Unix_Linux

  1. /* mpn_mu_div_qr, mpn_preinv_mu_div_qr.
  2.    Compute Q = floor(N / D) and R = N-QD.  N is nn limbs and D is dn limbs and
  3.    must be normalized, and Q must be nn-dn limbs.  The requirement that Q is
  4.    nn-dn limbs (and not nn-dn+1 limbs) was put in place in order to allow us to
  5.    let N be unmodified during the operation.
  6.    Contributed to the GNU project by Torbjorn Granlund.
  7.    THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES.  IT IS ONLY
  8.    SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES.  IN FACT, IT IS ALMOST
  9.    GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE.
  10. Copyright 2005, 2006, 2007, 2009, 2010 Free Software Foundation, Inc.
  11. This file is part of the GNU MP Library.
  12. The GNU MP Library is free software; you can redistribute it and/or modify
  13. it under the terms of the GNU Lesser General Public License as published by
  14. the Free Software Foundation; either version 3 of the License, or (at your
  15. option) any later version.
  16. The GNU MP Library is distributed in the hope that it will be useful, but
  17. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  18. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  19. License for more details.
  20. You should have received a copy of the GNU Lesser General Public License
  21. along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  22. /*
  23.    The idea of the algorithm used herein is to compute a smaller inverted value
  24.    than used in the standard Barrett algorithm, and thus save time in the
  25.    Newton iterations, and pay just a small price when using the inverted value
  26.    for developing quotient bits.  This algorithm was presented at ICMS 2006.
  27. */
  28. /* CAUTION: This code and the code in mu_divappr_q.c should be edited in sync.
  29.  Things to work on:
  30.   * This isn't optimal when the quotient isn't needed, as it might take a lot
  31.     of space.  The computation is always needed, though, so there is no time to
  32.     save with special code.
  33.   * The itch/scratch scheme isn't perhaps such a good idea as it once seemed,
  34.     demonstrated by the fact that the mpn_invertappr function's scratch needs
  35.     mean that we need to keep a large allocation long after it is needed.
  36.     Things are worse as mpn_mul_fft does not accept any scratch parameter,
  37.     which means we'll have a large memory hole while in mpn_mul_fft.  In
  38.     general, a peak scratch need in the beginning of a function isn't
  39.     well-handled by the itch/scratch scheme.
  40. */
  41. #ifdef STAT
  42. #undef STAT
  43. #define STAT(x) x
  44. #else
  45. #define STAT(x)
  46. #endif
  47. #include <stdlib.h> /* for NULL */
  48. #include "gmp.h"
  49. #include "gmp-impl.h"
  50. /* FIXME: The MU_DIV_QR_SKEW_THRESHOLD was not analysed properly.  It gives a
  51.    speedup according to old measurements, but does the decision mechanism
  52.    really make sense?  It seem like the quotient between dn and qn might be
  53.    what we really should be checking.  */
  54. #ifndef MU_DIV_QR_SKEW_THRESHOLD
  55. #define MU_DIV_QR_SKEW_THRESHOLD 100
  56. #endif
  57. #ifdef CHECK /* FIXME: Enable in minithres */
  58. #undef  MU_DIV_QR_SKEW_THRESHOLD
  59. #define MU_DIV_QR_SKEW_THRESHOLD 1
  60. #endif
  61. static mp_limb_t mpn_mu_div_qr2 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
  62. mp_limb_t
  63. mpn_mu_div_qr (mp_ptr qp,
  64.        mp_ptr rp,
  65.        mp_srcptr np,
  66.        mp_size_t nn,
  67.        mp_srcptr dp,
  68.        mp_size_t dn,
  69.        mp_ptr scratch)
  70. {
  71.   mp_size_t qn;
  72.   mp_limb_t cy, qh;
  73.   qn = nn - dn;
  74.   if (qn + MU_DIV_QR_SKEW_THRESHOLD < dn)
  75.     {
  76.       /* |______________|_ign_first__|   dividend   nn
  77. |_______|_ign_first__|   divisor   dn
  78. |______|      quotient (prel)   qn
  79.  |___________________|   quotient * ignored-divisor-part  dn-1
  80.       */
  81.       /* Compute a preliminary quotient and a partial remainder by dividing the
  82.  most significant limbs of each operand.  */
  83.       qh = mpn_mu_div_qr2 (qp, rp + nn - (2 * qn + 1),
  84.    np + nn - (2 * qn + 1), 2 * qn + 1,
  85.    dp + dn - (qn + 1), qn + 1,
  86.    scratch);
  87.       /* Multiply the quotient by the divisor limbs ignored above.  */
  88.       if (dn - (qn + 1) > qn)
  89. mpn_mul (scratch, dp, dn - (qn + 1), qp, qn);  /* prod is dn-1 limbs */
  90.       else
  91. mpn_mul (scratch, qp, qn, dp, dn - (qn + 1));  /* prod is dn-1 limbs */
  92.       if (qh)
  93. cy = mpn_add_n (scratch + qn, scratch + qn, dp, dn - (qn + 1));
  94.       else
  95. cy = 0;
  96.       scratch[dn - 1] = cy;
  97.       cy = mpn_sub_n (rp, np, scratch, nn - (2 * qn + 1));
  98.       cy = mpn_sub_nc (rp + nn - (2 * qn + 1),
  99.        rp + nn - (2 * qn + 1),
  100.        scratch + nn - (2 * qn + 1),
  101.        qn + 1, cy);
  102.       if (cy)
  103. {
  104.   qh -= mpn_sub_1 (qp, qp, qn, 1);
  105.   mpn_add_n (rp, rp, dp, dn);
  106. }
  107.     }
  108.   else
  109.     {
  110.       qh = mpn_mu_div_qr2 (qp, rp, np, nn, dp, dn, scratch);
  111.     }
  112.   return qh;
  113. }
  114. static mp_limb_t
  115. mpn_mu_div_qr2 (mp_ptr qp,
  116. mp_ptr rp,
  117. mp_srcptr np,
  118. mp_size_t nn,
  119. mp_srcptr dp,
  120. mp_size_t dn,
  121. mp_ptr scratch)
  122. {
  123.   mp_size_t qn, in;
  124.   mp_limb_t cy, qh;
  125.   mp_ptr ip, tp;
  126.   ASSERT (dn > 1);
  127.   qn = nn - dn;
  128.   /* Compute the inverse size.  */
  129.   in = mpn_mu_div_qr_choose_in (qn, dn, 0);
  130.   ASSERT (in <= dn);
  131. #if 1
  132.   /* This alternative inverse computation method gets slightly more accurate
  133.      results.  FIXMEs: (1) Temp allocation needs not analysed (2) itch function
  134.      not adapted (3) mpn_invertappr scratch needs not met.  */
  135.   ip = scratch;
  136.   tp = scratch + in + 1;
  137.   /* compute an approximate inverse on (in+1) limbs */
  138.   if (dn == in)
  139.     {
  140.       MPN_COPY (tp + 1, dp, in);
  141.       tp[0] = 1;
  142.       mpn_invertappr (ip, tp, in + 1, NULL);
  143.       MPN_COPY_INCR (ip, ip + 1, in);
  144.     }
  145.   else
  146.     {
  147.       cy = mpn_add_1 (tp, dp + dn - (in + 1), in + 1, 1);
  148.       if (UNLIKELY (cy != 0))
  149. MPN_ZERO (ip, in);
  150.       else
  151. {
  152.   mpn_invertappr (ip, tp, in + 1, NULL);
  153.   MPN_COPY_INCR (ip, ip + 1, in);
  154. }
  155.     }
  156. #else
  157.   /* This older inverse computation method gets slightly worse results than the
  158.      one above.  */
  159.   ip = scratch;
  160.   tp = scratch + in;
  161.   /* Compute inverse of D to in+1 limbs, then round to 'in' limbs.  Ideally the
  162.      inversion function should do this automatically.  */
  163.   if (dn == in)
  164.     {
  165.       tp[in + 1] = 0;
  166.       MPN_COPY (tp + in + 2, dp, in);
  167.       mpn_invertappr (tp, tp + in + 1, in + 1, NULL);
  168.     }
  169.   else
  170.     {
  171.       mpn_invertappr (tp, dp + dn - (in + 1), in + 1, NULL);
  172.     }
  173.   cy = mpn_sub_1 (tp, tp, in + 1, GMP_NUMB_HIGHBIT);
  174.   if (UNLIKELY (cy != 0))
  175.     MPN_ZERO (tp + 1, in);
  176.   MPN_COPY (ip, tp + 1, in);
  177. #endif
  178.   qh = mpn_preinv_mu_div_qr (qp, rp, np, nn, dp, dn, ip, in, scratch + in);
  179.   return qh;
  180. }
  181. mp_limb_t
  182. mpn_preinv_mu_div_qr (mp_ptr qp,
  183.       mp_ptr rp,
  184.       mp_srcptr np,
  185.       mp_size_t nn,
  186.       mp_srcptr dp,
  187.       mp_size_t dn,
  188.       mp_srcptr ip,
  189.       mp_size_t in,
  190.       mp_ptr scratch)
  191. {
  192.   mp_size_t qn;
  193.   mp_limb_t cy, cx, qh;
  194.   mp_limb_t r;
  195.   mp_size_t tn, wn;
  196. #define tp           scratch
  197. #define scratch_out  (scratch + tn)
  198.   qn = nn - dn;
  199.   np += qn;
  200.   qp += qn;
  201.   qh = mpn_cmp (np, dp, dn) >= 0;
  202.   if (qh != 0)
  203.     mpn_sub_n (rp, np, dp, dn);
  204.   else
  205.     MPN_COPY (rp, np, dn);
  206.   if (qn == 0)
  207.     return qh; /* Degenerate use.  Should we allow this? */
  208.   while (qn > 0)
  209.     {
  210.       if (qn < in)
  211. {
  212.   ip += in - qn;
  213.   in = qn;
  214. }
  215.       np -= in;
  216.       qp -= in;
  217.       /* Compute the next block of quotient limbs by multiplying the inverse I
  218.  by the upper part of the partial remainder R.  */
  219.       mpn_mul_n (tp, rp + dn - in, ip, in); /* mulhi  */
  220.       cy = mpn_add_n (qp, tp + in, rp + dn - in, in); /* I's msb implicit */
  221.       ASSERT_ALWAYS (cy == 0);
  222.       qn -= in;
  223.       /* Compute the product of the quotient block and the divisor D, to be
  224.  subtracted from the partial remainder combined with new limbs from the
  225.  dividend N.  We only really need the low dn+1 limbs.  */
  226.       if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
  227. mpn_mul (tp, dp, dn, qp, in); /* dn+in limbs, high 'in' cancels */
  228.       else
  229. {
  230.   tn = mpn_mulmod_bnm1_next_size (dn + 1);
  231.   mpn_mulmod_bnm1 (tp, tn, dp, dn, qp, in, scratch_out);
  232.   wn = dn + in - tn; /* number of wrapped limbs */
  233.   if (wn > 0)
  234.     {
  235.       cy = mpn_sub_n (tp, tp, rp + dn - wn, wn);
  236.       cy = mpn_sub_1 (tp + wn, tp + wn, tn - wn, cy);
  237.       cx = mpn_cmp (rp + dn - in, tp + dn, tn - dn) < 0;
  238.       ASSERT_ALWAYS (cx >= cy);
  239.       mpn_incr_u (tp, cx - cy);
  240.     }
  241. }
  242.       r = rp[dn - in] - tp[dn];
  243.       /* Subtract the product from the partial remainder combined with new
  244.  limbs from the dividend N, generating a new partial remainder R.  */
  245.       if (dn != in)
  246. {
  247.   cy = mpn_sub_n (tp, np, tp, in); /* get next 'in' limbs from N */
  248.   cy = mpn_sub_nc (tp + in, rp, tp + in, dn - in, cy);
  249.   MPN_COPY (rp, tp, dn); /* FIXME: try to avoid this */
  250. }
  251.       else
  252. {
  253.   cy = mpn_sub_n (rp, np, tp, in); /* get next 'in' limbs from N */
  254. }
  255.       STAT (int i; int err = 0;
  256.     static int errarr[5]; static int err_rec; static int tot);
  257.       /* Check the remainder R and adjust the quotient as needed.  */
  258.       r -= cy;
  259.       while (r != 0)
  260. {
  261.   /* We loop 0 times with about 69% probability, 1 time with about 31%
  262.      probability, 2 times with about 0.6% probability, if inverse is
  263.      computed as recommended.  */
  264.   mpn_incr_u (qp, 1);
  265.   cy = mpn_sub_n (rp, rp, dp, dn);
  266.   r -= cy;
  267.   STAT (err++);
  268. }
  269.       if (mpn_cmp (rp, dp, dn) >= 0)
  270. {
  271.   /* This is executed with about 76% probability.  */
  272.   mpn_incr_u (qp, 1);
  273.   cy = mpn_sub_n (rp, rp, dp, dn);
  274.   STAT (err++);
  275. }
  276.       STAT (
  277.     tot++;
  278.     errarr[err]++;
  279.     if (err > err_rec)
  280.       err_rec = err;
  281.     if (tot % 0x10000 == 0)
  282.       {
  283. for (i = 0; i <= err_rec; i++)
  284.   printf ("  %d(%.1f%%)", errarr[i], 100.0*errarr[i]/tot);
  285. printf ("n");
  286.       }
  287.     );
  288.     }
  289.   return qh;
  290. }
  291. /* In case k=0 (automatic choice), we distinguish 3 cases:
  292.    (a) dn < qn:         in = ceil(qn / ceil(qn/dn))
  293.    (b) dn/3 < qn <= dn: in = ceil(qn / 2)
  294.    (c) qn < dn/3:       in = qn
  295.    In all cases we have in <= dn.
  296.  */
  297. mp_size_t
  298. mpn_mu_div_qr_choose_in (mp_size_t qn, mp_size_t dn, int k)
  299. {
  300.   mp_size_t in;
  301.   if (k == 0)
  302.     {
  303.       mp_size_t b;
  304.       if (qn > dn)
  305. {
  306.   /* Compute an inverse size that is a nice partition of the quotient.  */
  307.   b = (qn - 1) / dn + 1; /* ceil(qn/dn), number of blocks */
  308.   in = (qn - 1) / b + 1; /* ceil(qn/b) = ceil(qn / ceil(qn/dn)) */
  309. }
  310.       else if (3 * qn > dn)
  311. {
  312.   in = (qn - 1) / 2 + 1; /* b = 2 */
  313. }
  314.       else
  315. {
  316.   in = (qn - 1) / 1 + 1; /* b = 1 */
  317. }
  318.     }
  319.   else
  320.     {
  321.       mp_size_t xn;
  322.       xn = MIN (dn, qn);
  323.       in = (xn - 1) / k + 1;
  324.     }
  325.   return in;
  326. }
  327. mp_size_t
  328. mpn_mu_div_qr_itch (mp_size_t nn, mp_size_t dn, int mua_k)
  329. {
  330.   mp_size_t itch_local = mpn_mulmod_bnm1_next_size (dn + 1);
  331.   mp_size_t in = mpn_mu_div_qr_choose_in (nn - dn, dn, mua_k);
  332.   mp_size_t itch_out = mpn_mulmod_bnm1_itch (itch_local, dn, in);
  333.   return in + itch_local + itch_out;
  334. }