Home | History | Annotate | Line # | Download | only in mpz 
      1 /* Test mpz_perfect_power_p.
      2 
      3    Contributed to the GNU project by Torbjorn Granlund and Martin Boij.
      4 
      5 Copyright 2008-2010, 2014 Free Software Foundation, Inc.
      6 
      7 This file is part of the GNU MP Library test suite.
      8 
      9 The GNU MP Library test suite is free software; you can redistribute it
     10 and/or modify it under the terms of the GNU General Public License as
     11 published by the Free Software Foundation; either version 3 of the License,
     12 or (at your option) any later version.
     13 
     14 The GNU MP Library test suite is distributed in the hope that it will be
     15 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
     16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
     17 Public License for more details.
     18 
     19 You should have received a copy of the GNU General Public License along with
     20 the GNU MP Library test suite.  If not, see https://www.gnu.org/licenses/.  */
     21 
     22 #include <stdio.h>
     23 #include <stdlib.h>
     24 
     25 #include "gmp-impl.h"
     26 #include "tests.h"
     27 
     28 struct
     29 {
     30   const char *num_as_str;
     31   char want;
     32 } static tests[] =
     33   {
     34     { "0", 1},
     35     { "1", 1},
     36     {"-1", 1},
     37     { "2", 0},
     38     {"-2", 0},
     39     { "3", 0},
     40     {"-3", 0},
     41     { "4", 1},
     42     {"-4", 0},
     43     { "64", 1},
     44     {"-64", 1},
     45     { "128", 1},
     46     {"-128", 1},
     47     { "256", 1},
     48     {"-256", 0},
     49     { "512", 1},
     50     {"-512", 1},
     51     { "0x4000000", 1},
     52     {"-0x4000000", 1},
     53     { "0x3cab640", 1},
     54     {"-0x3cab640", 0},
     55     { "0x3e23840", 1},
     56     {"-0x3e23840", 0},
     57     { "0x3d3a7ed1", 1},
     58     {"-0x3d3a7ed1", 1},
     59     { "0x30a7a6000", 1},
     60     {"-0x30a7a6000", 1},
     61     { "0xf33e5a5a59", 1},
     62     {"-0xf33e5a5a59", 0},
     63     { "0xed1b1182118135d", 1},
     64     {"-0xed1b1182118135d", 1},
     65     { "0xe71f6eb7689cc276b2f1", 1},
     66     {"-0xe71f6eb7689cc276b2f1", 0},
     67     { "0x12644507fe78cf563a4b342c92e7da9fe5e99cb75a01", 1},
     68     {"-0x12644507fe78cf563a4b342c92e7da9fe5e99cb75a01", 0},
     69     { "0x1ff2e7c581bb0951df644885bd33f50e472b0b73a204e13cbe98fdb424d66561e4000000", 1},
     70     {"-0x1ff2e7c581bb0951df644885bd33f50e472b0b73a204e13cbe98fdb424d66561e4000000", 1},
     71     { "0x2b9b44db2d91a6f8165c8c7339ef73633228ea29e388592e80354e4380004aad84000000", 1},
     72     {"-0x2b9b44db2d91a6f8165c8c7339ef73633228ea29e388592e80354e4380004aad84000000", 1},
     73     { "0x28d5a2b8f330910a9d3cda06036ae0546442e5b1a83b26a436efea5b727bf1bcbe7e12b47d81", 1},
     74     {"-0x28d5a2b8f330910a9d3cda06036ae0546442e5b1a83b26a436efea5b727bf1bcbe7e12b47d81", 1},
     75     {NULL, 0}
     76   };
     77 
     78 
     79 void
     80 check_tests ()
     81 {
     82   mpz_t x;
     83   int i;
     84   int got, want;
     85 
     86   mpz_init (x);
     87 
     88   for (i = 0; tests[i].num_as_str != NULL; i++)
     89     {
     90       mpz_set_str (x, tests[i].num_as_str, 0);
     91       got = mpz_perfect_power_p (x);
     92       want = tests[i].want;
     93       if (got != want)
     94 	{
     95 	  fprintf (stderr, "mpz_perfect_power_p returns %d when %d was expected\n", got, want);
     96 	  fprintf (stderr, "fault operand: %s\n", tests[i].num_as_str);
     97 	  abort ();
     98 	}
     99     }
    100 
    101   mpz_clear (x);
    102 }
    103 
    104 #define NRP 15
    105 
    106 void
    107 check_random (int reps)
    108 {
    109   mpz_t n, np, temp, primes[NRP];
    110   int i, j, k, unique, destroy, res;
    111   unsigned long int nrprimes, primebits;
    112   mp_limb_t g, exp[NRP], e;
    113   gmp_randstate_ptr rands;
    114 
    115   rands = RANDS;
    116 
    117   mpz_init (n);
    118   mpz_init (np);
    119   mpz_init (temp);
    120 
    121   for (i = 0; i < NRP; i++)
    122     mpz_init (primes[i]);
    123 
    124   for (i = 0; i < reps; i++)
    125     {
    126       mpz_urandomb (np, rands, 32);
    127       nrprimes = mpz_get_ui (np) % NRP + 1; /* 1-NRP unique primes */
    128 
    129       mpz_urandomb (np, rands, 32);
    130       g = mpz_get_ui (np) % 32 + 2; /* gcd 2-33 */
    131 
    132       for (j = 0; j < nrprimes;)
    133 	{
    134 	  mpz_urandomb (np, rands, 32);
    135 	  primebits = mpz_get_ui (np) % 100 + 3; /* 3-102 bit primes */
    136 	  mpz_urandomb (primes[j], rands, primebits);
    137 	  mpz_nextprime (primes[j], primes[j]);
    138 	  unique = 1;
    139 	  for (k = 0; k < j; k++)
    140 	    {
    141 	      if (mpz_cmp (primes[j], primes[k]) == 0)
    142 		{
    143 		  unique = 0;
    144 		  break;
    145 		}
    146 	    }
    147 	  if (unique)
    148 	    {
    149 	      mpz_urandomb (np, rands, 32);
    150 	      e = 371 / (10 * primebits) + mpz_get_ui (np) % 11 + 1; /* Magic constants */
    151 	      exp[j++] = g * e;
    152 	    }
    153 	}
    154 
    155       if (nrprimes > 1)
    156 	{
    157 	  /* Destroy d exponents, d in [1, nrprimes - 1] */
    158 	  if (nrprimes == 2)
    159 	    {
    160 	      destroy = 1;
    161 	    }
    162 	  else
    163 	    {
    164 	      mpz_urandomb (np, rands, 32);
    165 	      destroy = mpz_get_ui (np) % (nrprimes - 2);
    166 	    }
    167 
    168 	  g = exp[destroy];
    169 	  for (k = destroy + 1; k < nrprimes; k++)
    170 	    g = mpn_gcd_1 (&g, 1, exp[k]);
    171 
    172 	  for (j = 0; j < destroy; j++)
    173 	    {
    174 	      mpz_urandomb (np, rands, 32);
    175 	      e = mpz_get_ui (np) % 50 + 1;
    176 	      while (mpn_gcd_1 (&g, 1, e) > 1)
    177 		e++;
    178 
    179 	      exp[j] = e;
    180 	    }
    181 	}
    182 
    183       /* Compute n */
    184       mpz_pow_ui (n, primes[0], exp[0]);
    185       for (j = 1; j < nrprimes; j++)
    186 	{
    187 	  mpz_pow_ui (temp, primes[j], exp[j]);
    188 	  mpz_mul (n, n, temp);
    189 	}
    190 
    191       res = mpz_perfect_power_p (n);
    192 
    193       if (nrprimes == 1)
    194 	{
    195 	if (res == 0 && exp[0] > 1)
    196 	  {
    197 	    printf("n is a perfect power, perfpow_p disagrees\n");
    198 	    gmp_printf("n = %Zu\nprimes[0] = %Zu\nexp[0] = %lu\n", n, primes[0], exp[0]);
    199 	    abort ();
    200 	  }
    201 	else if (res == 1 && exp[0] == 1)
    202 	  {
    203 	    gmp_printf("n = %Zu\n", n);
    204 	    printf("n is now a prime number, but perfpow_p still believes n is a perfect power\n");
    205 	    abort ();
    206 	  }
    207 	}
    208       else
    209 	{
    210 	  if (res == 1 && destroy != 0)
    211 	    {
    212 	      gmp_printf("n = %Zu\nn was destroyed, but perfpow_p still believes n is a perfect power\n", n);
    213 	      abort ();
    214 	    }
    215 	  else if (res == 0 && destroy == 0)
    216 	    {
    217 	      gmp_printf("n = %Zu\nn is a perfect power, perfpow_p disagrees\n", n);
    218 	      abort ();
    219 	    }
    220 	}
    221     }
    222 
    223   mpz_clear (n);
    224   mpz_clear (np);
    225   mpz_clear (temp);
    226   for (i = 0; i < NRP; i++)
    227     mpz_clear (primes[i]);
    228 }
    229 
    230 int
    231 main (int argc, char **argv)
    232 {
    233   int n_tests;
    234 
    235   tests_start ();
    236   mp_trace_base = -16;
    237 
    238   check_tests ();
    239 
    240   n_tests = 500;
    241   if (argc == 2)
    242     n_tests = atoi (argv[1]);
    243   check_random (n_tests);
    244 
    245   tests_end ();
    246   exit (0);
    247 }
    248