|
Packit |
5c3484 |
/* Exercise mpz_bin_ui and mpz_bin_uiui.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Copyright 2000, 2001, 2010, 2012 Free Software Foundation, Inc.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This file is part of the GNU MP Library test suite.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library test suite is free software; you can redistribute it
|
|
Packit |
5c3484 |
and/or modify it under the terms of the GNU General Public License as
|
|
Packit |
5c3484 |
published by the Free Software Foundation; either version 3 of the License,
|
|
Packit |
5c3484 |
or (at your option) any later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library test suite is distributed in the hope that it will be
|
|
Packit |
5c3484 |
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
5c3484 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
|
|
Packit |
5c3484 |
Public License for more details.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
You should have received a copy of the GNU General Public License along with
|
|
Packit |
5c3484 |
the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include <stdio.h>
|
|
Packit |
5c3484 |
#include <stdlib.h>
|
|
Packit |
5c3484 |
#include "gmp.h"
|
|
Packit |
5c3484 |
#include "gmp-impl.h"
|
|
Packit |
5c3484 |
#include "tests.h"
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Default number of generated tests. */
|
|
Packit |
5c3484 |
#define COUNT 700
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
try_mpz_bin_ui (mpz_srcptr want, mpz_srcptr n, unsigned long k)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_t got;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_init (got);
|
|
Packit |
5c3484 |
mpz_bin_ui (got, n, k);
|
|
Packit |
5c3484 |
MPZ_CHECK_FORMAT (got);
|
|
Packit |
5c3484 |
if (mpz_cmp (got, want) != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
printf ("mpz_bin_ui wrong\n");
|
|
Packit |
5c3484 |
printf (" n="); mpz_out_str (stdout, 10, n); printf ("\n");
|
|
Packit |
5c3484 |
printf (" k=%lu\n", k);
|
|
Packit |
5c3484 |
printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n");
|
|
Packit |
5c3484 |
printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n");
|
|
Packit |
5c3484 |
abort();
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
mpz_clear (got);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
try_mpz_bin_uiui (mpz_srcptr want, unsigned long n, unsigned long k)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_t got;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_init (got);
|
|
Packit |
5c3484 |
mpz_bin_uiui (got, n, k);
|
|
Packit |
5c3484 |
MPZ_CHECK_FORMAT (got);
|
|
Packit |
5c3484 |
if (mpz_cmp (got, want) != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
printf ("mpz_bin_uiui wrong\n");
|
|
Packit |
5c3484 |
printf (" n=%lu\n", n);
|
|
Packit |
5c3484 |
printf (" k=%lu\n", k);
|
|
Packit |
5c3484 |
printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n");
|
|
Packit |
5c3484 |
printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n");
|
|
Packit |
5c3484 |
abort();
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
mpz_clear (got);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
samples (void)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
static const struct {
|
|
Packit |
5c3484 |
const char *n;
|
|
Packit |
5c3484 |
unsigned long k;
|
|
Packit |
5c3484 |
const char *want;
|
|
Packit |
5c3484 |
} data[] = {
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
{ "0", 123456, "0" },
|
|
Packit |
5c3484 |
{ "1", 543210, "0" },
|
|
Packit |
5c3484 |
{ "2", 123321, "0" },
|
|
Packit |
5c3484 |
{ "3", 234567, "0" },
|
|
Packit |
5c3484 |
{ "10", 23456, "0" },
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* negatives, using bin(-n,k)=bin(n+k-1,k) */
|
|
Packit |
5c3484 |
{ "-1", 0, "1" },
|
|
Packit |
5c3484 |
{ "-1", 1, "-1" },
|
|
Packit |
5c3484 |
{ "-1", 2, "1" },
|
|
Packit |
5c3484 |
{ "-1", 3, "-1" },
|
|
Packit |
5c3484 |
{ "-1", 4, "1" },
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
{ "-2", 0, "1" },
|
|
Packit |
5c3484 |
{ "-2", 1, "-2" },
|
|
Packit |
5c3484 |
{ "-2", 2, "3" },
|
|
Packit |
5c3484 |
{ "-2", 3, "-4" },
|
|
Packit |
5c3484 |
{ "-2", 4, "5" },
|
|
Packit |
5c3484 |
{ "-2", 5, "-6" },
|
|
Packit |
5c3484 |
{ "-2", 6, "7" },
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
{ "-3", 0, "1" },
|
|
Packit |
5c3484 |
{ "-3", 1, "-3" },
|
|
Packit |
5c3484 |
{ "-3", 2, "6" },
|
|
Packit |
5c3484 |
{ "-3", 3, "-10" },
|
|
Packit |
5c3484 |
{ "-3", 4, "15" },
|
|
Packit |
5c3484 |
{ "-3", 5, "-21" },
|
|
Packit |
5c3484 |
{ "-3", 6, "28" },
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* A few random values */
|
|
Packit |
5c3484 |
{ "41", 20, "269128937220" },
|
|
Packit |
5c3484 |
{ "62", 37, "147405545359541742" },
|
|
Packit |
5c3484 |
{ "50", 18, "18053528883775" },
|
|
Packit |
5c3484 |
{ "149", 21, "19332950844468483467894649" },
|
|
Packit |
5c3484 |
};
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_t n, want;
|
|
Packit |
5c3484 |
int i;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_init (n);
|
|
Packit |
5c3484 |
mpz_init (want);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (i = 0; i < numberof (data); i++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_set_str_or_abort (n, data[i].n, 0);
|
|
Packit |
5c3484 |
mpz_set_str_or_abort (want, data[i].want, 0);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
try_mpz_bin_ui (want, n, data[i].k);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (mpz_fits_ulong_p (n))
|
|
Packit |
5c3484 |
try_mpz_bin_uiui (want, mpz_get_ui (n), data[i].k);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_clear (n);
|
|
Packit |
5c3484 |
mpz_clear (want);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Test some bin(2k,k) cases. This produces some biggish numbers to
|
|
Packit |
5c3484 |
exercise the limb accumulating code. */
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
twos (int count)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_t n, want;
|
|
Packit |
5c3484 |
unsigned long k;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_init (n);
|
|
Packit |
5c3484 |
mpz_init (want);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_set_ui (want, (unsigned long) 2);
|
|
Packit |
5c3484 |
for (k = 1; k < count; k++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_set_ui (n, 2*k);
|
|
Packit |
5c3484 |
try_mpz_bin_ui (want, n, k);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
try_mpz_bin_uiui (want, 2*k, k);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_mul_ui (want, want, 2*(2*k+1));
|
|
Packit |
5c3484 |
mpz_fdiv_q_ui (want, want, k+1);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_clear (n);
|
|
Packit |
5c3484 |
mpz_clear (want);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Test some random bin(n,k) cases. This produces some biggish
|
|
Packit |
5c3484 |
numbers to exercise the limb accumulating code. */
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
randomwalk (int count)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_t n_z, want;
|
|
Packit |
5c3484 |
unsigned long n, k, i, r;
|
|
Packit |
5c3484 |
int tests;
|
|
Packit |
5c3484 |
gmp_randstate_ptr rands;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
rands = RANDS;
|
|
Packit |
5c3484 |
mpz_init (n_z);
|
|
Packit |
5c3484 |
mpz_init (want);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
k = 3;
|
|
Packit |
5c3484 |
n = 12;
|
|
Packit |
5c3484 |
mpz_set_ui (want, (unsigned long) 220); /* binomial(12,3) = 220 */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (tests = 1; tests < count; tests++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
r = gmp_urandomm_ui (rands, 62) + 1;
|
|
Packit |
5c3484 |
for (i = r & 7; i > 0; i--)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
n++; k++;
|
|
Packit |
5c3484 |
mpz_mul_ui (want, want, n);
|
|
Packit |
5c3484 |
mpz_fdiv_q_ui (want, want, k);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
for (i = r >> 3; i > 0; i--)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
n++;
|
|
Packit |
5c3484 |
mpz_mul_ui (want, want, n);
|
|
Packit |
5c3484 |
mpz_fdiv_q_ui (want, want, n - k);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_set_ui (n_z, n);
|
|
Packit |
5c3484 |
try_mpz_bin_ui (want, n_z, k);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
try_mpz_bin_uiui (want, n, k);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_clear (n_z);
|
|
Packit |
5c3484 |
mpz_clear (want);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Test all bin(n,k) cases, with 0 <= k <= n + 1 <= count. */
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
smallexaustive (unsigned int count)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_t n_z, want;
|
|
Packit |
5c3484 |
unsigned long n, k;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_init (n_z);
|
|
Packit |
5c3484 |
mpz_init (want);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (n = 0; n < count; n++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_set_ui (want, (unsigned long) 1);
|
|
Packit |
5c3484 |
mpz_set_ui (n_z, n);
|
|
Packit |
5c3484 |
for (k = 0; k <= n; k++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
try_mpz_bin_ui (want, n_z, k);
|
|
Packit |
5c3484 |
try_mpz_bin_uiui (want, n, k);
|
|
Packit |
5c3484 |
mpz_mul_ui (want, want, n - k);
|
|
Packit |
5c3484 |
mpz_fdiv_q_ui (want, want, k + 1);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
try_mpz_bin_ui (want, n_z, k);
|
|
Packit |
5c3484 |
try_mpz_bin_uiui (want, n, k);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_clear (n_z);
|
|
Packit |
5c3484 |
mpz_clear (want);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
int
|
|
Packit |
5c3484 |
main (int argc, char **argv)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
int count;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (argc > 1)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
char *end;
|
|
Packit |
5c3484 |
count = strtol (argv[1], &end, 0);
|
|
Packit |
5c3484 |
if (*end || count <= 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
fprintf (stderr, "Invalid test count: %s.\n", argv[1]);
|
|
Packit |
5c3484 |
return 1;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
count = COUNT;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
tests_start ();
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
samples ();
|
|
Packit |
5c3484 |
smallexaustive (count >> 4);
|
|
Packit |
5c3484 |
twos (count >> 1);
|
|
Packit |
5c3484 |
randomwalk (count - (count >> 1));
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
tests_end ();
|
|
Packit |
5c3484 |
exit (0);
|
|
Packit |
5c3484 |
}
|