1 /* Test mpz_perfect_power_p. 2 3 Contributed to the GNU project by Torbjorn Granlund and Martin Boij. 4 5 Copyright 2008, 2009, 2010 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 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 const 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; 113 mp_limb_t g, exp[NRP], e; 114 gmp_randstate_ptr rands; 115 116 rands = RANDS; 117 118 mpz_init (n); 119 mpz_init (np); 120 mpz_init (temp); 121 122 for (i = 0; i < NRP; i++) 123 mpz_init (primes[i]); 124 125 for (i = 0; i < reps; i++) 126 { 127 mpz_urandomb (np, rands, 32); 128 nrprimes = mpz_get_ui (np) % NRP + 1; /* 1-NRP unique primes */ 129 130 mpz_urandomb (np, rands, 32); 131 g = mpz_get_ui (np) % 32 + 2; /* gcd 2-33 */ 132 133 for (j = 0; j < nrprimes;) 134 { 135 mpz_urandomb (np, rands, 32); 136 primebits = mpz_get_ui (np) % 100 + 3; /* 3-102 bit primes */ 137 mpz_urandomb (primes[j], rands, primebits); 138 mpz_nextprime (primes[j], primes[j]); 139 unique = 1; 140 for (k = 0; k < j; k++) 141 { 142 if (mpz_cmp (primes[j], primes[k]) == 0) 143 { 144 unique = 0; 145 break; 146 } 147 } 148 if (unique) 149 { 150 mpz_urandomb (np, rands, 32); 151 e = 371 / (10 * primebits) + mpz_get_ui (np) % 11 + 1; /* Magic constants */ 152 exp[j++] = g * e; 153 } 154 } 155 156 if (nrprimes > 1) 157 { 158 /* Destroy d exponents, d in [1, nrprimes - 1] */ 159 if (nrprimes == 2) 160 { 161 destroy = 1; 162 } 163 else 164 { 165 mpz_urandomb (np, rands, 32); 166 destroy = mpz_get_ui (np) % (nrprimes - 2) + 1; 167 } 168 169 g = exp[destroy]; 170 for (k = destroy + 1; k < nrprimes; k++) 171 g = mpn_gcd_1 (&g, 1, exp[k]); 172 173 for (j = 0; j < destroy; j++) 174 { 175 mpz_urandomb (np, rands, 32); 176 e = mpz_get_ui (np) % 50 + 1; 177 while (mpn_gcd_1 (&g, 1, e) > 1) 178 e++; 179 180 exp[j] = e; 181 } 182 } 183 184 /* Compute n */ 185 mpz_pow_ui (n, primes[0], exp[0]); 186 for (j = 1; j < nrprimes; j++) 187 { 188 mpz_pow_ui (temp, primes[j], exp[j]); 189 mpz_mul (n, n, temp); 190 } 191 192 res = mpz_perfect_power_p (n); 193 194 if (nrprimes == 1) 195 { 196 if (res == 0 && exp[0] > 1) 197 { 198 printf("n is a perfect power, perfpow_p disagrees\n"); 199 gmp_printf("n = %Zu\nprimes[0] = %Zu\nexp[0] = %lu\n", n, primes[0], exp[0]); 200 abort (); 201 } 202 else if (res == 1 && exp[0] == 1) 203 { 204 gmp_printf("n = %Zu\n", n); 205 printf("n is now a prime number, but perfpow_p still believes n is a perfect power\n"); 206 abort (); 207 } 208 } 209 else 210 { 211 if (res == 1) 212 { 213 gmp_printf("n = %Zu\nn was destroyed, but perfpow_p still believes n is a perfect power\n", n); 214 abort (); 215 } 216 } 217 } 218 219 mpz_clear (n); 220 mpz_clear (np); 221 mpz_clear (temp); 222 for (i = 0; i < NRP; i++) 223 mpz_clear (primes[i]); 224 } 225 226 int 227 main (int argc, char **argv) 228 { 229 int n_tests; 230 231 tests_start (); 232 mp_trace_base = -16; 233 234 check_tests (); 235 236 n_tests = 500; 237 if (argc == 2) 238 n_tests = atoi (argv[1]); 239 check_random (n_tests); 240 241 tests_end (); 242 exit (0); 243 } 244