diff options
Diffstat (limited to 'gmp-6.3.0/tests/mpz/t-perfpow.c')
| -rw-r--r-- | gmp-6.3.0/tests/mpz/t-perfpow.c | 247 |
1 files changed, 247 insertions, 0 deletions
diff --git a/gmp-6.3.0/tests/mpz/t-perfpow.c b/gmp-6.3.0/tests/mpz/t-perfpow.c new file mode 100644 index 0000000..84f9c8e --- /dev/null +++ b/gmp-6.3.0/tests/mpz/t-perfpow.c @@ -0,0 +1,247 @@ +/* Test mpz_perfect_power_p. + + Contributed to the GNU project by Torbjorn Granlund and Martin Boij. + +Copyright 2008-2010, 2014 Free Software Foundation, Inc. + +This file is part of the GNU MP Library test suite. + +The GNU MP Library test suite is free software; you can redistribute it +and/or modify it under the terms of the GNU General Public License as +published by the Free Software Foundation; either version 3 of the License, +or (at your option) any later version. + +The GNU MP Library test suite is distributed in the hope that it will be +useful, but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General +Public License for more details. + +You should have received a copy of the GNU General Public License along with +the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ + +#include <stdio.h> +#include <stdlib.h> + +#include "gmp-impl.h" +#include "tests.h" + +struct +{ + const char *num_as_str; + char want; +} static tests[] = + { + { "0", 1}, + { "1", 1}, + {"-1", 1}, + { "2", 0}, + {"-2", 0}, + { "3", 0}, + {"-3", 0}, + { "4", 1}, + {"-4", 0}, + { "64", 1}, + {"-64", 1}, + { "128", 1}, + {"-128", 1}, + { "256", 1}, + {"-256", 0}, + { "512", 1}, + {"-512", 1}, + { "0x4000000", 1}, + {"-0x4000000", 1}, + { "0x3cab640", 1}, + {"-0x3cab640", 0}, + { "0x3e23840", 1}, + {"-0x3e23840", 0}, + { "0x3d3a7ed1", 1}, + {"-0x3d3a7ed1", 1}, + { "0x30a7a6000", 1}, + {"-0x30a7a6000", 1}, + { "0xf33e5a5a59", 1}, + {"-0xf33e5a5a59", 0}, + { "0xed1b1182118135d", 1}, + {"-0xed1b1182118135d", 1}, + { "0xe71f6eb7689cc276b2f1", 1}, + {"-0xe71f6eb7689cc276b2f1", 0}, + { "0x12644507fe78cf563a4b342c92e7da9fe5e99cb75a01", 1}, + {"-0x12644507fe78cf563a4b342c92e7da9fe5e99cb75a01", 0}, + { "0x1ff2e7c581bb0951df644885bd33f50e472b0b73a204e13cbe98fdb424d66561e4000000", 1}, + {"-0x1ff2e7c581bb0951df644885bd33f50e472b0b73a204e13cbe98fdb424d66561e4000000", 1}, + { "0x2b9b44db2d91a6f8165c8c7339ef73633228ea29e388592e80354e4380004aad84000000", 1}, + {"-0x2b9b44db2d91a6f8165c8c7339ef73633228ea29e388592e80354e4380004aad84000000", 1}, + { "0x28d5a2b8f330910a9d3cda06036ae0546442e5b1a83b26a436efea5b727bf1bcbe7e12b47d81", 1}, + {"-0x28d5a2b8f330910a9d3cda06036ae0546442e5b1a83b26a436efea5b727bf1bcbe7e12b47d81", 1}, + {NULL, 0} + }; + + +void +check_tests () +{ + mpz_t x; + int i; + int got, want; + + mpz_init (x); + + for (i = 0; tests[i].num_as_str != NULL; i++) + { + mpz_set_str (x, tests[i].num_as_str, 0); + got = mpz_perfect_power_p (x); + want = tests[i].want; + if (got != want) + { + fprintf (stderr, "mpz_perfect_power_p returns %d when %d was expected\n", got, want); + fprintf (stderr, "fault operand: %s\n", tests[i].num_as_str); + abort (); + } + } + + mpz_clear (x); +} + +#define NRP 15 + +void +check_random (int reps) +{ + mpz_t n, np, temp, primes[NRP]; + int i, j, k, unique, destroy, res; + unsigned long int nrprimes, primebits; + mp_limb_t g, exp[NRP], e; + gmp_randstate_ptr rands; + + rands = RANDS; + + mpz_init (n); + mpz_init (np); + mpz_init (temp); + + for (i = 0; i < NRP; i++) + mpz_init (primes[i]); + + for (i = 0; i < reps; i++) + { + mpz_urandomb (np, rands, 32); + nrprimes = mpz_get_ui (np) % NRP + 1; /* 1-NRP unique primes */ + + mpz_urandomb (np, rands, 32); + g = mpz_get_ui (np) % 32 + 2; /* gcd 2-33 */ + + for (j = 0; j < nrprimes;) + { + mpz_urandomb (np, rands, 32); + primebits = mpz_get_ui (np) % 100 + 3; /* 3-102 bit primes */ + mpz_urandomb (primes[j], rands, primebits); + mpz_nextprime (primes[j], primes[j]); + unique = 1; + for (k = 0; k < j; k++) + { + if (mpz_cmp (primes[j], primes[k]) == 0) + { + unique = 0; + break; + } + } + if (unique) + { + mpz_urandomb (np, rands, 32); + e = 371 / (10 * primebits) + mpz_get_ui (np) % 11 + 1; /* Magic constants */ + exp[j++] = g * e; + } + } + + if (nrprimes > 1) + { + /* Destroy d exponents, d in [1, nrprimes - 1] */ + if (nrprimes == 2) + { + destroy = 1; + } + else + { + mpz_urandomb (np, rands, 32); + destroy = mpz_get_ui (np) % (nrprimes - 2); + } + + g = exp[destroy]; + for (k = destroy + 1; k < nrprimes; k++) + g = mpn_gcd_1 (&g, 1, exp[k]); + + for (j = 0; j < destroy; j++) + { + mpz_urandomb (np, rands, 32); + e = mpz_get_ui (np) % 50 + 1; + while (mpn_gcd_1 (&g, 1, e) > 1) + e++; + + exp[j] = e; + } + } + + /* Compute n */ + mpz_pow_ui (n, primes[0], exp[0]); + for (j = 1; j < nrprimes; j++) + { + mpz_pow_ui (temp, primes[j], exp[j]); + mpz_mul (n, n, temp); + } + + res = mpz_perfect_power_p (n); + + if (nrprimes == 1) + { + if (res == 0 && exp[0] > 1) + { + printf("n is a perfect power, perfpow_p disagrees\n"); + gmp_printf("n = %Zu\nprimes[0] = %Zu\nexp[0] = %lu\n", n, primes[0], exp[0]); + abort (); + } + else if (res == 1 && exp[0] == 1) + { + gmp_printf("n = %Zu\n", n); + printf("n is now a prime number, but perfpow_p still believes n is a perfect power\n"); + abort (); + } + } + else + { + if (res == 1 && destroy != 0) + { + gmp_printf("n = %Zu\nn was destroyed, but perfpow_p still believes n is a perfect power\n", n); + abort (); + } + else if (res == 0 && destroy == 0) + { + gmp_printf("n = %Zu\nn is a perfect power, perfpow_p disagrees\n", n); + abort (); + } + } + } + + mpz_clear (n); + mpz_clear (np); + mpz_clear (temp); + for (i = 0; i < NRP; i++) + mpz_clear (primes[i]); +} + +int +main (int argc, char **argv) +{ + int n_tests; + + tests_start (); + mp_trace_base = -16; + + check_tests (); + + n_tests = 500; + if (argc == 2) + n_tests = atoi (argv[1]); + check_random (n_tests); + + tests_end (); + exit (0); +} |