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

数学计算

开发平台:

Unix_Linux

  1. /* Test mpz_perfect_square_p.
  2. Copyright 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. #include <stdio.h>
  15. #include <stdlib.h>
  16. #include "gmp.h"
  17. #include "gmp-impl.h"
  18. #include "tests.h"
  19. #include "mpn/perfsqr.h"
  20. /* check_modulo() exercises mpz_perfect_square_p on squares which cover each
  21.    possible quadratic residue to each divisor used within
  22.    mpn_perfect_square_p, ensuring those residues aren't incorrectly claimed
  23.    to be non-residues.
  24.    Each divisor is taken separately.  It's arranged that n is congruent to 0
  25.    modulo the other divisors, 0 of course being a quadratic residue to any
  26.    modulus.
  27.    The values "(j*others)^2" cover all quadratic residues mod divisor[i],
  28.    but in no particular order.  j is run from 1<=j<=divisor[i] so that zero
  29.    is excluded.  A literal n==0 doesn't reach the residue tests.  */
  30. void
  31. check_modulo (void)
  32. {
  33.   static const unsigned long  divisor[] = PERFSQR_DIVISORS;
  34.   unsigned long  i, j;
  35.   mpz_t  alldiv, others, n;
  36.   mpz_init (alldiv);
  37.   mpz_init (others);
  38.   mpz_init (n);
  39.   /* product of all divisors */
  40.   mpz_set_ui (alldiv, 1L);
  41.   for (i = 0; i < numberof (divisor); i++)
  42.     mpz_mul_ui (alldiv, alldiv, divisor[i]);
  43.   for (i = 0; i < numberof (divisor); i++)
  44.     {
  45.       /* product of all divisors except i */
  46.       mpz_set_ui (others, 1L);
  47.       for (j = 0; j < numberof (divisor); j++)
  48.         if (i != j)
  49.           mpz_mul_ui (others, others, divisor[j]);
  50.       for (j = 1; j <= divisor[i]; j++)
  51.         {
  52.           /* square */
  53.           mpz_mul_ui (n, others, j);
  54.           mpz_mul (n, n, n);
  55.           if (! mpz_perfect_square_p (n))
  56.             {
  57.               printf ("mpz_perfect_square_p got 0, want 1n");
  58.               mpz_trace ("  n", n);
  59.               abort ();
  60.             }
  61.         }
  62.     }
  63.   mpz_clear (alldiv);
  64.   mpz_clear (others);
  65.   mpz_clear (n);
  66. }
  67. /* Exercise mpz_perfect_square_p compared to what mpz_sqrt says. */
  68. void
  69. check_sqrt (int reps)
  70. {
  71.   mpz_t x2, x2t, x;
  72.   mp_size_t x2n;
  73.   int res;
  74.   int i;
  75.   /* int cnt = 0; */
  76.   gmp_randstate_ptr rands = RANDS;
  77.   mpz_t bs;
  78.   mpz_init (bs);
  79.   mpz_init (x2);
  80.   mpz_init (x);
  81.   mpz_init (x2t);
  82.   for (i = 0; i < reps; i++)
  83.     {
  84.       mpz_urandomb (bs, rands, 9);
  85.       x2n = mpz_get_ui (bs);
  86.       mpz_rrandomb (x2, rands, x2n);
  87.       /* mpz_out_str (stdout, -16, x2); puts (""); */
  88.       res = mpz_perfect_square_p (x2);
  89.       mpz_sqrt (x, x2);
  90.       mpz_mul (x2t, x, x);
  91.       if (res != (mpz_cmp (x2, x2t) == 0))
  92.         {
  93.           printf    ("mpz_perfect_square_p and mpz_sqrt differn");
  94.           mpz_trace ("   x  ", x);
  95.           mpz_trace ("   x2 ", x2);
  96.           mpz_trace ("   x2t", x2t);
  97.           printf    ("   mpz_perfect_square_p %dn", res);
  98.           printf    ("   mpz_sqrt             %dn", mpz_cmp (x2, x2t) == 0);
  99.           abort ();
  100.         }
  101.       /* cnt += res != 0; */
  102.     }
  103.   /* printf ("%d/%d perfect squaresn", cnt, reps); */
  104.   mpz_clear (bs);
  105.   mpz_clear (x2);
  106.   mpz_clear (x);
  107.   mpz_clear (x2t);
  108. }
  109. int
  110. main (int argc, char **argv)
  111. {
  112.   int reps = 200000;
  113.   tests_start ();
  114.   mp_trace_base = -16;
  115.   if (argc == 2)
  116.      reps = atoi (argv[1]);
  117.   check_modulo ();
  118.   check_sqrt (reps);
  119.   tests_end ();
  120.   exit (0);
  121. }