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

数学计算

开发平台:

Unix_Linux

  1. /* mpn_perfect_power_p -- mpn perfect power detection.
  2.    Contributed to the GNU project by Martin Boij.
  3. Copyright 2009, 2010 Free Software 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. #define SMALL 20
  19. #define MEDIUM 100
  20. /*
  21.    Returns non-zero if {np,nn} == {xp,xn} ^ k.
  22.    Algorithm:
  23.        For s = 1, 2, 4, ..., s_max, compute the s least significant
  24.        limbs of {xp,xn}^k. Stop if they don't match the s least
  25.        significant limbs of {np,nn}.
  26. */
  27. static int
  28. pow_equals (mp_srcptr np, mp_size_t nn,
  29.     mp_srcptr xp,mp_size_t xn,
  30.     mp_limb_t k, mp_bitcnt_t f,
  31.     mp_ptr tp)
  32. {
  33.   mp_limb_t *tp2;
  34.   mp_bitcnt_t y, z, count;
  35.   mp_size_t i, bn;
  36.   int ans;
  37.   mp_limb_t h, l;
  38.   TMP_DECL;
  39.   ASSERT (nn > 1 || (nn == 1 && np[0] > 1));
  40.   ASSERT (np[nn - 1] > 0);
  41.   ASSERT (xn > 0);
  42.   if (xn == 1 && xp[0] == 1)
  43.     return 0;
  44.   z = 1 + (nn >> 1);
  45.   for (bn = 1; bn < z; bn <<= 1)
  46.     {
  47.       mpn_powlo (tp, xp, &k, 1, bn, tp + bn);
  48.       if (mpn_cmp (tp, np, bn) != 0)
  49. return 0;
  50.     }
  51.   TMP_MARK;
  52.   /* Final check. Estimate the size of {xp,xn}^k before computing
  53.      the power with full precision.
  54.      Optimization: It might pay off to make a more accurate estimation of
  55.      the logarithm of {xp,xn}, rather than using the index of the MSB.
  56.   */
  57.   count_leading_zeros (count, xp[xn - 1]);
  58.   y = xn * GMP_LIMB_BITS - count - 1;  /* msb_index (xp, xn) */
  59.   umul_ppmm (h, l, k, y);
  60.   h -= l == 0;  l--; /* two-limb decrement */
  61.   z = f - 1; /* msb_index (np, nn) */
  62.   if (h == 0 && l <= z)
  63.     {
  64.       mp_limb_t size;
  65.       size = l + k;
  66.       ASSERT_ALWAYS (size >= k);
  67.       y = 2 + size / GMP_LIMB_BITS;
  68.       tp2 = TMP_ALLOC_LIMBS (y);
  69.       i = mpn_pow_1 (tp, xp, xn, k, tp2);
  70.       if (i == nn && mpn_cmp (tp, np, nn) == 0)
  71. ans = 1;
  72.       else
  73. ans = 0;
  74.     }
  75.   else
  76.     {
  77.       ans = 0;
  78.     }
  79.   TMP_FREE;
  80.   return ans;
  81. }
  82. /*
  83.    Computes rp such that rp^k * yp = 1 (mod 2^b).
  84.    Algorithm:
  85.        Apply Hensel lifting repeatedly, each time
  86.        doubling (approx.) the number of known bits in rp.
  87. */
  88. static void
  89. binv_root (mp_ptr rp, mp_srcptr yp,
  90.    mp_limb_t k, mp_size_t bn,
  91.    mp_bitcnt_t b, mp_ptr tp)
  92. {
  93.   mp_limb_t *tp2 = tp + bn, *tp3 = tp + 2 * bn, di, k2 = k + 1;
  94.   mp_bitcnt_t order[GMP_LIMB_BITS * 2];
  95.   int i, d = 0;
  96.   ASSERT (bn > 0);
  97.   ASSERT (b > 0);
  98.   ASSERT ((k & 1) != 0);
  99.   binvert_limb (di, k);
  100.   rp[0] = 1;
  101.   for (; b != 1; b = (b + 1) >> 1)
  102.     order[d++] = b;
  103.   for (i = d - 1; i >= 0; i--)
  104.     {
  105.       b = order[i];
  106.       bn = 1 + (b - 1) / GMP_LIMB_BITS;
  107.       mpn_mul_1 (tp, rp, bn, k2);
  108.       mpn_powlo (tp2, rp, &k2, 1, bn, tp3);
  109.       mpn_mullo_n (rp, yp, tp2, bn);
  110.       mpn_sub_n (tp2, tp, rp, bn);
  111.       mpn_pi1_bdiv_q_1 (rp, tp2, bn, k, di, 0);
  112.       if ((b % GMP_LIMB_BITS) != 0)
  113. rp[(b - 1) / GMP_LIMB_BITS] &= (((mp_limb_t) 1) << (b % GMP_LIMB_BITS)) - 1;
  114.     }
  115.   return;
  116. }
  117. /*
  118.    Computes rp such that rp^2 * yp = 1 (mod 2^{b+1}).
  119.    Returns non-zero if such an integer rp exists.
  120. */
  121. static int
  122. binv_sqroot (mp_ptr rp, mp_srcptr yp,
  123.      mp_size_t bn, mp_bitcnt_t b,
  124.      mp_ptr tp)
  125. {
  126.   mp_limb_t k = 3, *tp2 = tp + bn, *tp3 = tp + (bn << 1);
  127.   mp_bitcnt_t order[GMP_LIMB_BITS * 2];
  128.   int i, d = 0;
  129.   ASSERT (bn > 0);
  130.   ASSERT (b > 0);
  131.   rp[0] = 1;
  132.   if (b == 1)
  133.     {
  134.       if ((yp[0] & 3) != 1)
  135. return 0;
  136.     }
  137.   else
  138.     {
  139.       if ((yp[0] & 7) != 1)
  140. return 0;
  141.       for (; b != 2; b = (b + 2) >> 1)
  142. order[d++] = b;
  143.       for (i = d - 1; i >= 0; i--)
  144. {
  145.   b = order[i];
  146.   bn = 1 + b / GMP_LIMB_BITS;
  147.   mpn_mul_1 (tp, rp, bn, k);
  148.   mpn_powlo (tp2, rp, &k, 1, bn, tp3);
  149.   mpn_mullo_n (rp, yp, tp2, bn);
  150. #if HAVE_NATIVE_mpn_rsh1sub_n
  151.   mpn_rsh1sub_n (rp, tp, rp, bn);
  152. #else
  153.   mpn_sub_n (tp2, tp, rp, bn);
  154.   mpn_rshift (rp, tp2, bn, 1);
  155. #endif
  156.   rp[b / GMP_LIMB_BITS] &= (((mp_limb_t) 1) << (b % GMP_LIMB_BITS)) - 1;
  157. }
  158.     }
  159.   return 1;
  160. }
  161. /*
  162.    Returns non-zero if {np,nn} is a kth power.
  163. */
  164. static int
  165. is_kth_power (mp_ptr rp, mp_srcptr np,
  166.       mp_limb_t k, mp_srcptr yp,
  167.       mp_size_t nn, mp_bitcnt_t f,
  168.       mp_ptr tp)
  169. {
  170.   mp_limb_t x, c;
  171.   mp_bitcnt_t b;
  172.   mp_size_t i, rn, xn;
  173.   ASSERT (nn > 0);
  174.   ASSERT (((k & 1) != 0) || (k == 2));
  175.   ASSERT ((np[0] & 1) != 0);
  176.   if (k == 2)
  177.     {
  178.       b = (f + 1) >> 1;
  179.       rn = 1 + b / GMP_LIMB_BITS;
  180.       if (binv_sqroot (rp, yp, rn, b, tp) != 0)
  181. {
  182.   xn = rn;
  183.   MPN_NORMALIZE (rp, xn);
  184.   if (pow_equals (np, nn, rp, xn, k, f, tp) != 0)
  185.     return 1;
  186.   /* Check if (2^b - rp)^2 == np */
  187.   c = 0;
  188.   for (i = 0; i < rn; i++)
  189.     {
  190.       x = rp[i];
  191.       rp[i] = -x - c;
  192.       c |= (x != 0);
  193.     }
  194.   rp[rn - 1] &= (((mp_limb_t) 1) << (b % GMP_LIMB_BITS)) - 1;
  195.   MPN_NORMALIZE (rp, rn);
  196.   if (pow_equals (np, nn, rp, rn, k, f, tp) != 0)
  197.     return 1;
  198. }
  199.     }
  200.   else
  201.     {
  202.       b = 1 + (f - 1) / k;
  203.       rn = 1 + (b - 1) / GMP_LIMB_BITS;
  204.       binv_root (rp, yp, k, rn, b, tp);
  205.       MPN_NORMALIZE (rp, rn);
  206.       if (pow_equals (np, nn, rp, rn, k, f, tp) != 0)
  207. return 1;
  208.     }
  209.   MPN_ZERO (rp, rn); /* Untrash rp */
  210.   return 0;
  211. }
  212. static int
  213. perfpow (mp_srcptr np, mp_size_t nn,
  214.  mp_limb_t ub, mp_limb_t g,
  215.  mp_bitcnt_t f, int neg)
  216. {
  217.   mp_limb_t *yp, *tp, k = 0, *rp1;
  218.   int ans = 0;
  219.   mp_bitcnt_t b;
  220.   gmp_primesieve_t ps;
  221.   TMP_DECL;
  222.   ASSERT (nn > 0);
  223.   ASSERT ((np[0] & 1) != 0);
  224.   ASSERT (ub > 0);
  225.   TMP_MARK;
  226.   gmp_init_primesieve (&ps);
  227.   b = (f + 3) >> 1;
  228.   yp = TMP_ALLOC_LIMBS (nn);
  229.   rp1 = TMP_ALLOC_LIMBS (nn);
  230.   tp = TMP_ALLOC_LIMBS (5 * nn); /* FIXME */
  231.   MPN_ZERO (rp1, nn);
  232.   mpn_binvert (yp, np, 1 + (b - 1) / GMP_LIMB_BITS, tp);
  233.   if (b % GMP_LIMB_BITS)
  234.     yp[(b - 1) / GMP_LIMB_BITS] &= (((mp_limb_t) 1) << (b % GMP_LIMB_BITS)) - 1;
  235.   if (neg)
  236.     gmp_nextprime (&ps);
  237.   if (g > 0)
  238.     {
  239.       ub = MIN (ub, g + 1);
  240.       while ((k = gmp_nextprime (&ps)) < ub)
  241. {
  242.   if ((g % k) == 0)
  243.     {
  244.       if (is_kth_power (rp1, np, k, yp, nn, f, tp) != 0)
  245. {
  246.   ans = 1;
  247.   goto ret;
  248. }
  249.     }
  250. }
  251.     }
  252.   else
  253.     {
  254.       while ((k = gmp_nextprime (&ps)) < ub)
  255. {
  256.   if (is_kth_power (rp1, np, k, yp, nn, f, tp) != 0)
  257.     {
  258.       ans = 1;
  259.       goto ret;
  260.     }
  261. }
  262.     }
  263.  ret:
  264.   TMP_FREE;
  265.   return ans;
  266. }
  267. static const unsigned short nrtrial[] = { 100, 500, 1000 };
  268. /* Table of (log_{p_i} 2) values, where p_i is
  269.    the (nrtrial[i] + 1)'th prime number.
  270. */
  271. static const double logs[] = { 0.1099457228193620, 0.0847016403115322, 0.0772048195144415 };
  272. int
  273. mpn_perfect_power_p (mp_srcptr np, mp_size_t nn)
  274. {
  275.   mp_size_t ncn, s, pn, xn;
  276.   mp_limb_t *nc, factor, g = 0;
  277.   mp_limb_t exp, *prev, *next, d, l, r, c, *tp, cry;
  278.   mp_bitcnt_t twos = 0, count;
  279.   int ans, where = 0, neg = 0, trial;
  280.   TMP_DECL;
  281.   nc = (mp_ptr) np;
  282.   if (nn < 0)
  283.     {
  284.       neg = 1;
  285.       nn = -nn;
  286.     }
  287.   if (nn == 0 || (nn == 1 && np[0] == 1))
  288.     return 1;
  289.   TMP_MARK;
  290.   ncn = nn;
  291.   twos = mpn_scan1 (np, 0);
  292.   if (twos > 0)
  293.     {
  294.       if (twos == 1)
  295. {
  296.   ans = 0;
  297.   goto ret;
  298. }
  299.       s = twos / GMP_LIMB_BITS;
  300.       if (s + 1 == nn && POW2_P (np[s]))
  301. {
  302.   ans = ! (neg && POW2_P (twos));
  303.   goto ret;
  304. }
  305.       count = twos % GMP_LIMB_BITS;
  306.       ncn = nn - s;
  307.       nc = TMP_ALLOC_LIMBS (ncn);
  308.       if (count > 0)
  309. {
  310.   mpn_rshift (nc, np + s, ncn, count);
  311.   ncn -= (nc[ncn - 1] == 0);
  312. }
  313.       else
  314. {
  315.   MPN_COPY (nc, np + s, ncn);
  316. }
  317.       g = twos;
  318.     }
  319.   if (ncn <= SMALL)
  320.     trial = 0;
  321.   else if (ncn <= MEDIUM)
  322.     trial = 1;
  323.   else
  324.     trial = 2;
  325.   factor = mpn_trialdiv (nc, ncn, nrtrial[trial], &where);
  326.   if (factor != 0)
  327.     {
  328.       if (twos == 0)
  329. {
  330.   nc = TMP_ALLOC_LIMBS (ncn);
  331.   MPN_COPY (nc, np, ncn);
  332. }
  333.       /* Remove factors found by trialdiv.
  334.  Optimization: Perhaps better to use
  335.  the strategy in mpz_remove ().
  336.       */
  337.       prev = TMP_ALLOC_LIMBS (ncn + 2);
  338.       next = TMP_ALLOC_LIMBS (ncn + 2);
  339.       tp = TMP_ALLOC_LIMBS (4 * ncn);
  340.       do
  341. {
  342.   binvert_limb (d, factor);
  343.   prev[0] = d;
  344.   pn = 1;
  345.   exp = 1;
  346.   while (2 * pn - 1 <= ncn)
  347.     {
  348.       mpn_sqr (next, prev, pn);
  349.       xn = 2 * pn;
  350.       xn -= (next[xn - 1] == 0);
  351.       if (mpn_divisible_p (nc, ncn, next, xn) == 0)
  352. break;
  353.       exp <<= 1;
  354.       pn = xn;
  355.       MP_PTR_SWAP (next, prev);
  356.     }
  357.   /* Binary search for the exponent */
  358.   l = exp + 1;
  359.   r = 2 * exp - 1;
  360.   while (l <= r)
  361.     {
  362.       c = (l + r) >> 1;
  363.       if (c - exp > 1)
  364. {
  365.   xn = mpn_pow_1 (tp, &d, 1, c - exp, next);
  366.   if (pn + xn - 1 > ncn)
  367.     {
  368.       r = c - 1;
  369.       continue;
  370.     }
  371.   mpn_mul (next, prev, pn, tp, xn);
  372.   xn += pn;
  373.   xn -= (next[xn - 1] == 0);
  374. }
  375.       else
  376. {
  377.   cry = mpn_mul_1 (next, prev, pn, d);
  378.   next[pn] = cry;
  379.   xn = pn + (cry != 0);
  380. }
  381.       if (mpn_divisible_p (nc, ncn, next, xn) == 0)
  382. {
  383.   r = c - 1;
  384. }
  385.       else
  386. {
  387.   exp = c;
  388.   l = c + 1;
  389.   MP_PTR_SWAP (next, prev);
  390.   pn = xn;
  391. }
  392.     }
  393.   if (g == 0)
  394.     g = exp;
  395.   else
  396.     g = mpn_gcd_1 (&g, 1, exp);
  397.   if (g == 1)
  398.     {
  399.       ans = 0;
  400.       goto ret;
  401.     }
  402.   mpn_divexact (next, nc, ncn, prev, pn);
  403.   ncn = ncn - pn;
  404.   ncn += next[ncn] != 0;
  405.   MPN_COPY (nc, next, ncn);
  406.   if (ncn == 1 && nc[0] == 1)
  407.     {
  408.       ans = ! (neg && POW2_P (g));
  409.       goto ret;
  410.     }
  411.   factor = mpn_trialdiv (nc, ncn, nrtrial[trial], &where);
  412. }
  413.       while (factor != 0);
  414.     }
  415.   count_leading_zeros (count, nc[ncn-1]);
  416.   count = GMP_LIMB_BITS * ncn - count;   /* log (nc) + 1 */
  417.   d = (mp_limb_t) (count * logs[trial] + 1e-9) + 1;
  418.   ans = perfpow (nc, ncn, d, g, count, neg);
  419.  ret:
  420.   TMP_FREE;
  421.   return ans;
  422. }