Imported gcc-4.4.3

[msp430-gcc.git] / gmp / tests / mpz / t-perfsqr.c

diff --git a/gmp/tests/mpz/t-perfsqr.c b/gmp/tests/mpz/t-perfsqr.c
new file mode 100644 (file)
index 0000000..f5fa15b
--- /dev/null
+++ b/gmp/tests/mpz/t-perfsqr.c
@@ -0,0 +1,155 @@
+/* Test mpz_perfect_square_p.
+
+Copyright 2000, 2001, 2002 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 3 of the License, or (at your
+option) any later version.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+License for more details.
+
+You should have received a copy of the GNU Lesser General Public License
+along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "gmp.h"
+#include "gmp-impl.h"
+#include "tests.h"
+
+#include "mpn/perfsqr.h"
+
+
+/* check_modulo() exercises mpz_perfect_square_p on squares which cover each
+   possible quadratic residue to each divisor used within
+   mpn_perfect_square_p, ensuring those residues aren't incorrectly claimed
+   to be non-residues.
+
+   Each divisor is taken separately.  It's arranged that n is congruent to 0
+   modulo the other divisors, 0 of course being a quadratic residue to any
+   modulus.
+
+   The values "(j*others)^2" cover all quadratic residues mod divisor[i],
+   but in no particular order.  j is run from 1<=j<=divisor[i] so that zero
+   is excluded.  A literal n==0 doesn't reach the residue tests.  */
+
+void
+check_modulo (void)
+{
+  static const unsigned long  divisor[] = PERFSQR_DIVISORS;
+  unsigned long  i, j;
+
+  mpz_t  alldiv, others, n;
+
+  mpz_init (alldiv);
+  mpz_init (others);
+  mpz_init (n);
+
+  /* product of all divisors */
+  mpz_set_ui (alldiv, 1L);
+  for (i = 0; i < numberof (divisor); i++)
+    mpz_mul_ui (alldiv, alldiv, divisor[i]);
+
+  for (i = 0; i < numberof (divisor); i++)
+    {
+      /* product of all divisors except i */
+      mpz_set_ui (others, 1L);
+      for (j = 0; j < numberof (divisor); j++)
+        if (i != j)
+          mpz_mul_ui (others, others, divisor[j]);
+
+      for (j = 1; j <= divisor[i]; j++)
+        {
+          /* square */
+          mpz_mul_ui (n, others, j);
+          mpz_mul (n, n, n);
+          if (! mpz_perfect_square_p (n))
+            {
+              printf ("mpz_perfect_square_p got 0, want 1\n");
+              mpz_trace ("  n", n);
+              abort ();
+            }
+        }
+    }
+
+  mpz_clear (alldiv);
+  mpz_clear (others);
+  mpz_clear (n);
+}
+
+
+/* Exercise mpz_perfect_square_p compared to what mpz_sqrt says. */
+void
+check_sqrt (int reps)
+{
+  mpz_t x2, x2t, x;
+  mp_size_t x2n;
+  int res;
+  int i;
+  /* int cnt = 0; */
+  gmp_randstate_ptr rands = RANDS;
+  mpz_t bs;
+
+  mpz_init (bs);
+
+  mpz_init (x2);
+  mpz_init (x);
+  mpz_init (x2t);
+
+  for (i = 0; i < reps; i++)
+    {
+      mpz_urandomb (bs, rands, 9);
+      x2n = mpz_get_ui (bs);
+      mpz_rrandomb (x2, rands, x2n);
+      /* mpz_out_str (stdout, -16, x2); puts (""); */
+
+      res = mpz_perfect_square_p (x2);
+      mpz_sqrt (x, x2);
+      mpz_mul (x2t, x, x);
+
+      if (res != (mpz_cmp (x2, x2t) == 0))
+        {
+          printf    ("mpz_perfect_square_p and mpz_sqrt differ\n");
+          mpz_trace ("   x  ", x);
+          mpz_trace ("   x2 ", x2);
+          mpz_trace ("   x2t", x2t);
+          printf    ("   mpz_perfect_square_p %d\n", res);
+          printf    ("   mpz_sqrt             %d\n", mpz_cmp (x2, x2t) == 0);
+          abort ();
+        }
+
+      /* cnt += res != 0; */
+    }
+  /* printf ("%d/%d perfect squares\n", cnt, reps); */
+
+  mpz_clear (bs);
+  mpz_clear (x2);
+  mpz_clear (x);
+  mpz_clear (x2t);
+}
+
+
+int
+main (int argc, char **argv)
+{
+  int reps = 200000;
+
+  tests_start ();
+  mp_trace_base = -16;
+
+  if (argc == 2)
+     reps = atoi (argv[1]);
+
+  check_modulo ();
+  check_sqrt (reps);
+
+  tests_end ();
+  exit (0);
+}