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
check_tests()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
check_random(int reps)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
main(int argc,char ** argv)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