tests/mpz/t-bin.c

/* 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);
}