aboutsummaryrefslogtreecommitdiff
path: root/gmp-6.3.0/tests/mpz/t-bin.c
diff options
context:
space:
mode:
Diffstat (limited to 'gmp-6.3.0/tests/mpz/t-bin.c')
-rw-r--r--gmp-6.3.0/tests/mpz/t-bin.c328
1 files changed, 328 insertions, 0 deletions
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 <stdio.h>
+#include <stdlib.h>
+#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);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-19 16:59:36 +0000