third_party/gmp/tests/mpz/t-bin.c

/* Exercise mpz_bin_ui and mpz_bin_uiui.

Copyright 2000, 2001, 2010, 2012, 2018 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_fdiv_q_ui (want, want, k);
	}
      for (i = r >> 3; i > 0; i--)
	{
	  n++;
	  mpz_mul_ui (want, want, n);
	  mpz_fdiv_q_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_tdiv_q_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_tdiv_q (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_tdiv_q_ui (want, want, k);
	}
      for (i = r >> 3; i > 0; i--)
	{
	  mpz_mul_ui (want, want, n - k);
	  mpz_tdiv_q_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);
}