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

数学计算

开发平台:

Unix_Linux

  1. /* mpn_mu_bdiv_q(qp,np,nn,dp,dn,tp) -- Compute {np,nn} / {dp,dn} mod B^nn.
  2.    storing the result in {qp,nn}.  Overlap allowed between Q and N; all other
  3.    overlap disallowed.
  4.    Contributed to the GNU project by Torbjorn Granlund.
  5.    THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES.  IT IS ONLY
  6.    SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES.  IN FACT, IT IS ALMOST
  7.    GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE.
  8. Copyright 2005, 2006, 2007, 2009, 2010 Free Software Foundation, Inc.
  9. This file is part of the GNU MP Library.
  10. The GNU MP Library is free software; you can redistribute it and/or modify
  11. it under the terms of the GNU Lesser General Public License as published by
  12. the Free Software Foundation; either version 3 of the License, or (at your
  13. option) any later version.
  14. The GNU MP Library is distributed in the hope that it will be useful, but
  15. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  16. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  17. License for more details.
  18. You should have received a copy of the GNU Lesser General Public License
  19. along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  20. /*
  21.    The idea of the algorithm used herein is to compute a smaller inverted value
  22.    than used in the standard Barrett algorithm, and thus save time in the
  23.    Newton iterations, and pay just a small price when using the inverted value
  24.    for developing quotient bits.  This algorithm was presented at ICMS 2006.
  25. */
  26. #include "gmp.h"
  27. #include "gmp-impl.h"
  28. /* N = {np,nn}
  29.    D = {dp,dn}
  30.    Requirements: N >= D
  31.  D >= 1
  32.  D odd
  33.  dn >= 2
  34.  nn >= 2
  35.  scratch space as determined by mpn_mu_bdiv_q_itch(nn,dn).
  36.    Write quotient to Q = {qp,nn}.
  37.    FIXME: When iterating, perhaps do the small step before loop, not after.
  38.    FIXME: Try to avoid the scalar divisions when computing inverse size.
  39.    FIXME: Trim allocation for (qn > dn) case, 3*dn might be possible.  In
  40.   particular, when dn==in, tp and rp could use the same space.
  41.    FIXME: Trim final quotient calculation to qn limbs of precision.
  42. */
  43. void
  44. mpn_mu_bdiv_q (mp_ptr qp,
  45.        mp_srcptr np, mp_size_t nn,
  46.        mp_srcptr dp, mp_size_t dn,
  47.        mp_ptr scratch)
  48. {
  49.   mp_size_t qn;
  50.   mp_size_t in;
  51.   int cy, c0;
  52.   mp_size_t tn, wn;
  53.   qn = nn;
  54.   ASSERT (dn >= 2);
  55.   ASSERT (qn >= 2);
  56.   if (qn > dn)
  57.     {
  58.       mp_size_t b;
  59.       /* |_______________________|   dividend
  60. |________|   divisor  */
  61. #define ip           scratch /* in */
  62. #define rp           (scratch + in) /* dn or rest >= binvert_itch(in) */
  63. #define tp           (scratch + in + dn) /* dn+in or next_size(dn) */
  64. #define scratch_out  (scratch + in + dn + tn) /* mulmod_bnm1_itch(next_size(dn)) */
  65.       /* Compute an inverse size that is a nice partition of the quotient.  */
  66.       b = (qn - 1) / dn + 1; /* ceil(qn/dn), number of blocks */
  67.       in = (qn - 1) / b + 1; /* ceil(qn/b) = ceil(qn / ceil(qn/dn)) */
  68.       /* Some notes on allocation:
  69.  When in = dn, R dies when mpn_mullo returns, if in < dn the low in
  70.  limbs of R dies at that point.  We could save memory by letting T live
  71.  just under R, and let the upper part of T expand into R. These changes
  72.  should reduce itch to perhaps 3dn.
  73.        */
  74.       mpn_binvert (ip, dp, in, rp);
  75.       cy = 0;
  76.       MPN_COPY (rp, np, dn);
  77.       np += dn;
  78.       mpn_mullo_n (qp, rp, ip, in);
  79.       qn -= in;
  80.       while (qn > in)
  81. {
  82.   if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
  83.     mpn_mul (tp, dp, dn, qp, in); /* mulhi, need tp[dn+in-1...in] */
  84.   else
  85.     {
  86.       tn = mpn_mulmod_bnm1_next_size (dn);
  87.       mpn_mulmod_bnm1 (tp, tn, dp, dn, qp, in, scratch_out);
  88.       wn = dn + in - tn; /* number of wrapped limbs */
  89.       if (wn > 0)
  90. {
  91.   c0 = mpn_sub_n (tp + tn, tp, rp, wn);
  92.   mpn_decr_u (tp + wn, c0);
  93. }
  94.     }
  95.   qp += in;
  96.   if (dn != in)
  97.     {
  98.       /* Subtract tp[dn-1...in] from partial remainder.  */
  99.       cy += mpn_sub_n (rp, rp + in, tp + in, dn - in);
  100.       if (cy == 2)
  101. {
  102.   mpn_incr_u (tp + dn, 1);
  103.   cy = 1;
  104. }
  105.     }
  106.   /* Subtract tp[dn+in-1...dn] from dividend.  */
  107.   cy = mpn_sub_nc (rp + dn - in, np, tp + dn, in, cy);
  108.   np += in;
  109.   mpn_mullo_n (qp, rp, ip, in);
  110.   qn -= in;
  111. }
  112.       /* Generate last qn limbs.
  113.  FIXME: It should be possible to limit precision here, since qn is
  114.  typically somewhat smaller than dn.  No big gains expected.  */
  115.       if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
  116. mpn_mul (tp, dp, dn, qp, in); /* mulhi, need tp[qn+in-1...in] */
  117.       else
  118. {
  119.   tn = mpn_mulmod_bnm1_next_size (dn);
  120.   mpn_mulmod_bnm1 (tp, tn, dp, dn, qp, in, scratch_out);
  121.   wn = dn + in - tn; /* number of wrapped limbs */
  122.   if (wn > 0)
  123.     {
  124.       c0 = mpn_sub_n (tp + tn, tp, rp, wn);
  125.       mpn_decr_u (tp + wn, c0);
  126.     }
  127. }
  128.       qp += in;
  129.       if (dn != in)
  130. {
  131.   cy += mpn_sub_n (rp, rp + in, tp + in, dn - in);
  132.   if (cy == 2)
  133.     {
  134.       mpn_incr_u (tp + dn, 1);
  135.       cy = 1;
  136.     }
  137. }
  138.       mpn_sub_nc (rp + dn - in, np, tp + dn, qn - (dn - in), cy);
  139.       mpn_mullo_n (qp, rp, ip, qn);
  140. #undef ip
  141. #undef rp
  142. #undef tp
  143. #undef scratch_out
  144.    }
  145.   else
  146.     {
  147.       /* |_______________________|   dividend
  148. |________________|   divisor  */
  149. #define ip           scratch /* in */
  150. #define tp           (scratch + in) /* qn+in or next_size(qn) or rest >= binvert_itch(in) */
  151. #define scratch_out  (scratch + in + tn)/* mulmod_bnm1_itch(next_size(qn)) */
  152.       /* Compute half-sized inverse.  */
  153.       in = qn - (qn >> 1);
  154.       mpn_binvert (ip, dp, in, tp);
  155.       mpn_mullo_n (qp, np, ip, in); /* low `in' quotient limbs */
  156.       if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
  157. mpn_mul (tp, dp, qn, qp, in); /* mulhigh */
  158.       else
  159. {
  160.   tn = mpn_mulmod_bnm1_next_size (qn);
  161.   mpn_mulmod_bnm1 (tp, tn, dp, qn, qp, in, scratch_out);
  162.   wn = qn + in - tn; /* number of wrapped limbs */
  163.   if (wn > 0)
  164.     {
  165.       c0 = mpn_cmp (tp, np, wn) < 0;
  166.       mpn_decr_u (tp + wn, c0);
  167.     }
  168. }
  169.       mpn_sub_n (tp, np + in, tp + in, qn - in);
  170.       mpn_mullo_n (qp + in, tp, ip, qn - in); /* high qn-in quotient limbs */
  171. #undef ip
  172. #undef tp
  173. #undef scratch_out
  174.     }
  175. }
  176. mp_size_t
  177. mpn_mu_bdiv_q_itch (mp_size_t nn, mp_size_t dn)
  178. {
  179.   mp_size_t qn, in, tn, itch_binvert, itch_out, itches;
  180.   mp_size_t b;
  181.   qn = nn;
  182.   if (qn > dn)
  183.     {
  184.       b = (qn - 1) / dn + 1; /* ceil(qn/dn), number of blocks */
  185.       in = (qn - 1) / b + 1; /* ceil(qn/b) = ceil(qn / ceil(qn/dn)) */
  186.       if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
  187. {
  188.   tn = dn + in;
  189.   itch_out = 0;
  190. }
  191.       else
  192. {
  193.   tn = mpn_mulmod_bnm1_next_size (dn);
  194.   itch_out = mpn_mulmod_bnm1_itch (tn, dn, in);
  195. }
  196.       itch_binvert = mpn_binvert_itch (in);
  197.       itches = dn + tn + itch_out;
  198.       return in + MAX (itches, itch_binvert);
  199.     }
  200.   else
  201.     {
  202.       in = qn - (qn >> 1);
  203.       if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
  204. {
  205.   tn = qn + in;
  206.   itch_out = 0;
  207. }
  208.       else
  209. {
  210.   tn = mpn_mulmod_bnm1_next_size (qn);
  211.   itch_out = mpn_mulmod_bnm1_itch (tn, qn, in);
  212. }
  213.       itch_binvert = mpn_binvert_itch (in);
  214.       itches = tn + itch_out;
  215.       return in + MAX (itches, itch_binvert);
  216.     }
  217. }