t-perfpow.c
上传用户:qaz666999
上传日期:2022-08-06
资源大小:2570k
文件大小:6k
- /* Test mpz_perfect_power_p.
- Contributed to the GNU project by Torbjorn Granlund and Martin Boij.
- Copyright 2008, 2009 Free Software Foundation, Inc.
- This file is part of the GNU MP Library.
- The GNU MP Library is free software; you can redistribute it and/or modify
- it under the terms of the GNU Lesser 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 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 Lesser General Public
- License for more details.
- You should have received a copy of the GNU Lesser General Public License
- along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
- #include <stdio.h>
- #include <stdlib.h>
- #include "gmp.h"
- #include "gmp-impl.h"
- #include "tests.h"
- struct
- {
- char *num_as_str;
- char want;
- } 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 expectedn", got, want);
- fprintf (stderr, "fault operand: %sn", 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, 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) + 1;
- }
- 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 disagreesn");
- gmp_printf("n = %Zunprimes[0] = %Zunexp[0] = %lun", n, primes[0], exp[0]);
- abort ();
- }
- else if (res == 1 && exp[0] == 1)
- {
- gmp_printf("n = %Zun", n);
- printf("n is now a prime number, but perfpow_p still believes n is a perfect powern");
- abort ();
- }
- }
- else
- {
- if (res == 1)
- {
- gmp_printf("n = %Zunn was destroyed, but perfpow_p still believes n is a perfect powern", 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 = 1000;
- if (argc == 2)
- n_tests = atoi (argv[1]);
- check_random (n_tests);
- tests_end ();
- exit (0);
- }