From 11da511c784eca003deb90c23570f0873954e0de Mon Sep 17 00:00:00 2001 From: Duncan Wilkie Date: Sat, 18 Nov 2023 06:11:09 -0600 Subject: Initial commit. --- gmp-6.3.0/tests/mpz/t-bin.c | 328 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 328 insertions(+) create mode 100644 gmp-6.3.0/tests/mpz/t-bin.c (limited to 'gmp-6.3.0/tests/mpz/t-bin.c') diff --git a/gmp-6.3.0/tests/mpz/t-bin.c b/gmp-6.3.0/tests/mpz/t-bin.c new file mode 100644 index 0000000..b647be4 --- /dev/null +++ b/gmp-6.3.0/tests/mpz/t-bin.c @@ -0,0 +1,328 @@ +/* Exercise mpz_bin_ui and mpz_bin_uiui. + +Copyright 2000, 2001, 2010, 2012, 2018, 2020 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 +#include +#include "gmp-impl.h" +#include "tests.h" + +/* Default number of generated tests. */ +#define COUNT 700 + +void +try_mpz_bin_ui (mpz_srcptr want, mpz_srcptr n, unsigned long k) +{ + mpz_t got; + + mpz_init (got); + mpz_bin_ui (got, n, k); + MPZ_CHECK_FORMAT (got); + if (mpz_cmp (got, want) != 0) + { + printf ("mpz_bin_ui wrong\n"); + printf (" n="); mpz_out_str (stdout, 10, n); printf ("\n"); + printf (" k=%lu\n", k); + printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n"); + printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n"); + abort(); + } + mpz_clear (got); +} + + +void +try_mpz_bin_uiui (mpz_srcptr want, unsigned long n, unsigned long k) +{ + mpz_t got; + + mpz_init (got); + mpz_bin_uiui (got, n, k); + MPZ_CHECK_FORMAT (got); + if (mpz_cmp (got, want) != 0) + { + printf ("mpz_bin_uiui wrong\n"); + printf (" n=%lu\n", n); + printf (" k=%lu\n", k); + printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n"); + printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n"); + abort(); + } + mpz_clear (got); +} + + +void +samples (void) +{ + static const struct { + const char *n; + unsigned long k; + const char *want; + } data[] = { + + { "0", 123456, "0" }, + { "1", 543210, "0" }, + { "2", 123321, "0" }, + { "3", 234567, "0" }, + { "10", 23456, "0" }, + + /* negatives, using bin(-n,k)=bin(n+k-1,k) */ + { "-1", 0, "1" }, + { "-1", 1, "-1" }, + { "-1", 2, "1" }, + { "-1", 3, "-1" }, + { "-1", 4, "1" }, + + { "-2", 0, "1" }, + { "-2", 1, "-2" }, + { "-2", 2, "3" }, + { "-2", 3, "-4" }, + { "-2", 4, "5" }, + { "-2", 5, "-6" }, + { "-2", 6, "7" }, + + { "-3", 0, "1" }, + { "-3", 1, "-3" }, + { "-3", 2, "6" }, + { "-3", 3, "-10" }, + { "-3", 4, "15" }, + { "-3", 5, "-21" }, + { "-3", 6, "28" }, + + /* A few random values */ + { "41", 20, "269128937220" }, + { "62", 37, "147405545359541742" }, + { "50", 18, "18053528883775" }, + { "149", 21, "19332950844468483467894649" }, + }; + + mpz_t n, want; + int i; + + mpz_init (n); + mpz_init (want); + + for (i = 0; i < numberof (data); i++) + { + mpz_set_str_or_abort (n, data[i].n, 0); + mpz_set_str_or_abort (want, data[i].want, 0); + + try_mpz_bin_ui (want, n, data[i].k); + + if (mpz_fits_ulong_p (n)) + try_mpz_bin_uiui (want, mpz_get_ui (n), data[i].k); + } + + mpz_clear (n); + mpz_clear (want); +} + + +/* Test some bin(2k,k) cases. This produces some biggish numbers to + exercise the limb accumulating code. */ +void +twos (int count) +{ + mpz_t n, want; + unsigned long k; + + mpz_init (n); + + mpz_init_set_ui (want, (unsigned long) 2); + for (k = 1; k < count; k++) + { + mpz_set_ui (n, 2*k); + try_mpz_bin_ui (want, n, k); + + try_mpz_bin_uiui (want, 2*k, k); + + mpz_mul_ui (want, want, 2*(2*k+1)); + mpz_fdiv_q_ui (want, want, k+1); + } + + mpz_clear (n); + mpz_clear (want); +} + +/* Test some random bin(n,k) cases. This produces some biggish + numbers to exercise the limb accumulating code. */ +void +randomwalk (int count) +{ + mpz_t n_z, want, tmp; + unsigned long n, k, i, r; + int tests; + gmp_randstate_ptr rands; + + rands = RANDS; + mpz_init (n_z); + + k = 3; + n = 12; + mpz_init_set_ui (want, (unsigned long) 220); /* binomial(12,3) = 220 */ + + for (tests = 1; tests < count; tests++) + { + r = gmp_urandomm_ui (rands, 62) + 1; + for (i = r & 7; i > 0; i--) + { + n++; k++; + mpz_mul_ui (want, want, n); + mpz_divexact_ui (want, want, k); + } + for (i = r >> 3; i > 0; i--) + { + n++; + mpz_mul_ui (want, want, n); + mpz_divexact_ui (want, want, n - k); + } + + mpz_set_ui (n_z, n); + try_mpz_bin_ui (want, n_z, k); + + try_mpz_bin_uiui (want, n, k); + } + + k = 2; + mpz_urandomb (n_z, rands, 200); + mpz_mul (want, n_z, n_z); /* want = n_z ^ 2 */ + mpz_sub (want, want, n_z); /* want = n_z ^ 2 - n_z = n_z (n_z- 1) */ + mpz_tdiv_q_2exp (want, want, 1); /* want = n_z (n_z- 1) / 2 = binomial (n_z, 2) */ + mpz_init (tmp); + for (tests = 1; tests < count; tests++) + { + r = gmp_urandomm_ui (rands, 62) + 1; + for (i = r & 7; i > 0; i--) + { + k++; + mpz_add_ui (n_z, n_z, 1); + mpz_mul (want, want, n_z); + mpz_divexact_ui (want, want, k); + } + for (i = r >> 3; i > 0; i--) + { + mpz_add_ui (n_z, n_z, 1); + mpz_mul (want, want, n_z); + mpz_sub_ui (tmp, n_z, k); + mpz_divexact (want, want, tmp); + } + + try_mpz_bin_ui (want, n_z, k); + } + + mpz_clear (tmp); + mpz_clear (n_z); + mpz_clear (want); +} + +/* Test some random bin(n,k) cases. This produces some biggish + numbers to exercise the limb accumulating code. */ +void +randomwalk_down (int count) +{ + mpz_t n_z, want, tmp; + unsigned long n, k, i, r; + int tests; + gmp_randstate_ptr rands; + + rands = RANDS; + mpz_init (n_z); + mpz_init (tmp); + + k = 2; + n = ULONG_MAX; + mpz_init_set_ui (want, n); + mpz_mul_ui (want, want, n >> 1); + + for (tests = 1; tests < count; tests++) + { + r = gmp_urandomm_ui (rands, 62) + 1; + for (i = r & 7; i > 0; i--) + { + mpz_mul_ui (want, want, n - k); + ++k; + mpz_divexact_ui (want, want, k); + } + for (i = r >> 3; i > 0; i--) + { + mpz_mul_ui (want, want, n - k); + mpz_divexact_ui (want, want, n); + --n; + } + + mpz_set_ui (n_z, n); + try_mpz_bin_ui (want, n_z, n - k); + + try_mpz_bin_uiui (want, n, n - k); + } + + mpz_clear (tmp); + mpz_clear (n_z); + mpz_clear (want); +} + + +/* Test all bin(n,k) cases, with 0 <= k <= n + 1 <= count. */ +void +smallexaustive (unsigned int count) +{ + mpz_t n_z, want; + unsigned long n, k; + + mpz_init (n_z); + mpz_init (want); + + for (n = 0; n < count; n++) + { + mpz_set_ui (want, (unsigned long) 1); + mpz_set_ui (n_z, n); + for (k = 0; k <= n; k++) + { + try_mpz_bin_ui (want, n_z, k); + try_mpz_bin_uiui (want, n, k); + mpz_mul_ui (want, want, n - k); + mpz_fdiv_q_ui (want, want, k + 1); + } + try_mpz_bin_ui (want, n_z, k); + try_mpz_bin_uiui (want, n, k); + } + + mpz_clear (n_z); + mpz_clear (want); +} + +int +main (int argc, char **argv) +{ + int count; + + count = COUNT; + TESTS_REPS (count, argv, argc); + + tests_start (); + + samples (); + smallexaustive (count >> 4); + twos (count >> 1); + randomwalk (count - (count >> 1)); + randomwalk_down (count >> 1); + + tests_end (); + exit (0); +} -- cgit v1.2.3