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

数学计算

开发平台:

Unix_Linux

  1. /* mpn_gcdext -- Extended Greatest Common Divisor.
  2. Copyright 1996, 1998, 2000, 2001, 2002, 2003, 2004, 2005, 2008, 2009 Free Software
  3. Foundation, Inc.
  4. This file is part of the GNU MP Library.
  5. The GNU MP Library is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU Lesser General Public License as published by
  7. the Free Software Foundation; either version 3 of the License, or (at your
  8. option) any later version.
  9. The GNU MP Library is distributed in the hope that it will be useful, but
  10. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  11. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  12. License for more details.
  13. You should have received a copy of the GNU Lesser General Public License
  14. along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  15. #include "gmp.h"
  16. #include "gmp-impl.h"
  17. #include "longlong.h"
  18. /* Computes (r;b) = (a; b) M. Result is of size n + M->n +/- 1, and
  19.    the size is returned (if inputs are non-normalized, result may be
  20.    non-normalized too). Temporary space needed is M->n + n.
  21.  */
  22. static size_t
  23. hgcd_mul_matrix_vector (struct hgcd_matrix *M,
  24. mp_ptr rp, mp_srcptr ap, mp_ptr bp, mp_size_t n, mp_ptr tp)
  25. {
  26.   mp_limb_t ah, bh;
  27.   /* Compute (r,b) <-- (u00 a + u10 b, u01 a + u11 b) as
  28.      t  = u00 * a
  29.      r  = u10 * b
  30.      r += t;
  31.      t  = u11 * b
  32.      b  = u01 * a
  33.      b += t;
  34.   */
  35.   if (M->n >= n)
  36.     {
  37.       mpn_mul (tp, M->p[0][0], M->n, ap, n);
  38.       mpn_mul (rp, M->p[1][0], M->n, bp, n);
  39.     }
  40.   else
  41.     {
  42.       mpn_mul (tp, ap, n, M->p[0][0], M->n);
  43.       mpn_mul (rp, bp, n, M->p[1][0], M->n);
  44.     }
  45.   ah = mpn_add_n (rp, rp, tp, n + M->n);
  46.   if (M->n >= n)
  47.     {
  48.       mpn_mul (tp, M->p[1][1], M->n, bp, n);
  49.       mpn_mul (bp, M->p[0][1], M->n, ap, n);
  50.     }
  51.   else
  52.     {
  53.       mpn_mul (tp, bp, n, M->p[1][1], M->n);
  54.       mpn_mul (bp, ap, n, M->p[0][1], M->n);
  55.     }
  56.   bh = mpn_add_n (bp, bp, tp, n + M->n);
  57.   n += M->n;
  58.   if ( (ah | bh) > 0)
  59.     {
  60.       rp[n] = ah;
  61.       bp[n] = bh;
  62.       n++;
  63.     }
  64.   else
  65.     {
  66.       /* Normalize */
  67.       while ( (rp[n-1] | bp[n-1]) == 0)
  68. n--;
  69.     }
  70.   return n;
  71. }
  72. #define COMPUTE_V_ITCH(n) (2*(n) + 1)
  73. /* Computes |v| = |(g - u a)| / b, where u may be positive or
  74.    negative, and v is of the opposite sign. a, b are of size n, u and
  75.    v at most size n, and v must have space for n+1 limbs. */
  76. static mp_size_t
  77. compute_v (mp_ptr vp,
  78.    mp_srcptr ap, mp_srcptr bp, mp_size_t n,
  79.    mp_srcptr gp, mp_size_t gn,
  80.    mp_srcptr up, mp_size_t usize,
  81.    mp_ptr tp)
  82. {
  83.   mp_size_t size;
  84.   mp_size_t an;
  85.   mp_size_t bn;
  86.   mp_size_t vn;
  87.   ASSERT (n > 0);
  88.   ASSERT (gn > 0);
  89.   ASSERT (usize != 0);
  90.   size = ABS (usize);
  91.   ASSERT (size <= n);
  92.   an = n;
  93.   MPN_NORMALIZE (ap, an);
  94.   if (an >= size)
  95.     mpn_mul (tp, ap, an, up, size);
  96.   else
  97.     mpn_mul (tp, up, size, ap, an);
  98.   size += an;
  99.   size -= tp[size - 1] == 0;
  100.   ASSERT (gn <= size);
  101.   if (usize > 0)
  102.     {
  103.       /* |v| = -v = (u a - g) / b */
  104.       ASSERT_NOCARRY (mpn_sub (tp, tp, size, gp, gn));
  105.       MPN_NORMALIZE (tp, size);
  106.       if (size == 0)
  107. return 0;
  108.     }
  109.   else
  110.     { /* usize < 0 */
  111.       /* |v| = v = (c - u a) / b = (c + |u| a) / b */
  112.       mp_limb_t cy = mpn_add (tp, tp, size, gp, gn);
  113.       if (cy)
  114. tp[size++] = cy;
  115.     }
  116.   /* Now divide t / b. There must be no remainder */
  117.   bn = n;
  118.   MPN_NORMALIZE (bp, bn);
  119.   ASSERT (size >= bn);
  120.   vn = size + 1 - bn;
  121.   ASSERT (vn <= n + 1);
  122.   mpn_divexact (vp, tp, size, bp, bn);
  123.   vn -= (vp[vn-1] == 0);
  124.   return vn;
  125. }
  126. /* Temporary storage:
  127.    Initial division: Quotient of at most an - n + 1 <= an limbs.
  128.    Storage for u0 and u1: 2(n+1).
  129.    Storage for hgcd matrix M, with input ceil(n/2): 5 * ceil(n/4)
  130.    Storage for hgcd, input (n + 1)/2: 9 n/4 plus some.
  131.    When hgcd succeeds: 1 + floor(3n/2) for adjusting a and b, and 2(n+1) for the cofactors.
  132.    When hgcd fails: 2n + 1 for mpn_gcdext_subdiv_step, which is less.
  133.    For the lehmer call after the loop, Let T denote
  134.    GCDEXT_DC_THRESHOLD. For the gcdext_lehmer call, we need T each for
  135.    u, a and b, and 4T+3 scratch space. Next, for compute_v, we need T
  136.    for u, T+1 for v and 2T + 1 scratch space. In all, 7T + 3 is
  137.    sufficient for both operations.
  138. */
  139. /* Optimal choice of p seems difficult. In each iteration the division
  140.  * of work between hgcd and the updates of u0 and u1 depends on the
  141.  * current size of the u. It may be desirable to use a different
  142.  * choice of p in each iteration. Also the input size seems to matter;
  143.  * choosing p = n / 3 in the first iteration seems to improve
  144.  * performance slightly for input size just above the threshold, but
  145.  * degrade performance for larger inputs. */
  146. #define CHOOSE_P_1(n) ((n) / 2)
  147. #define CHOOSE_P_2(n) ((n) / 3)
  148. mp_size_t
  149. mpn_gcdext (mp_ptr gp, mp_ptr up, mp_size_t *usizep,
  150.     mp_ptr ap, mp_size_t an, mp_ptr bp, mp_size_t n)
  151. {
  152.   mp_size_t talloc;
  153.   mp_size_t scratch;
  154.   mp_size_t matrix_scratch;
  155.   mp_size_t ualloc = n + 1;
  156.   mp_size_t un;
  157.   mp_ptr u0;
  158.   mp_ptr u1;
  159.   mp_ptr tp;
  160.   TMP_DECL;
  161.   ASSERT (an >= n);
  162.   ASSERT (n > 0);
  163.   TMP_MARK;
  164.   /* FIXME: Check for small sizes first, before setting up temporary
  165.      storage etc. */
  166.   talloc = MPN_GCDEXT_LEHMER_N_ITCH(n);
  167.   /* For initial division */
  168.   scratch = an - n + 1;
  169.   if (scratch > talloc)
  170.     talloc = scratch;
  171.   if (ABOVE_THRESHOLD (n, GCDEXT_DC_THRESHOLD))
  172.     {
  173.       /* For hgcd loop. */
  174.       mp_size_t hgcd_scratch;
  175.       mp_size_t update_scratch;
  176.       mp_size_t p1 = CHOOSE_P_1 (n);
  177.       mp_size_t p2 = CHOOSE_P_2 (n);
  178.       mp_size_t min_p = MIN(p1, p2);
  179.       mp_size_t max_p = MAX(p1, p2);
  180.       matrix_scratch = MPN_HGCD_MATRIX_INIT_ITCH (n - min_p);
  181.       hgcd_scratch = mpn_hgcd_itch (n - min_p);
  182.       update_scratch = max_p + n - 1;
  183.       scratch = matrix_scratch + MAX(hgcd_scratch, update_scratch);
  184.       if (scratch > talloc)
  185. talloc = scratch;
  186.       /* Final mpn_gcdext_lehmer_n call. Need space for u and for
  187.  copies of a and b. */
  188.       scratch = MPN_GCDEXT_LEHMER_N_ITCH (GCDEXT_DC_THRESHOLD)
  189. + 3*GCDEXT_DC_THRESHOLD;
  190.       if (scratch > talloc)
  191. talloc = scratch;
  192.       /* Cofactors u0 and u1 */
  193.       talloc += 2*(n+1);
  194.     }
  195.   tp = TMP_ALLOC_LIMBS(talloc);
  196.   if (an > n)
  197.     {
  198.       mpn_tdiv_qr (tp, ap, 0, ap, an, bp, n);
  199.       if (mpn_zero_p (ap, n))
  200. {
  201.   MPN_COPY (gp, bp, n);
  202.   *usizep = 0;
  203.   TMP_FREE;
  204.   return n;
  205. }
  206.     }
  207.   if (BELOW_THRESHOLD (n, GCDEXT_DC_THRESHOLD))
  208.     {
  209.       mp_size_t gn = mpn_gcdext_lehmer_n(gp, up, usizep, ap, bp, n, tp);
  210.       TMP_FREE;
  211.       return gn;
  212.     }
  213.   MPN_ZERO (tp, 2*ualloc);
  214.   u0 = tp; tp += ualloc;
  215.   u1 = tp; tp += ualloc;
  216.   {
  217.     /* For the first hgcd call, there are no u updates, and it makes
  218.        some sense to use a different choice for p. */
  219.     /* FIXME: We could trim use of temporary storage, since u0 and u1
  220.        are not used yet. For the hgcd call, we could swap in the u0
  221.        and u1 pointers for the relevant matrix elements. */
  222.     struct hgcd_matrix M;
  223.     mp_size_t p = CHOOSE_P_1 (n);
  224.     mp_size_t nn;
  225.     mpn_hgcd_matrix_init (&M, n - p, tp);
  226.     nn = mpn_hgcd (ap + p, bp + p, n - p, &M, tp + matrix_scratch);
  227.     if (nn > 0)
  228.       {
  229. ASSERT (M.n <= (n - p - 1)/2);
  230. ASSERT (M.n + p <= (p + n - 1) / 2);
  231. /* Temporary storage 2 (p + M->n) <= p + n - 1 */
  232. n = mpn_hgcd_matrix_adjust (&M, p + nn, ap, bp, p, tp + matrix_scratch);
  233. MPN_COPY (u0, M.p[1][0], M.n);
  234. MPN_COPY (u1, M.p[1][1], M.n);
  235. un = M.n;
  236. while ( (u0[un-1] | u1[un-1] ) == 0)
  237.   un--;
  238.       }
  239.     else
  240.       {
  241. /* mpn_hgcd has failed. Then either one of a or b is very
  242.    small, or the difference is very small. Perform one
  243.    subtraction followed by one division. */
  244. mp_size_t gn;
  245. mp_size_t updated_un = 1;
  246. u1[0] = 1;
  247. /* Temporary storage 2n + 1 */
  248. n = mpn_gcdext_subdiv_step (gp, &gn, up, usizep, ap, bp, n,
  249.     u0, u1, &updated_un, tp, tp + n);
  250. if (n == 0)
  251.   {
  252.     TMP_FREE;
  253.     return gn;
  254.   }
  255. un = updated_un;
  256. ASSERT (un < ualloc);
  257.       }
  258.   }
  259.   while (ABOVE_THRESHOLD (n, GCDEXT_DC_THRESHOLD))
  260.     {
  261.       struct hgcd_matrix M;
  262.       mp_size_t p = CHOOSE_P_2 (n);
  263.       mp_size_t nn;
  264.       mpn_hgcd_matrix_init (&M, n - p, tp);
  265.       nn = mpn_hgcd (ap + p, bp + p, n - p, &M, tp + matrix_scratch);
  266.       if (nn > 0)
  267. {
  268.   mp_ptr t0;
  269.   t0 = tp + matrix_scratch;
  270.   ASSERT (M.n <= (n - p - 1)/2);
  271.   ASSERT (M.n + p <= (p + n - 1) / 2);
  272.   /* Temporary storage 2 (p + M->n) <= p + n - 1 */
  273.   n = mpn_hgcd_matrix_adjust (&M, p + nn, ap, bp, p, t0);
  274.   /* By the same analysis as for mpn_hgcd_matrix_mul */
  275.   ASSERT (M.n + un <= ualloc);
  276.   /* FIXME: This copying could be avoided by some swapping of
  277.    * pointers. May need more temporary storage, though. */
  278.   MPN_COPY (t0, u0, un);
  279.   /* Temporary storage ualloc */
  280.   un = hgcd_mul_matrix_vector (&M, u0, t0, u1, un, t0 + un);
  281.   ASSERT (un < ualloc);
  282.   ASSERT ( (u0[un-1] | u1[un-1]) > 0);
  283. }
  284.       else
  285. {
  286.   /* mpn_hgcd has failed. Then either one of a or b is very
  287.      small, or the difference is very small. Perform one
  288.      subtraction followed by one division. */
  289.   mp_size_t gn;
  290.   mp_size_t updated_un = un;
  291.   /* Temporary storage 2n + 1 */
  292.   n = mpn_gcdext_subdiv_step (gp, &gn, up, usizep, ap, bp, n,
  293.       u0, u1, &updated_un, tp, tp + n);
  294.   if (n == 0)
  295.     {
  296.       TMP_FREE;
  297.       return gn;
  298.     }
  299.   un = updated_un;
  300.   ASSERT (un < ualloc);
  301. }
  302.     }
  303.   if (UNLIKELY (mpn_cmp (ap, bp, n) == 0))
  304.     {
  305.       /* Must return the smallest cofactor, +u1 or -u0 */
  306.       int c;
  307.       MPN_COPY (gp, ap, n);
  308.       MPN_CMP (c, u0, u1, un);
  309.       ASSERT (c != 0);
  310.       if (c < 0)
  311. {
  312.   MPN_NORMALIZE (u0, un);
  313.   MPN_COPY (up, u0, un);
  314.   *usizep = -un;
  315. }
  316.       else
  317. {
  318.   MPN_NORMALIZE_NOT_ZERO (u1, un);
  319.   MPN_COPY (up, u1, un);
  320.   *usizep = un;
  321. }
  322.       TMP_FREE;
  323.       return n;
  324.     }
  325.   else if (mpn_zero_p (u0, un))
  326.     {
  327.       mp_size_t gn;
  328.       ASSERT (un == 1);
  329.       ASSERT (u1[0] == 1);
  330.       /* g = u a + v b = (u u1 - v u0) A + (...) B = u A + (...) B */
  331.       gn = mpn_gcdext_lehmer_n (gp, up, usizep, ap, bp, n, tp);
  332.       TMP_FREE;
  333.       return gn;
  334.     }
  335.   else
  336.     {
  337.       /* We have A = ... a + ... b
  338.  B =  u0 a +  u1 b
  339.  a = u1  A + ... B
  340.  b = -u0 A + ... B
  341.  with bounds
  342.    |u0|, |u1| <= B / min(a, b)
  343.  Compute g = u a + v b = (u u1 - v u0) A + (...) B
  344.  Here, u, v are bounded by
  345.  |u| <= b,
  346.  |v| <= a
  347.       */
  348.       mp_size_t u0n;
  349.       mp_size_t u1n;
  350.       mp_size_t lehmer_un;
  351.       mp_size_t lehmer_vn;
  352.       mp_size_t gn;
  353.       mp_ptr lehmer_up;
  354.       mp_ptr lehmer_vp;
  355.       int negate;
  356.       lehmer_up = tp; tp += n;
  357.       /* Call mpn_gcdext_lehmer_n with copies of a and b. */
  358.       MPN_COPY (tp, ap, n);
  359.       MPN_COPY (tp + n, bp, n);
  360.       gn = mpn_gcdext_lehmer_n (gp, lehmer_up, &lehmer_un, tp, tp + n, n, tp + 2*n);
  361.       u0n = un;
  362.       MPN_NORMALIZE (u0, u0n);
  363.       if (lehmer_un == 0)
  364. {
  365.   /* u == 0  ==>  v = g / b == 1  ==> g = - u0 A + (...) B */
  366.   MPN_COPY (up, u0, u0n);
  367.   *usizep = -u0n;
  368.   TMP_FREE;
  369.   return gn;
  370. }
  371.       lehmer_vp = tp;
  372.       /* Compute v = (g - u a) / b */
  373.       lehmer_vn = compute_v (lehmer_vp,
  374.      ap, bp, n, gp, gn, lehmer_up, lehmer_un, tp + n + 1);
  375.       if (lehmer_un > 0)
  376. negate = 0;
  377.       else
  378. {
  379.   lehmer_un = -lehmer_un;
  380.   negate = 1;
  381. }
  382.       u1n = un;
  383.       MPN_NORMALIZE (u1, u1n);
  384.       /* It's possible that u0 = 1, u1 = 0 */
  385.       if (u1n == 0)
  386. {
  387.   ASSERT (un == 1);
  388.   ASSERT (u0[0] == 1);
  389.   /* u1 == 0 ==> u u1 + v u0 = v */
  390.   MPN_COPY (up, lehmer_vp, lehmer_vn);
  391.   *usizep = negate ? lehmer_vn : - lehmer_vn;
  392.   TMP_FREE;
  393.   return gn;
  394. }
  395.       ASSERT (lehmer_un + u1n <= ualloc);
  396.       ASSERT (lehmer_vn + u0n <= ualloc);
  397.       /* Now u0, u1, u are non-zero. We may still have v == 0 */
  398.       /* Compute u u0 */
  399.       if (lehmer_un <= u1n)
  400. /* Should be the common case */
  401. mpn_mul (up, u1, u1n, lehmer_up, lehmer_un);
  402.       else
  403. mpn_mul (up, lehmer_up, lehmer_un, u1, u1n);
  404.       un = u1n + lehmer_un;
  405.       un -= (up[un - 1] == 0);
  406.       if (lehmer_vn > 0)
  407. {
  408.   mp_limb_t cy;
  409.   /* Overwrites old u1 value */
  410.   if (lehmer_vn <= u0n)
  411.     /* Should be the common case */
  412.     mpn_mul (u1, u0, u0n, lehmer_vp, lehmer_vn);
  413.   else
  414.     mpn_mul (u1, lehmer_vp, lehmer_vn, u0, u0n);
  415.   u1n = u0n + lehmer_vn;
  416.   u1n -= (u1[u1n - 1] == 0);
  417.   if (u1n <= un)
  418.     {
  419.       cy = mpn_add (up, up, un, u1, u1n);
  420.     }
  421.   else
  422.     {
  423.       cy = mpn_add (up, u1, u1n, up, un);
  424.       un = u1n;
  425.     }
  426.   up[un] = cy;
  427.   un += (cy != 0);
  428.   ASSERT (un < ualloc);
  429. }
  430.       *usizep = negate ? -un : un;
  431.       TMP_FREE;
  432.       return gn;
  433.     }
  434. }