1/* Exercise mpz_bin_ui and mpz_bin_uiui. 2 3Copyright 2000, 2001, 2010, 2012, 2018 Free Software Foundation, Inc. 4 5This file is part of the GNU MP Library test suite. 6 7The GNU MP Library test suite is free software; you can redistribute it 8and/or modify it under the terms of the GNU General Public License as 9published by the Free Software Foundation; either version 3 of the License, 10or (at your option) any later version. 11 12The GNU MP Library test suite is distributed in the hope that it will be 13useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General 15Public License for more details. 16 17You should have received a copy of the GNU General Public License along with 18the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ 19 20#include <stdio.h> 21#include <stdlib.h> 22#include "gmp-impl.h" 23#include "tests.h" 24 25/* Default number of generated tests. */ 26#define COUNT 700 27 28void 29try_mpz_bin_ui (mpz_srcptr want, mpz_srcptr n, unsigned long k) 30{ 31 mpz_t got; 32 33 mpz_init (got); 34 mpz_bin_ui (got, n, k); 35 MPZ_CHECK_FORMAT (got); 36 if (mpz_cmp (got, want) != 0) 37 { 38 printf ("mpz_bin_ui wrong\n"); 39 printf (" n="); mpz_out_str (stdout, 10, n); printf ("\n"); 40 printf (" k=%lu\n", k); 41 printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n"); 42 printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n"); 43 abort(); 44 } 45 mpz_clear (got); 46} 47 48 49void 50try_mpz_bin_uiui (mpz_srcptr want, unsigned long n, unsigned long k) 51{ 52 mpz_t got; 53 54 mpz_init (got); 55 mpz_bin_uiui (got, n, k); 56 MPZ_CHECK_FORMAT (got); 57 if (mpz_cmp (got, want) != 0) 58 { 59 printf ("mpz_bin_uiui wrong\n"); 60 printf (" n=%lu\n", n); 61 printf (" k=%lu\n", k); 62 printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n"); 63 printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n"); 64 abort(); 65 } 66 mpz_clear (got); 67} 68 69 70void 71samples (void) 72{ 73 static const struct { 74 const char *n; 75 unsigned long k; 76 const char *want; 77 } data[] = { 78 79 { "0", 123456, "0" }, 80 { "1", 543210, "0" }, 81 { "2", 123321, "0" }, 82 { "3", 234567, "0" }, 83 { "10", 23456, "0" }, 84 85 /* negatives, using bin(-n,k)=bin(n+k-1,k) */ 86 { "-1", 0, "1" }, 87 { "-1", 1, "-1" }, 88 { "-1", 2, "1" }, 89 { "-1", 3, "-1" }, 90 { "-1", 4, "1" }, 91 92 { "-2", 0, "1" }, 93 { "-2", 1, "-2" }, 94 { "-2", 2, "3" }, 95 { "-2", 3, "-4" }, 96 { "-2", 4, "5" }, 97 { "-2", 5, "-6" }, 98 { "-2", 6, "7" }, 99 100 { "-3", 0, "1" }, 101 { "-3", 1, "-3" }, 102 { "-3", 2, "6" }, 103 { "-3", 3, "-10" }, 104 { "-3", 4, "15" }, 105 { "-3", 5, "-21" }, 106 { "-3", 6, "28" }, 107 108 /* A few random values */ 109 { "41", 20, "269128937220" }, 110 { "62", 37, "147405545359541742" }, 111 { "50", 18, "18053528883775" }, 112 { "149", 21, "19332950844468483467894649" }, 113 }; 114 115 mpz_t n, want; 116 int i; 117 118 mpz_init (n); 119 mpz_init (want); 120 121 for (i = 0; i < numberof (data); i++) 122 { 123 mpz_set_str_or_abort (n, data[i].n, 0); 124 mpz_set_str_or_abort (want, data[i].want, 0); 125 126 try_mpz_bin_ui (want, n, data[i].k); 127 128 if (mpz_fits_ulong_p (n)) 129 try_mpz_bin_uiui (want, mpz_get_ui (n), data[i].k); 130 } 131 132 mpz_clear (n); 133 mpz_clear (want); 134} 135 136 137/* Test some bin(2k,k) cases. This produces some biggish numbers to 138 exercise the limb accumulating code. */ 139void 140twos (int count) 141{ 142 mpz_t n, want; 143 unsigned long k; 144 145 mpz_init (n); 146 147 mpz_init_set_ui (want, (unsigned long) 2); 148 for (k = 1; k < count; k++) 149 { 150 mpz_set_ui (n, 2*k); 151 try_mpz_bin_ui (want, n, k); 152 153 try_mpz_bin_uiui (want, 2*k, k); 154 155 mpz_mul_ui (want, want, 2*(2*k+1)); 156 mpz_fdiv_q_ui (want, want, k+1); 157 } 158 159 mpz_clear (n); 160 mpz_clear (want); 161} 162 163/* Test some random bin(n,k) cases. This produces some biggish 164 numbers to exercise the limb accumulating code. */ 165void 166randomwalk (int count) 167{ 168 mpz_t n_z, want, tmp; 169 unsigned long n, k, i, r; 170 int tests; 171 gmp_randstate_ptr rands; 172 173 rands = RANDS; 174 mpz_init (n_z); 175 176 k = 3; 177 n = 12; 178 mpz_init_set_ui (want, (unsigned long) 220); /* binomial(12,3) = 220 */ 179 180 for (tests = 1; tests < count; tests++) 181 { 182 r = gmp_urandomm_ui (rands, 62) + 1; 183 for (i = r & 7; i > 0; i--) 184 { 185 n++; k++; 186 mpz_mul_ui (want, want, n); 187 mpz_fdiv_q_ui (want, want, k); 188 } 189 for (i = r >> 3; i > 0; i--) 190 { 191 n++; 192 mpz_mul_ui (want, want, n); 193 mpz_fdiv_q_ui (want, want, n - k); 194 } 195 196 mpz_set_ui (n_z, n); 197 try_mpz_bin_ui (want, n_z, k); 198 199 try_mpz_bin_uiui (want, n, k); 200 } 201 202 k = 2; 203 mpz_urandomb (n_z, rands, 200); 204 mpz_mul (want, n_z, n_z); /* want = n_z ^ 2 */ 205 mpz_sub (want, want, n_z); /* want = n_z ^ 2 - n_z = n_z (n_z- 1) */ 206 mpz_tdiv_q_2exp (want, want, 1); /* want = n_z (n_z- 1) / 2 = binomial (n_z, 2) */ 207 mpz_init (tmp); 208 for (tests = 1; tests < count; tests++) 209 { 210 r = gmp_urandomm_ui (rands, 62) + 1; 211 for (i = r & 7; i > 0; i--) 212 { 213 k++; 214 mpz_add_ui (n_z, n_z, 1); 215 mpz_mul (want, want, n_z); 216 mpz_tdiv_q_ui (want, want, k); 217 } 218 for (i = r >> 3; i > 0; i--) 219 { 220 mpz_add_ui (n_z, n_z, 1); 221 mpz_mul (want, want, n_z); 222 mpz_sub_ui (tmp, n_z, k); 223 mpz_tdiv_q (want, want, tmp); 224 } 225 226 try_mpz_bin_ui (want, n_z, k); 227 } 228 229 mpz_clear (tmp); 230 mpz_clear (n_z); 231 mpz_clear (want); 232} 233 234/* Test some random bin(n,k) cases. This produces some biggish 235 numbers to exercise the limb accumulating code. */ 236void 237randomwalk_down (int count) 238{ 239 mpz_t n_z, want, tmp; 240 unsigned long n, k, i, r; 241 int tests; 242 gmp_randstate_ptr rands; 243 244 rands = RANDS; 245 mpz_init (n_z); 246 mpz_init (tmp); 247 248 k = 2; 249 n = ULONG_MAX; 250 mpz_init_set_ui (want, n); 251 mpz_mul_ui (want, want, n >> 1); 252 253 for (tests = 1; tests < count; tests++) 254 { 255 r = gmp_urandomm_ui (rands, 62) + 1; 256 for (i = r & 7; i > 0; i--) 257 { 258 mpz_mul_ui (want, want, n - k); 259 ++k; 260 mpz_tdiv_q_ui (want, want, k); 261 } 262 for (i = r >> 3; i > 0; i--) 263 { 264 mpz_mul_ui (want, want, n - k); 265 mpz_tdiv_q_ui (want, want, n); 266 --n; 267 } 268 269 mpz_set_ui (n_z, n); 270 try_mpz_bin_ui (want, n_z, n - k); 271 272 try_mpz_bin_uiui (want, n, n - k); 273 } 274 275 mpz_clear (tmp); 276 mpz_clear (n_z); 277 mpz_clear (want); 278} 279 280 281/* Test all bin(n,k) cases, with 0 <= k <= n + 1 <= count. */ 282void 283smallexaustive (unsigned int count) 284{ 285 mpz_t n_z, want; 286 unsigned long n, k; 287 288 mpz_init (n_z); 289 mpz_init (want); 290 291 for (n = 0; n < count; n++) 292 { 293 mpz_set_ui (want, (unsigned long) 1); 294 mpz_set_ui (n_z, n); 295 for (k = 0; k <= n; k++) 296 { 297 try_mpz_bin_ui (want, n_z, k); 298 try_mpz_bin_uiui (want, n, k); 299 mpz_mul_ui (want, want, n - k); 300 mpz_fdiv_q_ui (want, want, k + 1); 301 } 302 try_mpz_bin_ui (want, n_z, k); 303 try_mpz_bin_uiui (want, n, k); 304 } 305 306 mpz_clear (n_z); 307 mpz_clear (want); 308} 309 310int 311main (int argc, char **argv) 312{ 313 int count; 314 315 count = COUNT; 316 TESTS_REPS (count, argv, argc); 317 318 tests_start (); 319 320 samples (); 321 smallexaustive (count >> 4); 322 twos (count >> 1); 323 randomwalk (count - (count >> 1)); 324 randomwalk_down (count >> 1); 325 326 tests_end (); 327 exit (0); 328} 329