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. 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; 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 = 1000; 237 if (argc == 2) 238 n_tests = atoi (argv[1]); 239 check_random (n_tests); 240 241 tests_end (); 242 exit (0); 243 } 244