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

数学计算

开发平台:

Unix_Linux

  1. /* Reference mpz functions.
  2. Copyright 1997, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
  3. This file is part of the GNU MP Library.
  4. The GNU MP Library is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU Lesser General Public License as published by
  6. the Free Software Foundation; either version 3 of the License, or (at your
  7. option) any later version.
  8. The GNU MP Library is distributed in the hope that it will be useful, but
  9. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  10. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  11. License for more details.
  12. You should have received a copy of the GNU Lesser General Public License
  13. along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  14. /* always do assertion checking */
  15. #define WANT_ASSERT  1
  16. #include <stdio.h>
  17. #include <stdlib.h> /* for free */
  18. #include "gmp.h"
  19. #include "gmp-impl.h"
  20. #include "longlong.h"
  21. #include "tests.h"
  22. /* Change this to "#define TRACE(x) x" for some traces. */
  23. #define TRACE(x)
  24. /* FIXME: Shouldn't use plain mpz functions in a reference routine. */
  25. void
  26. refmpz_combit (mpz_ptr r, unsigned long bit)
  27. {
  28.   if (mpz_tstbit (r, bit))
  29.     mpz_clrbit (r, bit);
  30.   else
  31.     mpz_setbit (r, bit);
  32. }
  33. unsigned long
  34. refmpz_hamdist (mpz_srcptr x, mpz_srcptr y)
  35. {
  36.   mp_size_t      xsize, ysize, tsize;
  37.   mp_ptr         xp, yp;
  38.   unsigned long  ret;
  39.   if ((SIZ(x) < 0 && SIZ(y) >= 0)
  40.       || (SIZ(y) < 0 && SIZ(x) >= 0))
  41.     return ULONG_MAX;
  42.   xsize = ABSIZ(x);
  43.   ysize = ABSIZ(y);
  44.   tsize = MAX (xsize, ysize);
  45.   xp = refmpn_malloc_limbs (tsize);
  46.   refmpn_zero (xp, tsize);
  47.   refmpn_copy (xp, PTR(x), xsize);
  48.   yp = refmpn_malloc_limbs (tsize);
  49.   refmpn_zero (yp, tsize);
  50.   refmpn_copy (yp, PTR(y), ysize);
  51.   if (SIZ(x) < 0)
  52.     refmpn_neg (xp, xp, tsize);
  53.   if (SIZ(x) < 0)
  54.     refmpn_neg (yp, yp, tsize);
  55.   ret = refmpn_hamdist (xp, yp, tsize);
  56.   free (xp);
  57.   free (yp);
  58.   return ret;
  59. }
  60. /* (0/b), with mpz b; is 1 if b=+/-1, 0 otherwise */
  61. #define JACOBI_0Z(b)  JACOBI_0LS (PTR(b)[0], SIZ(b))
  62. /* (a/b) effect due to sign of b: mpz/mpz */
  63. #define JACOBI_BSGN_ZZ_BIT1(a, b)   JACOBI_BSGN_SS_BIT1 (SIZ(a), SIZ(b))
  64. /* (a/b) effect due to sign of a: mpz/unsigned-mpz, b odd;
  65.    is (-1/b) if a<0, or +1 if a>=0 */
  66. #define JACOBI_ASGN_ZZU_BIT1(a, b)  JACOBI_ASGN_SU_BIT1 (SIZ(a), PTR(b)[0])
  67. int
  68. refmpz_kronecker (mpz_srcptr a_orig, mpz_srcptr b_orig)
  69. {
  70.   unsigned long  twos;
  71.   mpz_t  a, b;
  72.   int    result_bit1 = 0;
  73.   if (mpz_sgn (b_orig) == 0)
  74.     return JACOBI_Z0 (a_orig);  /* (a/0) */
  75.   if (mpz_sgn (a_orig) == 0)
  76.     return JACOBI_0Z (b_orig);  /* (0/b) */
  77.   if (mpz_even_p (a_orig) && mpz_even_p (b_orig))
  78.     return 0;
  79.   if (mpz_cmp_ui (b_orig, 1) == 0)
  80.     return 1;
  81.   mpz_init_set (a, a_orig);
  82.   mpz_init_set (b, b_orig);
  83.   if (mpz_sgn (b) < 0)
  84.     {
  85.       result_bit1 ^= JACOBI_BSGN_ZZ_BIT1 (a, b);
  86.       mpz_neg (b, b);
  87.     }
  88.   if (mpz_even_p (b))
  89.     {
  90.       twos = mpz_scan1 (b, 0L);
  91.       mpz_tdiv_q_2exp (b, b, twos);
  92.       result_bit1 ^= JACOBI_TWOS_U_BIT1 (twos, PTR(a)[0]);
  93.     }
  94.   if (mpz_sgn (a) < 0)
  95.     {
  96.       result_bit1 ^= JACOBI_N1B_BIT1 (PTR(b)[0]);
  97.       mpz_neg (a, a);
  98.     }
  99.   if (mpz_even_p (a))
  100.     {
  101.       twos = mpz_scan1 (a, 0L);
  102.       mpz_tdiv_q_2exp (a, a, twos);
  103.       result_bit1 ^= JACOBI_TWOS_U_BIT1 (twos, PTR(b)[0]);
  104.     }
  105.   for (;;)
  106.     {
  107.       ASSERT (mpz_odd_p (a));
  108.       ASSERT (mpz_odd_p (b));
  109.       ASSERT (mpz_sgn (a) > 0);
  110.       ASSERT (mpz_sgn (b) > 0);
  111.       TRACE (printf ("topn");
  112.      mpz_trace (" a", a);
  113.      mpz_trace (" b", b));
  114.       if (mpz_cmp (a, b) < 0)
  115. {
  116.   TRACE (printf ("swapn"));
  117.   mpz_swap (a, b);
  118.   result_bit1 ^= JACOBI_RECIP_UU_BIT1 (PTR(a)[0], PTR(b)[0]);
  119. }
  120.       if (mpz_cmp_ui (b, 1) == 0)
  121. break;
  122.       mpz_sub (a, a, b);
  123.       TRACE (printf ("subn");
  124.      mpz_trace (" a", a));
  125.       if (mpz_sgn (a) == 0)
  126. goto zero;
  127.       twos = mpz_scan1 (a, 0L);
  128.       mpz_fdiv_q_2exp (a, a, twos);
  129.       TRACE (printf ("twos %lun", twos);
  130.      mpz_trace (" a", a));
  131.       result_bit1 ^= JACOBI_TWOS_U_BIT1 (twos, PTR(b)[0]);
  132.     }
  133.   mpz_clear (a);
  134.   mpz_clear (b);
  135.   return JACOBI_BIT1_TO_PN (result_bit1);
  136.  zero:
  137.   mpz_clear (a);
  138.   mpz_clear (b);
  139.   return 0;
  140. }
  141. /* Same as mpz_kronecker, but ignoring factors of 2 on b */
  142. int
  143. refmpz_jacobi (mpz_srcptr a, mpz_srcptr b)
  144. {
  145.   mpz_t  b_odd;
  146.   mpz_init_set (b_odd, b);
  147.   if (mpz_sgn (b_odd) != 0)
  148.     mpz_fdiv_q_2exp (b_odd, b_odd, mpz_scan1 (b_odd, 0L));
  149.   return refmpz_kronecker (a, b_odd);
  150. }
  151. int
  152. refmpz_legendre (mpz_srcptr a, mpz_srcptr b)
  153. {
  154.   return refmpz_jacobi (a, b);
  155. }
  156. int
  157. refmpz_kronecker_ui (mpz_srcptr a, unsigned long b)
  158. {
  159.   mpz_t  bz;
  160.   int    ret;
  161.   mpz_init_set_ui (bz, b);
  162.   ret = refmpz_kronecker (a, bz);
  163.   mpz_clear (bz);
  164.   return ret;
  165. }
  166. int
  167. refmpz_kronecker_si (mpz_srcptr a, long b)
  168. {
  169.   mpz_t  bz;
  170.   int    ret;
  171.   mpz_init_set_si (bz, b);
  172.   ret = refmpz_kronecker (a, bz);
  173.   mpz_clear (bz);
  174.   return ret;
  175. }
  176. int
  177. refmpz_ui_kronecker (unsigned long a, mpz_srcptr b)
  178. {
  179.   mpz_t  az;
  180.   int    ret;
  181.   mpz_init_set_ui (az, a);
  182.   ret = refmpz_kronecker (az, b);
  183.   mpz_clear (az);
  184.   return ret;
  185. }
  186. int
  187. refmpz_si_kronecker (long a, mpz_srcptr b)
  188. {
  189.   mpz_t  az;
  190.   int    ret;
  191.   mpz_init_set_si (az, a);
  192.   ret = refmpz_kronecker (az, b);
  193.   mpz_clear (az);
  194.   return ret;
  195. }
  196. void
  197. refmpz_pow_ui (mpz_ptr w, mpz_srcptr b, unsigned long e)
  198. {
  199.   mpz_t          s, t;
  200.   unsigned long  i;
  201.   mpz_init_set_ui (t, 1L);
  202.   mpz_init_set (s, b);
  203.   if ((e & 1) != 0)
  204.     mpz_mul (t, t, s);
  205.   for (i = 2; i <= e; i <<= 1)
  206.     {
  207.       mpz_mul (s, s, s);
  208.       if ((i & e) != 0)
  209. mpz_mul (t, t, s);
  210.     }
  211.   mpz_set (w, t);
  212.   mpz_clear (s);
  213.   mpz_clear (t);
  214. }