tests/mpz/t-perfpow.c

   1 /* Test mpz_perfect_power_p.
   2
   3    Contributed to the GNU project by Torbjorn Granlund and Martin Boij.
   4
   5 Copyright 2008, 2009 Free Software Foundation, Inc.
   6
   7 This file is part of the GNU MP Library.
   8
   9 The GNU MP Library is free software; you can redistribute it and/or modify
  10 it under the terms of the GNU Lesser General Public License as published by
  11 the Free Software Foundation; either version 3 of the License, or (at your
  12 option) any later version.
  13
  14 The GNU MP Library is distributed in the hope that it will be useful, but
  15 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  16 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  17 License for more details.
  18
  19 You should have received a copy of the GNU Lesser General Public License
  20 along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  21
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24
  25 #include "gmp.h"
  26 #include "gmp-impl.h"
  27 #include "tests.h"
  28
  29 struct
  30 {
  31   char *num_as_str;
  32   char want;
  33 } tests[] =
  34   {
  35     { "0", 1},
  36     { "1", 1},
  37     {"-1", 1},
  38     { "2", 0},
  39     {"-2", 0},
  40     { "3", 0},
  41     {"-3", 0},
  42     { "4", 1},
  43     {"-4", 0},
  44     { "64", 1},
  45     {"-64", 1},
  46     { "128", 1},
  47     {"-128", 1},
  48     { "256", 1},
  49     {"-256", 0},
  50     { "512", 1},
  51     {"-512", 1},
  52     { "0x4000000", 1},
  53     {"-0x4000000", 1},
  54     { "0x3cab640", 1},
  55     {"-0x3cab640", 0},
  56     { "0x3e23840", 1},
  57     {"-0x3e23840", 0},
  58     { "0x3d3a7ed1", 1},
  59     {"-0x3d3a7ed1", 1},
  60     { "0x30a7a6000", 1},
  61     {"-0x30a7a6000", 1},
  62     { "0xf33e5a5a59", 1},
  63     {"-0xf33e5a5a59", 0},
  64     { "0xed1b1182118135d", 1},
  65     {"-0xed1b1182118135d", 1},
  66     { "0xe71f6eb7689cc276b2f1", 1},
  67     {"-0xe71f6eb7689cc276b2f1", 0},
  68     { "0x12644507fe78cf563a4b342c92e7da9fe5e99cb75a01", 1},
  69     {"-0x12644507fe78cf563a4b342c92e7da9fe5e99cb75a01", 0},
  70     { "0x1ff2e7c581bb0951df644885bd33f50e472b0b73a204e13cbe98fdb424d66561e4000000", 1},
  71     {"-0x1ff2e7c581bb0951df644885bd33f50e472b0b73a204e13cbe98fdb424d66561e4000000", 1},
  72     { "0x2b9b44db2d91a6f8165c8c7339ef73633228ea29e388592e80354e4380004aad84000000", 1},
  73     {"-0x2b9b44db2d91a6f8165c8c7339ef73633228ea29e388592e80354e4380004aad84000000", 1},
  74     { "0x28d5a2b8f330910a9d3cda06036ae0546442e5b1a83b26a436efea5b727bf1bcbe7e12b47d81", 1},
  75     {"-0x28d5a2b8f330910a9d3cda06036ae0546442e5b1a83b26a436efea5b727bf1bcbe7e12b47d81", 1},
  76     {NULL, 0}
  77   };
  78
  79
  80 void
  81 check_tests ()
  82 {
  83   mpz_t x;
  84   int i;
  85   int got, want;
  86
  87   mpz_init (x);
  88
  89   for (i = 0; tests[i].num_as_str != NULL; i++)
  90     {
  91       mpz_set_str (x, tests[i].num_as_str, 0);
  92       got = mpz_perfect_power_p (x);
  93       want = tests[i].want;
  94       if (got != want)
  95         {
  96           fprintf (stderr, "mpz_perfect_power_p returns %d when %d was expected\n", got, want);
  97           fprintf (stderr, "fault operand: %s\n", tests[i].num_as_str);
  98           abort ();
  99         }
 100     }
 101
 102   mpz_clear (x);
 103 }
 104
 105 #define NRP 15
 106
 107 void
 108 check_random (int reps)
 109 {
 110   mpz_t n, np, temp, primes[NRP];
 111   int i, j, k, unique, destroy, res;
 112   unsigned long int nrprimes, primebits, 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) + 1;
 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)
 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         }
 216     }
 217
 218   mpz_clear (n);
 219   mpz_clear (np);
 220   mpz_clear (temp);
 221   for (i = 0; i < NRP; i++)
 222     mpz_clear (primes[i]);
 223 }
 224
 225 int
 226 main (int argc, char **argv)
 227 {
 228   int n_tests;
 229
 230   tests_start ();
 231   mp_trace_base = -16;
 232
 233   check_tests ();
 234
 235   n_tests = 1000;
 236   if (argc == 2)
 237     n_tests = atoi (argv[1]);
 238   check_random (n_tests);
 239
 240   tests_end ();
 241   exit (0);
 242 }